pythonでskip list
skip listというデータ構造をpythonで実装しました。listとありますが、実際には探索木のような構造で、
- 要素の挿入時に木をバランスさせる必要が無い
- lock-free
なアルゴリズムだそうです。バランス操作が不要だと、並列プログラムと相性がよさそうというのは感覚的にわかります。まだ高度な実装は読んでないけれど。
画像は木構造用の画像化モジュールでskip listを画像化したものです。
- 'hello' => 'world'
- 'tic' => 'tac'
- 'hoge' => 'fuga'
- 'foo' = 'bar'
の3組を格納した状態で出力させています。
追記：削除実装するの忘れてました。挿入とほぼ同じだからいいよね^^;
