スポンサーサイト

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

双方向リスト/単方向リスト/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 を使えるかもしれない。
書いてて思ったが、そんなことは多分無い。
あとデバッガが使える環境だと、追いにくくなるということに難色を示されると思う。
スポンサーサイト

コメントの投稿

非公開コメント

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

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

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