Whiteのふりーとーく

仕事

速度面で懸念していた部分のO(1)化を敢行。昨日と一昨日で適当にコードを組んで今日は本番に近いデータ突っこんで試験。そして書きながら途中でデータ構造変更とかしてたせいでバグだらけだったことが露見。

そのへんを解消して現在はダミーテスト環境でぶん回し中。大胆な見直しのおかげでかなり速度は向上している…ように見える。しかし結局肝心のモジュールからO(N)な部分を排除することはできなかった。最頻で呼ばれていたくせにO(N)だった部分をO(1)化、その実現のために頻度的にはそうでもなかった部分がO(1)からO(N)に、という変更なので全体としては高速化しているはずなのだけれど。O(N)ってもbinary search(O(logN)なアルゴリズム)を使って高速化をかけてるし。

本当はどっちもO(logN)になるように2つのbinary treeでインデックス化されたデータ構造とかにするべきだったんかなあ、などと悩みつつ、しばらくはあれこれテストしてみる所存。