  |
一次元インデックスから二次元インデックス、すなわちバイト数であらわされる位置から行と桁への変換がテキストエディターだとよく発生する。
この変換を素早くするために変換テーブルを作るのだが、普通に作ると更新の時にO(N)かかる。
さくさくエディターの作者は局所的行更新手法で殆どの場面ではO(1)、最悪はO(N)にしていたが、色々と事故が発生しやすい。
特にstepRowをまたぐ状況でテーブルのほぼ全部の更新を避けようと思うと事故りやすい。
俺は何度も事故を起こした。
そこで別のやり方でオーダーを削減してみた。
https://github.com/rirufa/FooList/blob/main/List/BigRangeList.cs
考え方は至極単純でRopeをたどるときに変換テーブルの長さを覚えておき、ついでに変換を済ませておこうというごくごく簡単なものである。
この方法により、変換テーブルの更新はO(Log N)+M、探索はO(Log N)+O(Log M)程度で済ませられるようになった。
局所的行更新手法に比べるとだいぶ遅いが、Mが十分に小さければそこまでコストはかからないはず。
ただし、マーカーみたいに連続していないものを放り込んだら、うまく動かないのでそこはご了承いただきたい。
Allocated GC Memory:32,803,672bytes
Allocated GC Memory:32,809,360bytes
clear buffer
Allocated GC Memory:82,976bytes
https://github.com/rirufa/FooList/blob/main/EditorDemo/Program.cs
22
