日記（2022/10/14）：クソ遅いバブルソートもどき処理を何とかして改善していた（今更何だ）

（ヘッダ画像はNHKの頃のアルゴリズム体操です）
（なぜ…？）
（NHKから要望があれば取り下げます）

＊＊＊

前職（プログラマ）の時に、データの並べ替えや照合の際に、
「同じリストを二つ作り、リストAの要素をリストBの要素全部と照合し、それを繰り返す」
ということをしばしばやりがちでした。

＊＊＊

これやるとメチャクチャ遅くなるんですよ。
単純に考えてもリスト長の2乗なので、リスト長が例えば100個だったら10,000回、1,000個だったら1,000,000回。
もし前者で10分かかって「チッ」となっているのたとしたら、後者で半日以上かかってしまいます。
プロジェクトを進めるうちに、扱うデータはどんどん増えていくものですが、データが10倍増えたら時間は100倍増える。そして数時間とかかかる。およそやっとれん。

＊＊＊

さて、最近自作プログラムでこれに悩まされていたのでした。
そこで、悩んでる最中に、ふと閃いたのでした。

「2のn乗ごとに区切っていき、整理したものをくっつけてまた整理する。
こうすれば、これ以上処理しなくていいものが早めに分かる。
それらは処理しなくてよいこととすれば、より早くなるんじゃね？」

試しにやってみました（大変でしたが）。
明らかに速い！　丸一日かかってたのが一時間もかからなくなった！　なんだこれは。（なんだこれは）

＊＊＊

とはいえ、やはりデータが増えれば増えるほど遅くなるのはしょうがないのです。
データを減らしたらどうなるか。
10分かかっていたやつは…10秒もかからん！　なんだこれは。（なんだこれは）

アルゴリズムの改善もさることながら、データ量、というか処理せねばならないゴミの量が、処理回数に大きな影響を与えているのですね。
数学で言うと、「mのn乗」回かかるとすると、アルゴリズムの改善はnを小さくすることに効果があり、ゴミの量を減らすことはmを小さくすることに効果がある。
だから、全体像にこだわらなければ、小さく区切って整理しておけば、目的には足る（もちろんそれらの前後関係は間違いないようにしなければならないが）。

たぶん今後の処理を考えると、
「適切な前後関係が保たれた上で細分化する」
→「整理して取れるゴミを取る」
→「細分化してゴミの取れたデータを少しずつ統合する」
→「そこで初めて問題になるゴミがありうるが、それも取る」
→「全部統合する」
→「全部のゴミを取る」（おそらく処理すべきゴミの量は激減しているから処理時間もさほど長くはない）

こう作業した方がいいな。頑張ろう。
（まだ仕様追加はいくつかあるので、相当頑張んなきゃならんのだよな…）