スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

赤黒木 高速化版

以前の赤黒木の高速化版。15~25%ぐらい速い。
高速化版といってもアルゴリズムの変更ではなく余分なストアとロードを削っただけ。

SetParentは色を読み込むためにロードが発生し結構重い。
色が確定されている状況だとストアだけにできる。
また、値を上書きすることが分かっている場合、先に行う方のストアはいらないので削ることができる。

rbtree.h


rbtree.cpp
スポンサーサイト

循環型双方向リスト

循環型双方向リスト
続きを展開する

双方向リスト/単方向リスト/xor linked list 比較

種類/項目 ノードの追加 ノードの削除 ノードの走査 ノード当りの
メモリ
速度
先頭 最後尾 任意ノードの前 任意ノードの後 先頭 最後尾 任意ノード 順番 逆順
双方向リスト ポインタ2個 速い
単方向リスト ×(*1) × × × × ポインタ1個 すごく速い
xor linked list ポインタ1個 速い?

◎ … O(1)で特に条件も無く可能
× … O(n)覚悟で先頭からリンク辿らない限り無理
△ … O(n)覚悟で先頭からリンク辿るか、前後のノードのうちいずれかのポインタがあれば可能

*1 最後尾ノードへのリンクがあれば可能

xor linked list に何か日の目が当てられないかと表にしてみたが、やっぱり微妙。
△を×扱いにすると、単方向リストと比較しての優位は、最後尾ノードへの操作が可能なことだけになる。
ありえないが、前後のノードのうちどっちかが判明している状況でなら、△を◎扱いにすることで速度が遅くなる代わりにメモリが減る双方向リストになる。

・最後尾への操作(追加だけなら単方向リストでも可能)
・最後尾からの逆順走査
のどちらかあるいは両方に加え、更に
・ポインタ1個分のメモリ
に価値を見出し
・xor演算による速度低下
を許容できる状況なら xor linked list を使えるかもしれない。
書いてて思ったが、そんなことは多分無い。
あとデバッガが使える環境だと、追いにくくなるということに難色を示されると思う。

xor linked list

前後のポインタを持つ代わりに、前後のポインタのxor値をもつ双方向リスト。
・ポインタ2個分のメモリが1個になる
・要素を操作するときには、操作する要素のポインタに加え、前後どちらかの要素がわかっていなければならない。
・ポインタ操作にxor演算がはいるので通常の双方向リストと比べて遅くなる。
という特徴をもつ。面白いけど使い所がわからない・・・

前後どちらかのポインタがわからない限りは、リストの先頭要素か最終要素しか操作できない。
前後のどちらかの要素が判明しているなら、その分のメモリを使って双方向リスト使えよという話になるので、(外部から前後の要素が判明するようなパターンを除いて)要素単体単体へ操作可能なシーンは期待できない。

・リストを前向きにも後ろ向きにも辿りたい
・メモリをポインタ1個分でいいから削りたい
・追加と削除はリストの先頭あるいは最後尾の要素に発生する
・要素の走査はリストの先頭あるいは最後尾からしか発生しない
という要求のときぐらいにしか使えない?


リングバッファ その4

ロックフリーなリングバッファを作ってみた。失敗。
バグあり。
バッファ自体にサイズ情報と書き込み済みかどうかのフラグ仕込むとかそういうことやらないと難しいかも。

検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。