大学で XOR…

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

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

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

JRF 2009年12月30日

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

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

《d.y.d.：slist LRUMap》
http://www.kmonos.net/wlog/104.html#_1044091215
JRF 2009年12月30日