1.NetworkX有向グラフショートカットノード省略プログラムの試み

ゴミ取りプログラムというのを作っております。

データの中のゴミを除去するプログラムです。

具体的には「a→b」「b→b」「a→c」という要素があった時に、ショートカットできてしまう「a→c」を除去するのです。

もちろんこれはデータが増えれば増えるほど除去対象のゴミは増えます。これらをなくして、ショートカットなどという惰弱なものを許さない有向グラフを作りたい訳です。

（実際にはプログラミング言語Pythonのネットワーク構造処理モジュールNetworkXの有向グラフDiGraphとその矢印Edgesを使っています）

2.データが大きくなりすぎると読みに行ったまま帰って来ない

当初は何も考えず、こういう時に最適な関数（何かしらの処理をする1単位の小さなプログラムのことだと思ってください）、all_simple_pathsで全件読ませていたのですが、データがある程度のサイズを超えて大きくなると、読んだきり帰ってこなくなってしまう。という事態が頻発したのでした。

3.最初は小さい区切りで処理する&一里塚でセーブデータを作る

当然こんなもん困るので、改善のため、データを切り分けてその中で小さいゴミを除去し、データをだんだんデカくして大きいゴミも取っていき、その都度セーブデータを作る。という方針を取っています。

4.大データを攻略するために安易に区切りを倍倍ゲームで増やしてはいけない

基本的にはうまく行っているのですが、やはり問題の先送りにしかなっていなかったんですね。

何かというと、データを2要素で区切ってチェックし、それが終わったら4要素で区切りチェック、次は8要素で区切りチェック、という倍倍ゲームでゴミ取りをしていたのです。

ある2の(n-1)乗ではうまく行ってたものの、次の2のn乗で、やはり行ったきり帰ってこない。という現象が起きてしまうのでした。

倍倍ゲーム、2の冪は、一般化すると指数関数というやつなのだから、それは指数関数的に大きくなるに決まってる。

大きなデータを攻略するには、区切りはもちろん大きくしていかねばならないのは確かだ。

だが、少なくとも、倍倍ゲームでは、安易に大きくなりすぎる。これではいけない。

5.指数関数と対数関数の組み合わせによってなだらかに区切りを増やす

ということで、倍倍ゲームをなだらかにしたら、もう少し丁寧にゴミが取れて、また処理が止まるリスクも減るんじゃないか？　つまり、2のn+(1/4)乗、2のn+(2/4)乗、2のn+(3/4)乗、2のn+(4/4)乗つまり2の(n+1)乗、という風に。

すると、奇妙なことに気づきます。2進対数がこれにモロに効く！

そうなのです。2進対数とは正に「2のn+(1/4)乗、2のn+(2/4)乗、2のn+(3/4)乗、2のn+(4/4)乗つまり2の(n+1)乗」のグラデーションを適切に扱うためのものなのでした。

分かった！　俺、2進対数くんのことが分かった！　（おせーよ。今更かよ）（うるせー！！　今更でも体感できたことが大事なんだよ！！！）

6.テクニカルな実装の話（テクニカルか？）

実際にはなだらかさのためにかなりカスタマイズしております。（以下、テクニカルな話になります）

まず、行数の2進対数を取ります（例えば、512行なら9という値が取れます）。

なだらかさのためにこれを3乗します（729）。場合によってはこの値に小数点以下が含まれることもあるので、これを小数点切り上げした値を処理の回数の上限とします。

そして、切り分けるデータの行数単位を512-（2の（n×n）乗）+1とします。大事なのはnは整数に限らないということで、具体的にはn=9-（カウンタ/81）です。

カウンタが729になると引く値は2の0乗すなわち1になり、ゴミ取りの枠としては512行から1を引いて足すのと同じだから要は512行。それでゴミが取り切れれば終わり。という寸法です。

「729なんか使わないで分数とかもせずにそのまま対数9回とかでやれば？」

と思いはしたのですが、これだと一発目にいきなり257行から処理せねばならず、なだらかさを欠くので下手すると行ったきり戻らなくなる可能性が高まります。

上記の通り調整すると初回は6行。次は10行。さらに次は14行、そのまた次は19行。手頃な増え方と言えます。729回もある処理も、現在のカウンタを表示させておけばまあ耐えられる。10万行までならこのプログラムで基本的には問題ない。

はずでした。

7.区切った中で同値類と商集合を使ってゴミ取りを徹底する

しかし、それでも問題の完全解決には至っていません。なだらかに増加しようが、やはり何かしらのポイントで行ったきりになってしまうのですね。

むーん。どうやら2進対数とは別に、何らかの抜根的な対処法が要るのでは？　ではどうすればいい？

今試みているのは同値類と商集合ですね。

「番地を2や3や4やnで割って（実際にはn/3の小数点切り上げを上限とする。今回のゴミ取りは要素が3つ以上ないと意味がないため）それで「余り1同士」「余り2」...「余り(n-1)」「余りなし」で集合を作り（いわゆる同値類）、これらの集合（いわゆる商集合）を作る。商集合の中で同値類ごとにゴミ取りをする」

という案です。

（テクニカルに言うと、実際には「さっき言ってた2の2進対数乗の区切り単位/n要素、n個の同値類ずつ区切った2次元配列たる商集合をつくり、これに行列の転置を行い、n要素、区切り単位/n個の同値類の2次元配列にして、n要素ずつ処理する。最後は区切り単位をまるごと処理して、次の区切り単位でこれを繰り返す）

実際にやってみると、実際にはこれでだいぶゴミは取れてきました。大したものです。

8.実際の動作

とはいえ、最初に処理に時間がかかるようになってしまいました。そりゃ後でやって困る処理を先にやるんだからしょうがない。

ただまあ、セーブがきめ細かくなるから、中断しても後で再開できるし、再開時間が省略できるのは有難い。

このまま放置しておけば、いつかはゴミを取り切れるぞー。後はパソコンさんとプログラムさんに任せた。俺は今から出勤だ（眠い）