2019年12月19日

だいぶ前から作りたいと思っていてしばらく作業していたのですが、ようやく公開できるところまで持ってこられました。
maraigue/LTOList - GitHub

線形リスト(値を一列に並べるためのデータ構造)としては、配列や連結リストが有名ですが、
・配列は、ランダムアクセスが定数時間(速い)だが、挿入・削除は最悪線形時間(遅い)
・連結リストは、挿入・削除が定数時間(速い)だが、ランダムアクセスは最悪線形時間(遅い)
という性質があります。

LTOList(Logarithmic-Time-Operation List)は、その中間を取れるというものです。ランダムアクセスも挿入・削除も対数時間でできます。
実装としては、二分探索木に子孫のノード数情報を持たせることで実装しています。(英語のみですが、解説はGitHubのトップページで見られます)

【補足】

こうやれば対数時間が実現できる、というのは自力で思いついたのですが、調べてみると他にも取り組んでいる方はいました。私と違って二分探索木でなくスキップリストで実装していますが、それを除けば同じです。
要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ

ただ、「ランダムアクセスも挿入・削除も対数時間でできる」という理論的に意味がありそうな性質を持つデータ構造ながら、決まったデータ構造の名前が付いているわけでもない、というのが気になったところだったのでした。
もしかしたら「実応用上の意義が薄い」ってのはあるのかもしれません…(そもそも二分探索木を使うことが単なる配列より遅くなる原因なうえ、この実装は単なる二分探索木以上にメモリを使うので。単なる二分探索木は1要素あたりポインタ変数が3つ必要なのですが、この構造だと5個必要)。

maraigue at 23:50コメント(0)プログラミング  

コメントする

名前
 
  絵文字
 
 
livedoor プロフィール

H. Hiro

  • ライブドアブログ