Unrolled linked list
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/04 14:29 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2011年4月) |
Unrolled linked listは連結リストの変種で、各ノードに格納する要素を複数個にしたものである。CPUキャッシュの利用効率を劇的に向上させるとともに、リストのメタデータ（参照など）によるメモリ消費のオーバーヘッドを削減できる。B木とも関連がある。
この例では"maxElements"は"4"である。
概要
典型的なUnrolled linked listの実装は以下のようになる。
record node {
node next // リストの次のノードへの参照
int numElements // このノード中の現在の要素数。最大maxElements個
array elements // 要素の配列。maxElements個の領域にnumElements個の要素が格納されている
}
各ノードはある一定の最大個数（maxElements個）まで要素を格納できる。maxElementsの大きさは、1つのノードが1から数個程度のキャッシュラインに乗るように設定する。リスト中の要素の位置は、ノードへの参照と配列中の位置のペアで識別される。上記の実装に、リストの一つ前のノードへの参照を追加して、双方向のUnrolled linked listとすることもできる。
新しい要素を挿入する際は、要素が配置されるべきノードを探した上で、elements配列に要素を挿入し、numElementsをインクリメントすればよい。配列がすでに一杯だった場合は、まず現在のノードの前か後ろのいずれかに新しいノードを挿入し、現在のノードの配列の内容の半分を新しいノードへ移動した上で、要素を配列へ追加する。
要素を削除する場合も同様で、削除されるべき要素が入っているノードを探し、elements配列から要素を削除し、numElementsをデクリメントする。numElementsがmaxElements÷2より小さくなった場合は、隣接ノードから現在のノードへ要素を移動させる。隣接ノードの要素もmaxElements÷2より少なかった場合は、要素を移動させてノードをひとつにまとめる。これにより、使用領域の無駄を省くことができる。
性能
Unrolled linked listの最大の利点は、使用領域を削減できることにある。たかだか1つのノードを除けば、それ以外の全てのノードは常に最低でも半分以上埋まっている状態になる。要素の挿入や削除がランダムに行われたとすると、各ノードは平均3/4まで埋まっている計算になる。
リストのパラメータを
* m =maxElements, 各elements配列の最大長 * v = 要素数や参照の保存によって発生する、ノードあたりのオーバーヘッド * s = 要素一つのサイズ
とすると、n個の要素を格納するために消費される領域のサイズは
「Unrolled linked list」の例文・使い方・用例・文例
- Unrolled linked listのページへのリンク
