Unrolled_linked_listとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Unrolled_linked_listの意味・解説 

Unrolled linked list

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/01/04 14:29 UTC 版)

Unrolled linked list連結リストの変種で、各ノードに格納する要素を複数個にしたものである。CPUキャッシュの利用効率を劇的に向上させるとともに、リストのメタデータ(参照など)によるメモリ消費のオーバーヘッドを削減できる。B木とも関連がある。

Unrolled linked list
この例では"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」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Unrolled_linked_list」の関連用語

Unrolled_linked_listのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Unrolled_linked_listのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのUnrolled linked list (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS