« 前のひとこと | トップページ | 次のひとこと »

aboutme:116612

大学で XOR リストというべきものを教えてもらったことがある。リスト構造を作るとき、単方向リスト(nextだけ)にするか双方向リスト(<next,prev>)にするかという問題があるが、next XOR prev という一つのポインタ領域だけ使うというリストである。

JRF 2009年12月30日 (水)

これは、現在位置 cur と現在位置の next と prev の「レジスタ」さえあれば、単方向リストのメモリ使用量で双方向リスト的挙動が実現できるというもの。

確かにメモリが十分にあれば双方向リストにすればいいし、計算量が十分にあれば単方向リストにすればいい。移動にポインタどうしの XOR を常に必要とするため、そのオーバーヘッドがかかるので計算スピード的に常に有利というわけでもない。

JRF 2009年12月30日 9826

XOR リストが有利になる条件って何だろう?リストの長さが「無限」で単方向リストにできず、ポインタ長も「無限」で双方向リストが「安全」でない。ただし、その長さが増えるスピードがどうにかするので、XOR リストは使える場合がある。…とかあるのだろうか?

JRF 2009年12月30日 1019

あまり関係はないと思うが↓を読んでふと思いだした。

《d.y.d.:slist LRUMap》
http://www.kmonos.net/wlog/104.html#_1044091215

JRF 2009年12月30日 7027

« 前のひとこと | トップページ | 次のひとこと »

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/93568/51548617

トラックバックのポリシー

他サイトなどからこの記事に自薦された関連記事(トラックバック)はまだありません。

このころのニュース