  |
テキストエディタを高速化するためにある人が書いたBigListを改造して、リーフノードをリンクドリストでつないだら全列挙が早くなって、スタックオーバーフローしなくなった。
ただ、その代わり元々のコードにあったノードの共有機能はいらなそうなので省くことにした。
Core i5 10400F、メモリー16GBで、100文字×100行＝1億文字を突っ込んで、あれこれ操作した場合はこのくらいの速度で動く。
benchmark start
Allocated GC Memory:60,392bytes
Allocated GC Memory:416,037,968bytes
Allocated GC Memory:416,082,104bytes
Allocated GC Memory:416,082,272bytes
Allocated GC Memory:416,082,296bytes
Allocated GC Memory:416,082,440bytes
clear buffer
ListやGapBufferだとGCに優しくないけど、BigListだとLOH入りしないので、GCに優しいのだ。
その代わり速度はBigListの中身はRopeなので、少し遅くなるのだ。
Ropeで、リーフノードをリンクドリストでつないだ場合、挿入と削除、追加、ランダムアクセスはO(Log N)、全列挙はO(N)なのだ。
MITライセンスなんで商用でも問題ないけど、元々のBigListのライセンスに不穏なことが書いてあったので、気になるなら、自分で書き直したほうがいい。
The rebalancing algorithm is from "Ropes: an Alternative to Strings", by
Boehm, Atkinson, and Plass, in SOFTWARE--PRACTICE AND EXPERIENCE, VOL. 25(12), 1315–1330 (DECEMBER 1995).
https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf
ちなみに俺はIQ84の境界知能で、発達障害持ちなのだ。 言語性106~120、動作性は60ぐらいなのだ。 言語性の下位項目は正常で、単語が飛びぬけて高いのだ。 動作性の下位項目はほぼ正常で...
素直にすげーな 自力でよくやった おれも自力でAndrew Ng教授のコースとかとったけど微分からやり直す羽目になって大変だったわ 半年くらいやってた
BigList<T>の内部で使われているやつをGapBuffer<T>に置き換えてみたら、リーフノードのサイズが32768だと遅くなるけど、最大メモリー使用量はそこまで変わらんな。 ブロックサイ...
RopeもといBigListでさくさくエディターの置き換え処理をやってみた。 使用したマシンはCore i7 14700、メモリー32GB、Intel ARC A750。 １００万行×１００文字を置き換え。 addはバッファーの構...
22
