JPH0554076A - メモリ内のデータサーチ及びデータ保持方法 - Google Patents
メモリ内のデータサーチ及びデータ保持方法Info
- Publication number
- JPH0554076A JPH0554076A JP4016400A JP1640092A JPH0554076A JP H0554076 A JPH0554076 A JP H0554076A JP 4016400 A JP4016400 A JP 4016400A JP 1640092 A JP1640092 A JP 1640092A JP H0554076 A JPH0554076 A JP H0554076A
- Authority
- JP
- Japan
- Prior art keywords
- list
- data elements
- data
- doubly linked
- array
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Memory System (AREA)
Abstract
(57)【要約】
【目的】 ミディアムサイズのデータ要素から成るリス
トをサーチ及び管理する効果的な方法を提供することを
目的としている。 【構成】 本発明は、二重連係リスト内に記憶されるメ
モリ内データ要素のサーチ及び保持方法に関するもので
ある。論理的に関連するアドレス構成要素アレイを用い
て、二重連係リスト内のデータ要素をアクセスする。二
重連係リストは、動的に保持されるリストセグメントに
分割され、全アクセス時間を低減させることができる。
トをサーチ及び管理する効果的な方法を提供することを
目的としている。 【構成】 本発明は、二重連係リスト内に記憶されるメ
モリ内データ要素のサーチ及び保持方法に関するもので
ある。論理的に関連するアドレス構成要素アレイを用い
て、二重連係リスト内のデータ要素をアクセスする。二
重連係リストは、動的に保持されるリストセグメントに
分割され、全アクセス時間を低減させることができる。
Description
【０００１】
【産業上の利用分野】本発明は、ディジタルコンピュー
タにおけるデータの記憶、特に中程度の量のデータを管
理及びサーチするための改良された方法に関するもので
ある。
タにおけるデータの記憶、特に中程度の量のデータを管
理及びサーチするための改良された方法に関するもので
ある。
【０００２】
【従来の技術】サーチ方法とは、変数ａを読み取り、ａ
をキー（key ）とするレコードを見いだそうとする方法
である。サーチ方法では、全記レコードをリターンする
ことができる。更に一般的にこの方法では、ポインタを
前記レコードにリターンすることができる。テーブル内
の特定変数をサーチできない場合もある。すなわち、キ
−としての前記変数を有するテーブル内にレコードが存
在しない場合がある。このような場合、サーチ方法で
は、特別なニル（nil ）レコード、又はニルポインタを
リターンすることができる。通常、サーチが不成功の場
合には、キーとしての変数を有する新たなレコードを追
加することが望ましい。このような方法を、サーチ及び
挿入方法と称する。成功したサーチを、しばしば検索と
称する。
をキー（key ）とするレコードを見いだそうとする方法
である。サーチ方法では、全記レコードをリターンする
ことができる。更に一般的にこの方法では、ポインタを
前記レコードにリターンすることができる。テーブル内
の特定変数をサーチできない場合もある。すなわち、キ
−としての前記変数を有するテーブル内にレコードが存
在しない場合がある。このような場合、サーチ方法で
は、特別なニル（nil ）レコード、又はニルポインタを
リターンすることができる。通常、サーチが不成功の場
合には、キーとしての変数を有する新たなレコードを追
加することが望ましい。このような方法を、サーチ及び
挿入方法と称する。成功したサーチを、しばしば検索と
称する。
【０００３】シーケンシャルサーチ法 最も簡単なサーチ方式がシーケンシャルサーチ方法であ
る。このサーチ方式は、アレイ又は連係リストとして編
成されたテーブルに適用することができる。シーケンシ
ャルサーチ法は、順番に各キーを試験する方法であり、
サーチ変数に適合する変数を見いだした際に、そのイン
デックス（そのレコードに対するポインタとして機能す
る）をリターンする。適合する変数が見いだされない場
合にはゼロをリターンする。
る。このサーチ方式は、アレイ又は連係リストとして編
成されたテーブルに適用することができる。シーケンシ
ャルサーチ法は、順番に各キーを試験する方法であり、
サーチ変数に適合する変数を見いだした際に、そのイン
デックス（そのレコードに対するポインタとして機能す
る）をリターンする。適合する変数が見いだされない場
合にはゼロをリターンする。
【０００４】シーケンシャルサーチの効率 一定サイズｎのテーブルをサーチできるように、挿入又
は削除がないものとすると、比較回数は、変数キーのレ
コードがテーブル内のどこに現れるかに依存している。
このレコードがテーブル内の最初のものである場合に
は、１回だけの比較が行われる。すなわち、レコードが
テーブル内の最後にある場合には、ｎ回の比較が必要で
ある。変数がテーブル内の任意の位置に等しい確率で現
れる場合には、成功したサーチでは（平均して）（ｎ＋
１）／２回の比較が行われ、不成功のサーチではｎ回の
比較が行われる。任意の場合において、比較回数Ｏ(n)
は、ｎの関数であり、テーブル又はリストのサイズを示
している。
は削除がないものとすると、比較回数は、変数キーのレ
コードがテーブル内のどこに現れるかに依存している。
このレコードがテーブル内の最初のものである場合に
は、１回だけの比較が行われる。すなわち、レコードが
テーブル内の最後にある場合には、ｎ回の比較が必要で
ある。変数がテーブル内の任意の位置に等しい確率で現
れる場合には、成功したサーチでは（平均して）（ｎ＋
１）／２回の比較が行われ、不成功のサーチではｎ回の
比較が行われる。任意の場合において、比較回数Ｏ(n)
は、ｎの関数であり、テーブル又はリストのサイズを示
している。
【０００５】整列したテーブルのサーチ工程 テーブルが、昇順又は降順のレコードキーで記憶されて
いる場合、サーチ工程の効率を改善することのできる技
術が幾つかある。特にテーブルサイズが固定されている
場合に改善することができる。変数キーがファイルに存
在しない場合に、非分類のファイルをサーチするよりも
分類されたファイルをサーチする方が有利である。非分
類ファイルの場合、この事実を検出するのにｎ回の比較
が必要である。分類されたファイルの場合、ファイル内
のキー範囲にわたって変数キーが一様に分散しているも
のと仮定すると、（平均して）n/2 回だけの比較が必要
となる。このことは、ファイル内で変数よりも大きなキ
ーを検出すると直ちに、このキーよりも昇順に分類され
ているキーから成るファイルに所定のキーが存在しない
ことを認識しているからである。
いる場合、サーチ工程の効率を改善することのできる技
術が幾つかある。特にテーブルサイズが固定されている
場合に改善することができる。変数キーがファイルに存
在しない場合に、非分類のファイルをサーチするよりも
分類されたファイルをサーチする方が有利である。非分
類ファイルの場合、この事実を検出するのにｎ回の比較
が必要である。分類されたファイルの場合、ファイル内
のキー範囲にわたって変数キーが一様に分散しているも
のと仮定すると、（平均して）n/2 回だけの比較が必要
となる。このことは、ファイル内で変数よりも大きなキ
ーを検出すると直ちに、このキーよりも昇順に分類され
ているキーから成るファイルに所定のキーが存在しない
ことを認識しているからである。
【０００６】バイナリサーチ 補助インデックス又はリストを使用しないシーケンシャ
ルリストの最も有効なサーチ方法はバイナリサーチであ
る。オブジェクトをある順番に配置している要素のアレ
イについて考える。アレイが要素を一つだけ有している
場合は簡単である。これ以外の場合には、サーチされる
アイテムをアレイ（又はリスト）の中間に位置するアイ
テムと比較する。これらが等しい場合にはサーチは成功
し、終了する。前記中間のアイテムがサーチされるアイ
テムよりも大きい場合、サーチプロセスはアレイの前半
で繰り返される（その理由は、アイテムがどこかに現れ
るとすれば、前半に現れるはずだからである）。前記中
間のアイテムがサーチされるアイテムよりも小さい場
合、サーチプロセスはアレイの後半で繰り返される。比
較が行われる度に、サーチされる要素数の半分がカット
される。大きなアレイの場合、各比較毎にサーチされる
要素数が１まで小さくなるという点において、この方法
はシーケンシャルサーチよりも有利である。バイナリサ
ーチでは、各比較毎に２のファクタで起こり得る対象数
が減少する。このため、キー比較の最大試行回数は、ほ
ぼlog （２）ｎである。
ルリストの最も有効なサーチ方法はバイナリサーチであ
る。オブジェクトをある順番に配置している要素のアレ
イについて考える。アレイが要素を一つだけ有している
場合は簡単である。これ以外の場合には、サーチされる
アイテムをアレイ（又はリスト）の中間に位置するアイ
テムと比較する。これらが等しい場合にはサーチは成功
し、終了する。前記中間のアイテムがサーチされるアイ
テムよりも大きい場合、サーチプロセスはアレイの前半
で繰り返される（その理由は、アイテムがどこかに現れ
るとすれば、前半に現れるはずだからである）。前記中
間のアイテムがサーチされるアイテムよりも小さい場
合、サーチプロセスはアレイの後半で繰り返される。比
較が行われる度に、サーチされる要素数の半分がカット
される。大きなアレイの場合、各比較毎にサーチされる
要素数が１まで小さくなるという点において、この方法
はシーケンシャルサーチよりも有利である。バイナリサ
ーチでは、各比較毎に２のファクタで起こり得る対象数
が減少する。このため、キー比較の最大試行回数は、ほ
ぼlog （２）ｎである。
【０００７】しかし、バイナリサーチ法は、リストがア
レイとして記憶されている場合にのみ使用することがで
きる。この理由は、バイナリサーチでは、アレイ要素の
インデックスが連続整数であるということを利用してい
るからである。このため従来より、多くの挿入又は削除
が行われアレイ構造が不適当である場合には、バイナリ
サーチが有効でないことが確認されている。 追加的な方法
レイとして記憶されている場合にのみ使用することがで
きる。この理由は、バイナリサーチでは、アレイ要素の
インデックスが連続整数であるということを利用してい
るからである。このため従来より、多くの挿入又は削除
が行われアレイ構造が不適当である場合には、バイナリ
サーチが有効でないことが確認されている。 追加的な方法
【０００８】要素のリストをサーチ及び管理する追加的
方法としては、３−２トリーサーチ法、オーダｍのＢ−
トリーサーチ法、平衡バイナリトリーサーチ法、及び
“ A. Tenenbaum ＆ M.Augenstein,Data Structures Us
ing Pascal（PrenticeーHall 1981 ）”などのカレッジ
レベルのデータ構造に関するテキストブックに通常記載
されている他の種々の方法がある。
方法としては、３−２トリーサーチ法、オーダｍのＢ−
トリーサーチ法、平衡バイナリトリーサーチ法、及び
“ A. Tenenbaum ＆ M.Augenstein,Data Structures Us
ing Pascal（PrenticeーHall 1981 ）”などのカレッジ
レベルのデータ構造に関するテキストブックに通常記載
されている他の種々の方法がある。
【０００９】３−２トリーとは、各ノードが２又は３個
のサン（son)を有し、１又は２個のキーを具えているも
のである。１個のノードが２個のサンを有している場合
には、１個のキーを具えている。左側のサブトリー内の
すべてのキーが、前記１個のキーよりも小さく、右側の
サブトリー内のすべてのキーが、前記１個のキーよりも
大きい。ノードが３個のサンを有している場合、２個の
キーを具えている。左側のサブトリー内のすべてのキー
が、前記２個のキー内の左側のキーよりも小さく、この
左側のキーは、中間のサブトリー内のすべてのキーより
も小さい。この中間のサブトリー内のすべてのキーは、
前記２個のキー内の右側のキーよりも小さく、この右側
のキーは、右側のサブトリー内のすべてのキーよりも小
さい。
のサン（son)を有し、１又は２個のキーを具えているも
のである。１個のノードが２個のサンを有している場合
には、１個のキーを具えている。左側のサブトリー内の
すべてのキーが、前記１個のキーよりも小さく、右側の
サブトリー内のすべてのキーが、前記１個のキーよりも
大きい。ノードが３個のサンを有している場合、２個の
キーを具えている。左側のサブトリー内のすべてのキー
が、前記２個のキー内の左側のキーよりも小さく、この
左側のキーは、中間のサブトリー内のすべてのキーより
も小さい。この中間のサブトリー内のすべてのキーは、
前記２個のキー内の右側のキーよりも小さく、この右側
のキーは、右側のサブトリー内のすべてのキーよりも小
さい。
【００１０】オーダｍのＢ−トリーは、３−２トリーを
一般化したものである。このようなトリーは、以下の特
徴を具備する一般的なトリーとして規定される。 １．各ノードは、多くてｍ−１個のキーを具えている。 ２．ルート（root）を除き、各ノードは少なくとも（ｍ
／２）−１個のキーを具えている。 ３．リーフ（leaf）でない限り、ルートは少なくとも２
個のサンを有している。 ４．すべてのリーフは同じレベルにある。 ５．ｎ個のキーを有するノンリーフノードは、ｎ＋１個
のサンを有している。
一般化したものである。このようなトリーは、以下の特
徴を具備する一般的なトリーとして規定される。 １．各ノードは、多くてｍ−１個のキーを具えている。 ２．ルート（root）を除き、各ノードは少なくとも（ｍ
／２）−１個のキーを具えている。 ３．リーフ（leaf）でない限り、ルートは少なくとも２
個のサンを有している。 ４．すべてのリーフは同じレベルにある。 ５．ｎ個のキーを有するノンリーフノードは、ｎ＋１個
のサンを有している。
【００１１】平衡バイナリトリーとは、各ノードにおけ
る２個のサブトリーの高さの差が、決して２個以上とな
らないバイナリトリーのことである。バイナリトリーの
ノードにおける平衡は、左側のサブトリーの高さから右
側のサブトリーの高さを引いたものとして規定される。
ノードの削除は、平衡バイナリトリー法の対象とされ
ず、他の技術を用いて行われなければならない。平衡バ
イナリトリーの詳しい取り扱いについては、上述した幾
つかのカレッジレベルのデータ構造に関するテキストブ
ックに記載されている。
る２個のサブトリーの高さの差が、決して２個以上とな
らないバイナリトリーのことである。バイナリトリーの
ノードにおける平衡は、左側のサブトリーの高さから右
側のサブトリーの高さを引いたものとして規定される。
ノードの削除は、平衡バイナリトリー法の対象とされ
ず、他の技術を用いて行われなければならない。平衡バ
イナリトリーの詳しい取り扱いについては、上述した幾
つかのカレッジレベルのデータ構造に関するテキストブ
ックに記載されている。
【００１２】２個の要因から生じる平衡バイナリトリー
のオーバーヘッドには、決定できない特徴がある。まず
第１に、トリーは実際には完全に平衡化されておらず、
サーチ時間が理論値のＯ（log （２）ｎ）よりも大きく
なってしまう。第２に、再平衡化は重要なことではある
が、どの程度の労力が必要かを示すことは困難である。
ノードはトリーの底部にリーフとして挿入され、ローテ
ーションと称する動作を適用し、平衡状態を再記憶する
ことができる。これらのローテーションは理解が困難で
あり、完全にコンピュート（compute −intensive ）で
あると思われる。ノード挿入に対して数字が送られる
間、ノード削除によって多くのローテーションが生じ、
トリーを充てんする。ノード削除による再平衡化に必要
なプロセスは、必要な時に呼び出されるバックグランド
タスクに集められていた。このため、非同期特性を再平
衡化に導入することとなり、かなり困難なこととなる
のオーバーヘッドには、決定できない特徴がある。まず
第１に、トリーは実際には完全に平衡化されておらず、
サーチ時間が理論値のＯ（log （２）ｎ）よりも大きく
なってしまう。第２に、再平衡化は重要なことではある
が、どの程度の労力が必要かを示すことは困難である。
ノードはトリーの底部にリーフとして挿入され、ローテ
ーションと称する動作を適用し、平衡状態を再記憶する
ことができる。これらのローテーションは理解が困難で
あり、完全にコンピュート（compute −intensive ）で
あると思われる。ノード挿入に対して数字が送られる
間、ノード削除によって多くのローテーションが生じ、
トリーを充てんする。ノード削除による再平衡化に必要
なプロセスは、必要な時に呼び出されるバックグランド
タスクに集められていた。このため、非同期特性を再平
衡化に導入することとなり、かなり困難なこととなる
【００１３】上記の保全動作によって新たなトリーのサ
ーチがかなり妨げられてしまうため、高速ルックアップ
の利益が失われることとなる。このため、平衡バイナリ
トリーのサーチ時間を、更に正確にＯ（log （２）ｎ）
＋（delta ）と記述する。ここで、（delta ）は、上記
の２個の要因、すなわちトリー不平衡及び再平衡化処理
によって生じる追加的なオーバーヘッドである。
ーチがかなり妨げられてしまうため、高速ルックアップ
の利益が失われることとなる。このため、平衡バイナリ
トリーのサーチ時間を、更に正確にＯ（log （２）ｎ）
＋（delta ）と記述する。ここで、（delta ）は、上記
の２個の要因、すなわちトリー不平衡及び再平衡化処理
によって生じる追加的なオーバーヘッドである。
【００１４】平衡バイナリトリー技術は、通常効率的な
方法であるが、より複雑な方法であり、トリーノードの
削除によるオーバーヘッドを更に計算しなければならな
い。例えば、キャッシュコントローラは、キャッシュイ
ンデックスエントリをキャッシュデータ構造に動的に追
加すると共に、動的に削除するように設計されている。
削除に必要な、この特別なオーバーヘッド（非決定的な
量の処理必要性）は、リアルタイムという制約を有する
記憶コントローラにおいてあまり良いことではない。
方法であるが、より複雑な方法であり、トリーノードの
削除によるオーバーヘッドを更に計算しなければならな
い。例えば、キャッシュコントローラは、キャッシュイ
ンデックスエントリをキャッシュデータ構造に動的に追
加すると共に、動的に削除するように設計されている。
削除に必要な、この特別なオーバーヘッド（非決定的な
量の処理必要性）は、リアルタイムという制約を有する
記憶コントローラにおいてあまり良いことではない。
【００１５】
【発明の概要】本発明は、ミディアムサイズのデータ要
素から成るリストをサーチ及び管理する効果的な方法を
提供することを目的としている。アレイは、メモリ内で
作成され、構成要素を具えていないように初期化され
る。二重連係リストを用いて、整列したデータ要素のグ
ループを構成する。データ要素総数の平方根の整数値を
用いた数学的関係を利用して、二重連係リストをリスト
セグメントにグループ化する。各リストセグメントのイ
ニシャルメンバのアドレス構成要素をアレイ内に配置す
る。データ要素数と、これに対応するアドレス構成要素
を有する対応リストセグメント数との関係を動的なもの
とし、データ要素の追加又は削除に応答してリストセグ
メントのグループが変化するようにしている。任意の１
データ要素を検索する場合に、順次にデータ要素リスト
をサーチするのに必要な工程数を低減し、リストセグメ
ントの第１構成要素で開始するようにし、サーチ時間を
最小化する。サーチの初期化工程の後に、アドレス構成
要素から成るアレイのバイナリサーチを行い、その後、
対応するリストセグメントの開始位置において二重連係
リストにエントリする。
素から成るリストをサーチ及び管理する効果的な方法を
提供することを目的としている。アレイは、メモリ内で
作成され、構成要素を具えていないように初期化され
る。二重連係リストを用いて、整列したデータ要素のグ
ループを構成する。データ要素総数の平方根の整数値を
用いた数学的関係を利用して、二重連係リストをリスト
セグメントにグループ化する。各リストセグメントのイ
ニシャルメンバのアドレス構成要素をアレイ内に配置す
る。データ要素数と、これに対応するアドレス構成要素
を有する対応リストセグメント数との関係を動的なもの
とし、データ要素の追加又は削除に応答してリストセグ
メントのグループが変化するようにしている。任意の１
データ要素を検索する場合に、順次にデータ要素リスト
をサーチするのに必要な工程数を低減し、リストセグメ
ントの第１構成要素で開始するようにし、サーチ時間を
最小化する。サーチの初期化工程の後に、アドレス構成
要素から成るアレイのバイナリサーチを行い、その後、
対応するリストセグメントの開始位置において二重連係
リストにエントリする。
【００１６】本発明の付加的な目的及び利点は、後続す
る説明に記載された通りであり、また後続する説明から
明らかである。本発明の目的及び利点は、特許請求の範
囲に記載されている構成によって実現される。
る説明に記載された通りであり、また後続する説明から
明らかである。本発明の目的及び利点は、特許請求の範
囲に記載されている構成によって実現される。
【００１７】本発明は、アレイ及び二重連係リストの特
徴を具えている。この二重連係リストは、アレイを有す
る増補された二重連係リストであり、本発明の技術を、
増補二重連係リスト、すなわちADL リストと称する。
徴を具えている。この二重連係リストは、アレイを有す
る増補された二重連係リストであり、本発明の技術を、
増補二重連係リスト、すなわちADL リストと称する。
【００１８】
【実施例】以下図面を参照して本発明を実施例につき説
明する。図１において、増補二重連係リスト（ADL （au
gmented doubly-linked ）リスト）のサーチ及び管理方
法は、アドレス構成要素のアレイ10を具え、複数のエン
トリポイント14を、データ要素の二重連係リスト12に供
給する。データ要素の二重連係リスト12を、複数のリス
トセグメント16に分割する。図３より以降に説明するよ
うに、所定数のデータ要素17をアドレス構成要素18に関
連づけることができる。更に、データ要素17の追加又は
消去の間に幾つかの動的事象が生じることを以下に示
す。二重連係リスト12内のデータ要素17の数が変化する
と、リストセグメント16の数も変化する場合がある。リ
ストセグメント16内のデータ要素数が変化すると、これ
に応答してアドレス構成要素18が変化し、これによっ
て、各リストセグメント16の第１データ要素をアクセス
するのに必要なエントリポイント14も変化する。
明する。図１において、増補二重連係リスト（ADL （au
gmented doubly-linked ）リスト）のサーチ及び管理方
法は、アドレス構成要素のアレイ10を具え、複数のエン
トリポイント14を、データ要素の二重連係リスト12に供
給する。データ要素の二重連係リスト12を、複数のリス
トセグメント16に分割する。図３より以降に説明するよ
うに、所定数のデータ要素17をアドレス構成要素18に関
連づけることができる。更に、データ要素17の追加又は
消去の間に幾つかの動的事象が生じることを以下に示
す。二重連係リスト12内のデータ要素17の数が変化する
と、リストセグメント16の数も変化する場合がある。リ
ストセグメント16内のデータ要素数が変化すると、これ
に応答してアドレス構成要素18が変化し、これによっ
て、各リストセグメント16の第１データ要素をアクセス
するのに必要なエントリポイント14も変化する。
【００１９】図１において、アレイ要素、すなわちアド
レス構成要素18のバイナリサーチを行う能力、及びバイ
ナリサーチの性能を利用する能力に応じてアレイを選択
する。連係リストを、最も簡単な種類の動的データ構造
とする。この連係リストは、構成要素をランダムに追加
又は消去することのできるリストを保持することに関す
る問題点を解決するものである。正方向ポインタととも
に逆方向ポインタを有しているリストを、二重連係リス
ト12と称する。このリストは、追加及び消去を効果的に
行うものであるが、データ要素の総数を変更するために
全リストを検索しなければならない場合には時間を浪費
することとなる。二重連係リスト12などの関連構造は、
通常これらと関連する幾つかのポインタを有している。
これらのポインタはプレイスマーカー（place marker）
として機能し、リストの開始、リストの終了、現在の位
置などとのコンタクトを保持する。
レス構成要素18のバイナリサーチを行う能力、及びバイ
ナリサーチの性能を利用する能力に応じてアレイを選択
する。連係リストを、最も簡単な種類の動的データ構造
とする。この連係リストは、構成要素をランダムに追加
又は消去することのできるリストを保持することに関す
る問題点を解決するものである。正方向ポインタととも
に逆方向ポインタを有しているリストを、二重連係リス
ト12と称する。このリストは、追加及び消去を効果的に
行うものであるが、データ要素の総数を変更するために
全リストを検索しなければならない場合には時間を浪費
することとなる。二重連係リスト12などの関連構造は、
通常これらと関連する幾つかのポインタを有している。
これらのポインタはプレイスマーカー（place marker）
として機能し、リストの開始、リストの終了、現在の位
置などとのコンタクトを保持する。
【００２０】図２は、典型的なADL リストのサーチを行
う方法を説明するためのフローチャートである。サーチ
を初期化し（20）、バイナリサーチ（22）がアドレス構
成要素18のアレイに適用される。所望のアドレスが発見
された場合には、サーチは二重連係リストの１リストセ
グメント16に絞られ、全二重連係リストをサーチするこ
となく、劇的に、全シークタイムを短くすることができ
る。適切なリストセグメント16を線形的に検索し（2
4）、所望のデータ要素17が存在するか否かを決定する
ことができる。所望のデータ要素が発見されない場合
（30）、新たなデータ要素をリストに追加する（32）。
所望のデータ要素が発見された場合（26）にはサーチを
終了する（28）。
う方法を説明するためのフローチャートである。サーチ
を初期化し（20）、バイナリサーチ（22）がアドレス構
成要素18のアレイに適用される。所望のアドレスが発見
された場合には、サーチは二重連係リストの１リストセ
グメント16に絞られ、全二重連係リストをサーチするこ
となく、劇的に、全シークタイムを短くすることができ
る。適切なリストセグメント16を線形的に検索し（2
4）、所望のデータ要素17が存在するか否かを決定する
ことができる。所望のデータ要素が発見されない場合
（30）、新たなデータ要素をリストに追加する（32）。
所望のデータ要素が発見された場合（26）にはサーチを
終了する（28）。
【００２１】図３は具体的に、アドレス構成要素のアレ
イ10内の２個のアドレス構成要素18及び18a と関連する
データ要素の二重連係リスト12内のデータ要素が、５個
の場合17,17a,17b,17c,17dを示すものである。一例とし
て、アドレス構成要素のアレイ10に対してバイナリサー
チを実行しアドレス構成要素18a を識別することによっ
て、データ要素17d のサーチを開始する。アドレス構成
要素18aは、エントリポイント14a をリストセグメント1
6a 、具体的にはデータ要素17b に供給する。リストセ
グメント16a の線形的な検索は、データ要素17b から開
始し、データ要素17c を介して、所望のリスト要素17d
に至るまで実行される。図３は、ADLリスト構造のこれ
までの変化のスナップショットを示す図である。データ
要素17の総数が動的に変化するに連れ、これに応答して
ADL リスト構造も変化する。すなわち、データ要素17の
総数が変化することによって、リストセグメント16の
数、所定のリストセグメント内のデータ要素の数が変化
するとともに、これに対応して整列したアレイ10内のア
ドレス構成要素18の数も変化する。これらの変化を以下
に説明する。
イ10内の２個のアドレス構成要素18及び18a と関連する
データ要素の二重連係リスト12内のデータ要素が、５個
の場合17,17a,17b,17c,17dを示すものである。一例とし
て、アドレス構成要素のアレイ10に対してバイナリサー
チを実行しアドレス構成要素18a を識別することによっ
て、データ要素17d のサーチを開始する。アドレス構成
要素18aは、エントリポイント14a をリストセグメント1
6a 、具体的にはデータ要素17b に供給する。リストセ
グメント16a の線形的な検索は、データ要素17b から開
始し、データ要素17c を介して、所望のリスト要素17d
に至るまで実行される。図３は、ADLリスト構造のこれ
までの変化のスナップショットを示す図である。データ
要素17の総数が動的に変化するに連れ、これに応答して
ADL リスト構造も変化する。すなわち、データ要素17の
総数が変化することによって、リストセグメント16の
数、所定のリストセグメント内のデータ要素の数が変化
するとともに、これに対応して整列したアレイ10内のア
ドレス構成要素18の数も変化する。これらの変化を以下
に説明する。
【００２２】上述したように、アレイのバイナリサーチ
速度を利用し、線形的な方法で検索する必要のある二重
連係リスト内のデータ要素数を最小にし、全体的なサー
チプロセスを促進するためには、二重連係リストをリス
トセグメント16内で管理することが望ましい。図３は、
各リストセグメントの第１データ要素のアドレス構成要
素のみを整列したアレイ10に配置することによって、ど
のようにしてアレイのバイナリサーチ、及び二重連係リ
ストのシーケンシャルサーチを最小化するかを示す図で
ある。更に具体的に述べると、図３において、整列した
アレイ10内のアドレス構成要素18は、エントリをリスト
セグメント16の第１データ要素17に供給する。また、整
列したアレイ10内のアドレス構成要素18a は、エントリ
をリストセグメント16a の第１データ要素17b に供給す
る。
速度を利用し、線形的な方法で検索する必要のある二重
連係リスト内のデータ要素数を最小にし、全体的なサー
チプロセスを促進するためには、二重連係リストをリス
トセグメント16内で管理することが望ましい。図３は、
各リストセグメントの第１データ要素のアドレス構成要
素のみを整列したアレイ10に配置することによって、ど
のようにしてアレイのバイナリサーチ、及び二重連係リ
ストのシーケンシャルサーチを最小化するかを示す図で
ある。更に具体的に述べると、図３において、整列した
アレイ10内のアドレス構成要素18は、エントリをリスト
セグメント16の第１データ要素17に供給する。また、整
列したアレイ10内のアドレス構成要素18a は、エントリ
をリストセグメント16a の第１データ要素17b に供給す
る。
【００２３】図４は、ADL リストが前記データ要素リス
トを管理し、任意の１データ要素のシークタイムを最小
にする方法を説明するフローチャートである。アドレス
構成要素のアレイを作成した後（40）、データ要素の二
重連係リストを作成し（42）、動的にデータ要素をリス
トに追加する（48）とともに、動的にデータ要素をリス
トから消去又は除去する必要がある（46）。データ要素
の追加（48）又は消去（46）を行う場合には、データ要
素の総数の整数値を決定する（44）。（44において計算
された）この整数値を、現在の二重連係リストセグメン
トの現行の値と比較し（編成しきい値のチェックと称す
る）（50）、新たな動的再編成を行う必要がある（54）
か否か（52）を決定する。理想的な平衡状態は、データ
要素の総数を平等にグループ化する場合に生じる。この
理想的な平衡状態は、データ要素の総数の平方根が有効
なアドレス構成要素の数と等しい場合にのみ生じる。す
なわち、データ要素の数（42）が、ほぼアドレス構成要
素数（40）の二乗に等しいということである。再編成が
必要でない場合（52）、このプロセスは終了する。新た
に動的再編成が必要な場合（54）、新たに編成された各
組の第１メンバのアドレス構成要素が決定される（5
6）。その後、各リストセグメントの各イニシャルメン
バの新アドレス構成要素が、アドレス構成要素のアレイ
に書き込まれる。すなわち、アレイが充てんされ（5
8）、プロセスが終了する。
トを管理し、任意の１データ要素のシークタイムを最小
にする方法を説明するフローチャートである。アドレス
構成要素のアレイを作成した後（40）、データ要素の二
重連係リストを作成し（42）、動的にデータ要素をリス
トに追加する（48）とともに、動的にデータ要素をリス
トから消去又は除去する必要がある（46）。データ要素
の追加（48）又は消去（46）を行う場合には、データ要
素の総数の整数値を決定する（44）。（44において計算
された）この整数値を、現在の二重連係リストセグメン
トの現行の値と比較し（編成しきい値のチェックと称す
る）（50）、新たな動的再編成を行う必要がある（54）
か否か（52）を決定する。理想的な平衡状態は、データ
要素の総数を平等にグループ化する場合に生じる。この
理想的な平衡状態は、データ要素の総数の平方根が有効
なアドレス構成要素の数と等しい場合にのみ生じる。す
なわち、データ要素の数（42）が、ほぼアドレス構成要
素数（40）の二乗に等しいということである。再編成が
必要でない場合（52）、このプロセスは終了する。新た
に動的再編成が必要な場合（54）、新たに編成された各
組の第１メンバのアドレス構成要素が決定される（5
6）。その後、各リストセグメントの各イニシャルメン
バの新アドレス構成要素が、アドレス構成要素のアレイ
に書き込まれる。すなわち、アレイが充てんされ（5
8）、プロセスが終了する。
【００２４】ADL リストの再編成と関連する処理時間が
あるために、１個の要素が追加又は消去される度毎のサ
ーチ及び管理方法は、二重連係リスト中のデータ要素数
が100 〜 500の場合に最適な性能を発揮することを確か
めた。結果的に、アレイサイズは 10 〜23個のアドレス
構成要素から成る。
あるために、１個の要素が追加又は消去される度毎のサ
ーチ及び管理方法は、二重連係リスト中のデータ要素数
が100 〜 500の場合に最適な性能を発揮することを確か
めた。結果的に、アレイサイズは 10 〜23個のアドレス
構成要素から成る。
【００２５】データ要素の追加によるADL リストのリス
トセグメントの動的グループ化への影響に関する例を、
図５，６，７，８，９及び10におけるADL リストの全体
的な構造変化にしたがって説明する。図５では、４個の
データ要素17,17a,17b,17cを、２個のリストセグメント
16及び16a にグループ化する。アドレス構成要素10のア
レイは、２個のアドレス構成要素18及び18a で充てんさ
れ、２個のリストエントリポイント14及び14a を、それ
ぞれ、リストセグメント16及び16a のイニシャルメンバ
であるリストデータ要素17及び17b に供給する。データ
要素数（この場合、データ要素数は４個）の平方根の整
数値は、２である。これは、所望のリストセグメント16
の数に対応しなければならない、アレイ要素の数、すな
わちアドレス構成要素18の数を提供するものである。リ
ストセグメント16は、データ要素17及び17a を有し、リ
ストセグメント16a は、データ要素17b 及び17c を有し
ている。
トセグメントの動的グループ化への影響に関する例を、
図５，６，７，８，９及び10におけるADL リストの全体
的な構造変化にしたがって説明する。図５では、４個の
データ要素17,17a,17b,17cを、２個のリストセグメント
16及び16a にグループ化する。アドレス構成要素10のア
レイは、２個のアドレス構成要素18及び18a で充てんさ
れ、２個のリストエントリポイント14及び14a を、それ
ぞれ、リストセグメント16及び16a のイニシャルメンバ
であるリストデータ要素17及び17b に供給する。データ
要素数（この場合、データ要素数は４個）の平方根の整
数値は、２である。これは、所望のリストセグメント16
の数に対応しなければならない、アレイ要素の数、すな
わちアドレス構成要素18の数を提供するものである。リ
ストセグメント16は、データ要素17及び17a を有し、リ
ストセグメント16a は、データ要素17b 及び17c を有し
ている。
【００２６】図６のデータ構造は、図５のデータ構造に
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図６は５個のデータ構造17,17a,17b,1
7c,17dを具え、これらを２個のリストセグメント16と16
a とにグループ化する。アドレス構成要素のアレイ10
は、２個のアドレス構成要素18及び18a で充てんされ、
２個のリストエントリポイント14及び14a を、それぞれ
リストセグメント 16 及び16a のイニシャルメンバであ
る、リストデータ要素17及び17b に供給する。データ要
素数（この場合、データ要素数は５）の平方根の整数値
は、依然として２である。この数字は、所望のリストセ
グメント数に対応させるのに必要なアレイ要素数を提供
するものである。リストセグメント16はデータ要素17及
び17a を有し、リストセグメント16a はデータ要素17b,
17c 及び17d を有しており、結果的にわずかに不平衡に
なる。
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図６は５個のデータ構造17,17a,17b,1
7c,17dを具え、これらを２個のリストセグメント16と16
a とにグループ化する。アドレス構成要素のアレイ10
は、２個のアドレス構成要素18及び18a で充てんされ、
２個のリストエントリポイント14及び14a を、それぞれ
リストセグメント 16 及び16a のイニシャルメンバであ
る、リストデータ要素17及び17b に供給する。データ要
素数（この場合、データ要素数は５）の平方根の整数値
は、依然として２である。この数字は、所望のリストセ
グメント数に対応させるのに必要なアレイ要素数を提供
するものである。リストセグメント16はデータ要素17及
び17a を有し、リストセグメント16a はデータ要素17b,
17c 及び17d を有しており、結果的にわずかに不平衡に
なる。
【００２７】図７のデータ構造は、図６のデータ構造に
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図７は、６個のデータ要素17,17a,17
b,17c,17d,17eを具え、これらを等しく２個のリストセ
グメント16と16a とにグループ化する。アドレス構成要
素のアレイ10は、２個のアドレス構成要素18及び18a で
充てんされ、２個のリストエントリポイント14及び14a
を、それぞれリストセグメント 16 及び16a のイニシャ
ルメンバである、リストデータ要素17及び17ｃに供給す
る。データ要素数（この場合、データ要素数は６）の平
方根の整数値は、依然として２である。この数字は、所
望のリストセグメント数に対応させるのに必要なアレイ
要素数を提供するものである。リストセグメント16はデ
ータ要素17,17a及び17b を有し、リストセグメント16a
はデータ要素17c,17d 及び17e を有している。
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図７は、６個のデータ要素17,17a,17
b,17c,17d,17eを具え、これらを等しく２個のリストセ
グメント16と16a とにグループ化する。アドレス構成要
素のアレイ10は、２個のアドレス構成要素18及び18a で
充てんされ、２個のリストエントリポイント14及び14a
を、それぞれリストセグメント 16 及び16a のイニシャ
ルメンバである、リストデータ要素17及び17ｃに供給す
る。データ要素数（この場合、データ要素数は６）の平
方根の整数値は、依然として２である。この数字は、所
望のリストセグメント数に対応させるのに必要なアレイ
要素数を提供するものである。リストセグメント16はデ
ータ要素17,17a及び17b を有し、リストセグメント16a
はデータ要素17c,17d 及び17e を有している。
【００２８】図８のデータ構造は、図７のデータ構造に
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図８は、７個のデータ要素17,17a,17
b,17c,17d,17e,17fを具え、これらを２個のリストセグ
メント16と16a とにグループ化しており、わずかに不平
衡となる。アドレス構成要素のアレイ10は、２個のアド
レス構成要素18及び18a で占有され、２個のリストエン
トリポイント14及び14aを、それぞれリストセグメント
16 及び16a のイニシャルメンバである、リストデータ
要素17及び17ｃに供給する。データ要素数（この場合、
データ要素数は７）の平方根の整数値は、依然として２
である。この数字は、所望のリストセグメント数に対応
させるのに必要なアレイ要素数を提供するものである。
リストセグメント16はデータ要素17,17a及び17b を有
し、リストセグメント16a はデータ要素17c,17d,17e 及
び17f を有している。
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図８は、７個のデータ要素17,17a,17
b,17c,17d,17e,17fを具え、これらを２個のリストセグ
メント16と16a とにグループ化しており、わずかに不平
衡となる。アドレス構成要素のアレイ10は、２個のアド
レス構成要素18及び18a で占有され、２個のリストエン
トリポイント14及び14aを、それぞれリストセグメント
16 及び16a のイニシャルメンバである、リストデータ
要素17及び17ｃに供給する。データ要素数（この場合、
データ要素数は７）の平方根の整数値は、依然として２
である。この数字は、所望のリストセグメント数に対応
させるのに必要なアレイ要素数を提供するものである。
リストセグメント16はデータ要素17,17a及び17b を有
し、リストセグメント16a はデータ要素17c,17d,17e 及
び17f を有している。
【００２９】図９のデータ構造は、図８のデータ構造に
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図９は、８個のデータ要素17,17a,17
b,17c,17d,17e,17f,17gを具え、これらを２個のリスト
セグメント16と16a とに等しくグループ化する。アドレ
ス構成要素のアレイ10は、２個のアドレス構成要素18及
び18a で充てんされ、２個のリストエントリポイント14
及び14a を、それぞれリストセグメント 16 及び16a の
イニシャルメンバである、リストデータ要素17及び17d
に供給する。データ要素数（この場合、データ要素数は
８）の平方根の整数値は、依然として２である。この数
字は、所望のリストセグメント数に対応させるのに必要
なアレイ要素数を提供するものである。リストセグメン
ト16はデータ要素17,17a,17b及び17c を有し、リストセ
グメント16a はデータ要素17d,17e,17f 及び17g を有し
ている。
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図９は、８個のデータ要素17,17a,17
b,17c,17d,17e,17f,17gを具え、これらを２個のリスト
セグメント16と16a とに等しくグループ化する。アドレ
ス構成要素のアレイ10は、２個のアドレス構成要素18及
び18a で充てんされ、２個のリストエントリポイント14
及び14a を、それぞれリストセグメント 16 及び16a の
イニシャルメンバである、リストデータ要素17及び17d
に供給する。データ要素数（この場合、データ要素数は
８）の平方根の整数値は、依然として２である。この数
字は、所望のリストセグメント数に対応させるのに必要
なアレイ要素数を提供するものである。リストセグメン
ト16はデータ要素17,17a,17b及び17c を有し、リストセ
グメント16a はデータ要素17d,17e,17f 及び17g を有し
ている。
【００３０】図10のデータ構造は、図９のデータ構造に
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図10は、９個のデータ要素17,17a,17
b,17c,17d,17e,17f,17g,17hを具え、ここではこれらを
３個のリストセグメント16,16a及び16b にグループ化す
る。アドレス構成要素のアレイ10は、３個のアドレス構
成要素18,18a及び18b で充てんされ、３個のリストエン
トリポイント14,14a及び14b を、それぞれリストセグメ
ント 16,16a 及び16b のイニシャルメンバである、リス
トデータ要素17,17c及び17f に供給する。データ要素数
（この場合、データ要素数は９）の平方根の整数値は、
ここでは３になる。この数字は、所望のリストセグメン
ト数に対応させるのに必要なアレイ要素数を提供するも
のである。リストセグメント16はデータ要素17,17a及び
17b を有し、リストセグメント16aはデータ要素17c,17d
及び17e を有し、リストセグメント16b は、データ要
素17f,17g 及び17h を有している。
１個の新たなデータ要素を追加したものである。更に具
体的に述べると、図10は、９個のデータ要素17,17a,17
b,17c,17d,17e,17f,17g,17hを具え、ここではこれらを
３個のリストセグメント16,16a及び16b にグループ化す
る。アドレス構成要素のアレイ10は、３個のアドレス構
成要素18,18a及び18b で充てんされ、３個のリストエン
トリポイント14,14a及び14b を、それぞれリストセグメ
ント 16,16a 及び16b のイニシャルメンバである、リス
トデータ要素17,17c及び17f に供給する。データ要素数
（この場合、データ要素数は９）の平方根の整数値は、
ここでは３になる。この数字は、所望のリストセグメン
ト数に対応させるのに必要なアレイ要素数を提供するも
のである。リストセグメント16はデータ要素17,17a及び
17b を有し、リストセグメント16aはデータ要素17c,17d
及び17e を有し、リストセグメント16b は、データ要
素17f,17g 及び17h を有している。
【００３１】例えば、図11は、整数値が５である次の段
階の全体的な再構成がどのようにして生じるかを示す図
であり、このことは、二重連係リスト12内のデータ要素
が25個である場合に生じる。更に具体的に述べると、図
11は、25個のデータ要素17,17a,17b,17c,17d,17e,17f,1
7g,17h,17i,17j,17k,17l,17m,17n,17o,17p,17q,,17r,17
s,17t,17u,17v,17w 及び17x を具え、これらを５個のリ
ストセグメント16,16a,16b,16c及び16d にグループ化す
る。アドレス構成要素のアレイ10は、５個のアドレス構
成要素18,18a,18b,18c及び18d で充てんされ、５個のリ
ストエントリポイント14,14a,14b,14c及び14d を、リス
トデータ要素17,17e,17j,17o及び17t に供給する。デー
タ要素数（この場合、データ要素数は25）の平方根の整
数値は、ここでは５になる。この数字は、所望のリスト
セグメント数に対応させるのに必要なアレイ要素数を提
供するものである。リストセグメント16はデータ要素1
7,17a,17b,17c 及び17d を有し、リストセグメント16a
はデータ要素17e,17f,17g,17h 及び17i を有し、リスト
セグメント16b はデータ要素17j,17k,17l,17m 及び17n
を有し、リストセグメント16c はデータ要素17o,17p,17
q,17r 及び17s を有し、リストセグメント16d はデータ
要素17t,17u,17v,17w及び17x を有している。
階の全体的な再構成がどのようにして生じるかを示す図
であり、このことは、二重連係リスト12内のデータ要素
が25個である場合に生じる。更に具体的に述べると、図
11は、25個のデータ要素17,17a,17b,17c,17d,17e,17f,1
7g,17h,17i,17j,17k,17l,17m,17n,17o,17p,17q,,17r,17
s,17t,17u,17v,17w 及び17x を具え、これらを５個のリ
ストセグメント16,16a,16b,16c及び16d にグループ化す
る。アドレス構成要素のアレイ10は、５個のアドレス構
成要素18,18a,18b,18c及び18d で充てんされ、５個のリ
ストエントリポイント14,14a,14b,14c及び14d を、リス
トデータ要素17,17e,17j,17o及び17t に供給する。デー
タ要素数（この場合、データ要素数は25）の平方根の整
数値は、ここでは５になる。この数字は、所望のリスト
セグメント数に対応させるのに必要なアレイ要素数を提
供するものである。リストセグメント16はデータ要素1
7,17a,17b,17c 及び17d を有し、リストセグメント16a
はデータ要素17e,17f,17g,17h 及び17i を有し、リスト
セグメント16b はデータ要素17j,17k,17l,17m 及び17n
を有し、リストセグメント16c はデータ要素17o,17p,17
q,17r 及び17s を有し、リストセグメント16d はデータ
要素17t,17u,17v,17w及び17x を有している。
【００３２】図12は、データ要素の総数（水平方向スケ
ール60）と、これに対応するリストセグメントの総数
（垂直方向スケール62）との間の動的な関係を示す図で
ある。更に具体的に述べると、ステップ型グラフ64は、
どのようにして二重連係リストへのデータ要素の追加又
は消去に応答してADL リスト構造が変化し、サーチ時間
が最小となるように構造を動的にグループ化するかを示
している。
ール60）と、これに対応するリストセグメントの総数
（垂直方向スケール62）との間の動的な関係を示す図で
ある。更に具体的に述べると、ステップ型グラフ64は、
どのようにして二重連係リストへのデータ要素の追加又
は消去に応答してADL リスト構造が変化し、サーチ時間
が最小となるように構造を動的にグループ化するかを示
している。
【００３３】コンピュータメモリに記憶されるデータ要
素を管理及びサーチするための、新規且つ有用な方法に
ついて説明した。具体的に述べると、簡単な数学的な関
係を用いて、データ要素の二重連係リストをより小さな
リストセグメントにグループ化する。アドレス構成要素
のアレイを各リストセグメントに直接アクセスするため
の手段として関連させることによって、各リストセグメ
ントへのエントリを供給する。まずアドレス構成要素ア
レイにバイナリサーチを行うとともに、その後、二重連
係リスト内のデータ要素のシーケンシャルサーチのみを
行うことによって、サーチ時間を最小にする。リストセ
グメント数、及びこれに対応するアレイ内のアドレス構
成要素数は、数学的にデータ要素の総数に関係している
とともに、リストにデータ要素を追加又はリストからデ
ータ要素を消去する際に動的に変化する。すなわち、前
記平方根の整数値が変化する際に、各個々のリストセグ
メント内のデータ要素数を再編成する。本発明はここに
開示されている実施例に限定されるものではなく、要旨
を変更しない範囲内で種々の変形又は変更が可能であ
る。
素を管理及びサーチするための、新規且つ有用な方法に
ついて説明した。具体的に述べると、簡単な数学的な関
係を用いて、データ要素の二重連係リストをより小さな
リストセグメントにグループ化する。アドレス構成要素
のアレイを各リストセグメントに直接アクセスするため
の手段として関連させることによって、各リストセグメ
ントへのエントリを供給する。まずアドレス構成要素ア
レイにバイナリサーチを行うとともに、その後、二重連
係リスト内のデータ要素のシーケンシャルサーチのみを
行うことによって、サーチ時間を最小にする。リストセ
グメント数、及びこれに対応するアレイ内のアドレス構
成要素数は、数学的にデータ要素の総数に関係している
とともに、リストにデータ要素を追加又はリストからデ
ータ要素を消去する際に動的に変化する。すなわち、前
記平方根の整数値が変化する際に、各個々のリストセグ
メント内のデータ要素数を再編成する。本発明はここに
開示されている実施例に限定されるものではなく、要旨
を変更しない範囲内で種々の変形又は変更が可能であ
る。
【図１】データ要素が４個の場合の、本発明によるADL
リストを示すブロック図である。
リストを示すブロック図である。
【図２】図１のADL リストにおける典型的なサーチを行
う方法を説明するためのフローチャートである。
う方法を説明するためのフローチャートである。
【図３】データ要素が５個の場合の、本発明によるADL
リストを示すブロック図である。
リストを示すブロック図である。
【図４】データ構成要素の二重連係リストを管理するた
めのADL リスト方法を説明するためのフローチャートで
ある。
めのADL リスト方法を説明するためのフローチャートで
ある。
【図５】データ要素が４個の場合の、本発明によるADL
リストを示すブロック図である。
リストを示すブロック図である。
【図６】データ要素が５個の場合の、本発明によるADL
リストを示すブロック図である。
リストを示すブロック図である。
【図７】データ要素が６個の場合の、本発明によるADL
リストを示すブロック図である。
リストを示すブロック図である。
【図８】データ要素が７個の場合の、本発明によるADL
リストを示すブロック図である。
リストを示すブロック図である。
【図９】データ要素が８個の場合の、本発明によるADL
リストを示すブロック図である。
リストを示すブロック図である。
【図１０】データ要素が９個の場合の、本発明によるAD
L リストを示すブロック図である。
L リストを示すブロック図である。
【図１１】データ要素が25個の場合の、本発明によるAD
L リストを示すブロック図である。
L リストを示すブロック図である。
【図１２】データ要素の総数と、これに対応するリスト
セグメント数との動的な関係を示す図である。
セグメント数との動的な関係を示す図である。
10 アドレス構成要素のアレイ 12 データ要素の二重連係リスト 14〜14d エントリポイント 16〜16d リストセグメント 17〜17x データ要素 18〜18d アドレス構成要素 20 サーチ初期化工程 22 アレイのサーチ工程 24 リストの線形的サーチ 26 所望のデータ要素が発見された場合 28 サーチの終了 30 所望のデータ要素が発見されない場合 32 新データ要素のリストへの追加工程 40 アレイの作成工程 42 リストの作成工程 44 平方根の整数値の計算工程 46 データ要素のリストからの消去工程 48 データ要素のリストへの追加工程 50 編成しきい値のチェック工程 52 再編成の必要がない場合 54 再編成の工程 56 第１要素のアドレス構成要素の決定工程 58 アレイを充てんさせる工程
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ドナルド イー マシユーズ アメリカ合衆国 コロラド州 80836 ウ ツドランド パーク サン バレイ ドラ イブ 1065 (72)発明者 デニス ユージン ホツフ アメリカ合衆国 コロラド州 80918 コ ロラド スプリングス タツカーマン ド ライブ 5634
Claims (6)
- 【請求項１】 メモリ内の整列したデータ要素のリスト
にデータを記憶するシステムにおける、メモリ内のデー
タをサーチ及び保持するための方法であって、該方法
が： ａ．アレイを作成する工程と； ｂ．整列したデータ要素から成る二重連係リストを作成
する工程と； ｃ．該二重連係リスト内の整列したデータ要素数を決定
する工程と； ｄ．整列したデータ要素から成る前記二重連係リストを
リストセグメントに動的にグループ化する工程と； ｅ．各リストセグメントの第１データ要素のアドレス構
成要素で前記アレイを充てんさせる工程と； ｆ．アドレス構成要素のアレイをサーチする工程と；リ
ストセグメントのエントリポイントから順次に二重連係
リストを走査する工程；とを有している、特定のデータ
値を有しているデータ要素の二重連係リストをサーチす
る工程と；ｇ．このようにしてサーチされた特定のデー
タ値を有しているデータ要素の二重連係リストを、識別
された二重連係リストメンバから検索する工程；とを具
えていることを特徴とするメモリ内データのサーチ及び
保持方法。 - 【請求項２】 前記二重連係リスト内の整列したデータ
要素を、リストセグメントに動的にグループ化する工程
が： ａ．前記二重連係リスト内のデータ要素の総数の平方根
を決定する工程と； ｂ．該データ要素総数の平方根の整数値を用い、リスト
セグメント数を識別する工程；とを具えていることを特
徴とする請求項１に記載のメモリ内データのサーチ及び
保持方法。 - 【請求項３】 メモリ内の整列したデータ要素のリスト
にデータを記憶するシステムにおける、メモリ内のデー
タをサーチ及び保持するための方法であって、該方法
が： ａ．アレイを作成する工程と； ｂ．整列したデータ要素から成る二重連係リストを作成
する工程と； ｃ．該二重連係リスト内の整列したデータ要素数を決定
する工程と； ｄ．前記二重連係リスト内の整列したデータ要素の総数
の平方根を決定する工程と； ｅ．該データ要素総数の平方根の整数値を用い、前記二
重連係リスト内のデータ要素から成る多数のリストセグ
メントを設定する工程と； ｆ．各リストセグメントの第１データ要素のアドレス構
成要素を識別する工程と； ｇ．該識別されたアドレス構成要素で前記アレイを充て
んし、整列したアレイを供給する工程と； ｈ．整列したデータ要素数の変化に応答して、リストセ
グメント内のデータ要素数をほぼ同じデータ要素数で、
各リストセグメントに動的に再編成し、アドレス構成要
素数の二乗がほぼデータ要素数となるようにする工程
と； ｉ．各再編成されたリストセグメントの第１データ要素
のアドレス構成要素を再び識別する工程と； ｊ．該再編成されたリストセグメントの再識別されたア
ドレス構成要素で前記アレイを充てんする工程と； ｋ．整列したアレイを供給する工程と； ｌ．特定のアドレス構成要素を有しているデータ要素を
識別するためのリクエストに応答して、再整列したアド
レスをサーチし、その関連リストセグメントを見いだす
工程と； ｍ．前記見いだされたリストセグメントを検索し、デー
タ要素を見いだす工程；とを具えていることを特徴とす
るメモリ内データのサーチ及び保持方法。 - 【請求項４】 前記整列したデータ要素数をリストセグ
メント内に動的に再編成する工程が： ａ．データ要素を前記二重連係リストに追加する工程
と； ｂ．拡張された二重連係リスト内の整列したデータ要素
数を決定する工程と； ｃ．整列したデータ要素総数の平方根の整数値を用い
て、前記拡張された二重連係リストの多数のグループ化
されたリストセグメントを識別する工程と； ｄ．新たに再グループ化された各セグメントの第１メン
バのアドレス構成要素を識別する工程と； ｅ．データ要素総数の平方根の整数値が増加した結果と
して、各リストセグメントの各第１メンバのアドレス構
成要素で前記アレイを再調整し、前記二重連係リスト内
のデータ要素のグループ化数を動的に変化させる工程；
とを具えていることを特徴とする請求項３に記載のメモ
リ内データのサーチ及び保持方法。 - 【請求項５】 前記リストセグメント内のデータ要素数
を動的に再編成する工程が： ａ．データ要素を二重連係リストから削除する工程と； ｂ．縮小された二重連係リスト内の整列したデータ要素
数を決定する工程と； ｃ．整列したデータ要素総数の平方根の整数値を用い、
縮小された二重連係リストの多数のグループ化されたリ
ストセグメントを識別する工程と； ｄ．新たに再グループ化された各セグメントの第１メン
バのアドレス構成要素を識別する工程と； ｅ．データ要素総数の平方根の整数値が減少した結果と
して、各リストセグメントの各第１メンバのアドレス構
成要素で前記アレイを再調整し、前記二重連係リスト内
の整列したデータ要素のグループ化数を動的に変化させ
る工程；とを具えていることを特徴とする請求項３に記
載のメモリ内データのサーチ及び保持方法。 - 【請求項６】 メモリ内の整列したデータ要素のリスト
にデータを記憶するシステムにおける、メモリ内のデー
タをサーチ及び保持するための方法であって、該方法
が： ａ．二重連係リスト内の整列したデータ要素数を決定す
る工程と； ｂ．前記二重連係リスト内の整列したデータ要素数をグ
ループ化及び再グループ化する工程と； ｃ．各リストセグメントの各イニシャルメンバのアドレ
ス構成要素を決定する工程と； ｄ．各リストセグメントの各イニシャルメンバのアドレ
ス構成要素から成る整列したアレイを作成する工程と； ｅ．複数の整列したデータ要素の拡張又は縮小に応答し
て、リストセグメント数を動的に調整する工程と； ｆ．複数のデータ要素の拡張又は縮小に応答して、前記
アレイを動的に調整する工程と； ｇ．適切なアドレス構成要素のアレイをサーチする工程
と； ｈ．適切なデータ要素の二重連係リストをサーチする工
程；とを具えていることを特徴とするメモリ内データの
サーチ及び保持方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/648,079 US5263160A (en) | 1991-01-31 | 1991-01-31 | Augmented doubly-linked list search and management method for a system having data stored in a list of data elements in memory |
| US07/648079 | 1991-01-31 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0554076A true JPH0554076A (ja) | 1993-03-05 |
Family
ID=24599354
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4016400A Pending JPH0554076A (ja) | 1991-01-31 | 1992-01-31 | メモリ内のデータサーチ及びデータ保持方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5263160A (ja) |
| EP (1) | EP0497543A3 (ja) |
| JP (1) | JPH0554076A (ja) |
| CA (1) | CA2060335A1 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001222469A (ja) * | 1999-11-05 | 2001-08-17 | Emc Corp | 変化するサービスレベルを提供するためのキャッシュのセグメント化 |
| WO2003077133A1 (fr) * | 2002-03-09 | 2003-09-18 | Sharp Kabushiki Kaisha | Technique de commande de memoire, dispositif a memoire, programme de commande et support d'enregistrement lisible |
Families Citing this family (52)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5560006A (en) * | 1991-05-15 | 1996-09-24 | Automated Technology Associates, Inc. | Entity-relation database |
| US5530957A (en) * | 1992-08-07 | 1996-06-25 | At&T Corp. | Storing trees in navigable form |
| US5410722A (en) * | 1993-01-21 | 1995-04-25 | Conner Peripherals, Inc. | Queue system for dynamically allocating and moving memory registers between a plurality of pseudo queues |
| JP3526595B2 (ja) * | 1993-10-29 | 2004-05-17 | 富士通株式会社 | 情報管理機構 |
| US5557786A (en) * | 1994-01-24 | 1996-09-17 | Advanced Computer Applications, Inc. | Threaded, height-balanced binary tree data structure |
| US5761501A (en) * | 1995-10-02 | 1998-06-02 | Digital Equipment Corporation | Stacked skip list data structures |
| US5659739A (en) * | 1995-10-02 | 1997-08-19 | Digital Equipment Corporation | Skip list data structure enhancements |
| US5671406A (en) * | 1995-10-18 | 1997-09-23 | Digital Equipment Corporation | Data structure enhancements for in-place sorting of a singly linked list |
| US5794243A (en) * | 1995-12-11 | 1998-08-11 | International Business Machines Corporation | Method and apparatus for executing a binary search in a data cache |
| US5787445A (en) * | 1996-03-07 | 1998-07-28 | Norris Communications Corporation | Operating system including improved file management for use in devices utilizing flash memory as main memory |
| GB2312079B (en) * | 1996-04-12 | 2000-11-15 | Sony Uk Ltd | Editing of recorded material |
| US6718550B1 (en) | 1996-06-26 | 2004-04-06 | Sun Microsystems, Inc. | Method and apparatus for improving the performance of object invocation |
| US8380796B2 (en) * | 1997-11-02 | 2013-02-19 | Amazon Technologies, Inc. | Social networking system |
| US6269369B1 (en) * | 1997-11-02 | 2001-07-31 | Amazon.Com Holdings, Inc. | Networked personal contact manager |
| US6438616B1 (en) | 1997-12-18 | 2002-08-20 | Sun Microsystems, Inc. | Method and apparatus for fast, local corba object references |
| US6516354B2 (en) | 1997-12-18 | 2003-02-04 | Sun Microsystems, Inc. | Method and apparatus for efficient representation of variable length identifiers in a distributed object system |
| US6016489A (en) * | 1997-12-18 | 2000-01-18 | Sun Microsystems, Inc. | Method and apparatus for constructing stable iterators in a shared data collection |
| US6249803B1 (en) | 1997-12-18 | 2001-06-19 | Sun Microsystems, Inc. | Method and apparatus for executing code during method invocation |
| US6205491B1 (en) | 1997-12-18 | 2001-03-20 | Sun Microsystems, Inc. | Method and apparatus for deferred throwing of exceptions in C++ |
| US6510460B1 (en) | 1997-12-18 | 2003-01-21 | Sun Microsystems, Inc. | Method and apparatus for enforcing locking invariants in multi-threaded systems |
| AU5910699A (en) * | 1998-09-18 | 2000-04-10 | Tacit Knowledge Systems | Method of constructing and displaying an entity profile constructed utilizing input from entities other than the owner |
| GB2345556B (en) * | 1999-01-06 | 2003-06-04 | Int Computers Ltd | List searching |
| US6493706B1 (en) * | 1999-10-26 | 2002-12-10 | Cisco Technology, Inc. | Arrangement for enhancing weighted element searches in dynamically balanced trees |
| US6457102B1 (en) * | 1999-11-05 | 2002-09-24 | Emc Corporation | Cache using multiple LRU's |
| JP2001216316A (ja) * | 2000-02-02 | 2001-08-10 | Nec Corp | 電子マニュアル検索システム、方法、及び記録媒体 |
| US7406547B2 (en) | 2000-08-09 | 2008-07-29 | Seagate Technology Llc | Sequential vectored buffer management |
| US6668251B1 (en) * | 2000-11-01 | 2003-12-23 | Tacit Knowledge Systems, Inc. | Rendering discriminator members from an initial set of result data |
| US7028023B2 (en) * | 2002-09-26 | 2006-04-11 | Lsi Logic Corporation | Linked list |
| US7627585B2 (en) * | 2002-12-02 | 2009-12-01 | Sap Ag | Data structure mapping and packaging |
| JPWO2005086003A1 (ja) * | 2004-03-08 | 2008-01-24 | アネックスシステムズ株式会社 | データベース・システム |
| US20060129452A1 (en) * | 2004-12-15 | 2006-06-15 | Sbc Knowledge Ventures, Lp | System and method for utilizing a multifaceted entity profile |
| US20060136995A1 (en) * | 2004-12-21 | 2006-06-22 | Chih-Wei Chen | Computer system cluster data access authorization checking method and system |
| US20060294096A1 (en) * | 2005-06-22 | 2006-12-28 | Eastman Kodak Company | Additive clustering of images into events using capture date-time information |
| CN100498740C (zh) * | 2007-09-11 | 2009-06-10 | 腾讯科技（深圳）有限公司 | 一种数据缓存处理方法、系统及数据缓存装置 |
| US7844637B2 (en) * | 2007-09-14 | 2010-11-30 | International Business Machines Corporation | Method for managing keyboard navigation within a tree control structure user interface component via a linked list |
| KR101673497B1 (ko) | 2009-01-05 | 2016-11-07 | 마벨 월드 트레이드 리미티드 | Ｍｉｍｏ 통신 시스템을 위한 프리코딩 코드북들 |
| US8675794B1 (en) * | 2009-10-13 | 2014-03-18 | Marvell International Ltd. | Efficient estimation of feedback for modulation and coding scheme (MCS) selection |
| US8917796B1 (en) | 2009-10-19 | 2014-12-23 | Marvell International Ltd. | Transmission-mode-aware rate matching in MIMO signal generation |
| WO2011055238A1 (en) | 2009-11-09 | 2011-05-12 | Marvell World Trade Ltd | Asymmetrical feedback for coordinated transmission systems |
| WO2011073876A2 (en) * | 2009-12-17 | 2011-06-23 | Marvell World Trade Ltd | Mimo feedback schemes for cross-polarized antennas |
| JP5258002B2 (ja) | 2010-02-10 | 2013-08-07 | マーベル ワールド トレード リミテッド | Ｍｉｍｏ通信システムにおける装置、移動通信端末、チップセット、およびその方法 |
| JP2012100254A (ja) | 2010-10-06 | 2012-05-24 | Marvell World Trade Ltd | Ｐｕｃｃｈフィードバックのためのコードブックサブサンプリング |
| US8954661B2 (en) * | 2010-11-02 | 2015-02-10 | Intel Corporation | Binary search pipeline |
| US9048970B1 (en) | 2011-01-14 | 2015-06-02 | Marvell International Ltd. | Feedback for cooperative multipoint transmission systems |
| US9124327B2 (en) | 2011-03-31 | 2015-09-01 | Marvell World Trade Ltd. | Channel feedback for cooperative multipoint transmission |
| US9020058B2 (en) | 2011-11-07 | 2015-04-28 | Marvell World Trade Ltd. | Precoding feedback for cross-polarized antennas based on signal-component magnitude difference |
| US8923427B2 (en) | 2011-11-07 | 2014-12-30 | Marvell World Trade Ltd. | Codebook sub-sampling for frequency-selective precoding feedback |
| WO2013068974A1 (en) | 2011-11-10 | 2013-05-16 | Marvell World Trade Ltd. | Differential cqi encoding for cooperative multipoint feedback |
| US9220087B1 (en) | 2011-12-08 | 2015-12-22 | Marvell International Ltd. | Dynamic point selection with combined PUCCH/PUSCH feedback |
| US8902842B1 (en) | 2012-01-11 | 2014-12-02 | Marvell International Ltd | Control signaling and resource mapping for coordinated transmission |
| US9143951B2 (en) | 2012-04-27 | 2015-09-22 | Marvell World Trade Ltd. | Method and system for coordinated multipoint (CoMP) communication between base-stations and mobile communication terminals |
| WO2014146024A1 (en) * | 2013-03-15 | 2014-09-18 | Datatempest, Llc | Databases and methods of storing, retrieving, and processing data |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3829837A (en) * | 1971-06-24 | 1974-08-13 | Honeywell Inf Systems | Controller for rotational storage device having linked information organization |
| US4679139A (en) * | 1984-05-01 | 1987-07-07 | Canevari Timber Co., Inc. | Method and system for determination of data record order based on keyfield values |
| US4887260A (en) * | 1987-02-17 | 1989-12-12 | Hewlett-Packard Company | X.25 Wide area network channel status display |
| JPH02178730A (ja) * | 1988-12-28 | 1990-07-11 | Toshiba Corp | 分割法を用いた内部ソート方式 |
| US5043885A (en) * | 1989-08-08 | 1991-08-27 | International Business Machines Corporation | Data cache using dynamic frequency based replacement and boundary criteria |
-
1991
- 1991-01-31 US US07/648,079 patent/US5263160A/en not_active Expired - Lifetime
-
1992
- 1992-01-28 EP EP9292300700A patent/EP0497543A3/en not_active Withdrawn
- 1992-01-30 CA CA002060335A patent/CA2060335A1/en not_active Abandoned
- 1992-01-31 JP JP4016400A patent/JPH0554076A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001222469A (ja) * | 1999-11-05 | 2001-08-17 | Emc Corp | 変化するサービスレベルを提供するためのキャッシュのセグメント化 |
| WO2003077133A1 (fr) * | 2002-03-09 | 2003-09-18 | Sharp Kabushiki Kaisha | Technique de commande de memoire, dispositif a memoire, programme de commande et support d'enregistrement lisible |
| US7308549B2 (en) | 2002-03-09 | 2007-12-11 | Sharp Kabushiki Kaisha | Memory control method, storage device, control program, and readable record medium |
Also Published As
| Publication number | Publication date |
|---|---|
| CA2060335A1 (en) | 1992-08-01 |
| US5263160A (en) | 1993-11-16 |
| EP0497543A3 (en) | 1994-09-14 |
| EP0497543A2 (en) | 1992-08-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0554076A (ja) | メモリ内のデータサーチ及びデータ保持方法 | |
| US5121493A (en) | Data sorting method | |
| US6473774B1 (en) | Method and apparatus for record addressing in partitioned files | |
| US5222235A (en) | Databases system for permitting concurrent indexing and reloading of data by early simulating the reload process to determine final locations of the data | |
| Litwin | Linear hashing: a new tool for file and table addressing. | |
| US5687361A (en) | System for managing and accessing a dynamically expanding computer database | |
| AU608872B2 (en) | Device for enabling concurrent access of indexed sequential data files | |
| US6516320B1 (en) | Tiered hashing for data access | |
| EP0851366B1 (en) | Modified indirect addressing for file system | |
| US5487164A (en) | Distribution-based replacement selection sorting system | |
| US6711562B1 (en) | Cache sensitive search (CSS) tree indexing system and method | |
| US4575798A (en) | External sorting using key value distribution and range formation | |
| US6427147B1 (en) | Deletion of ordered sets of keys in a compact O-complete tree | |
| JP3345628B2 (ja) | データ格納及び検索方法 | |
| Litwin et al. | A new method for fast data searches with keys | |
| Lo et al. | The design and implementation of seeded trees: An efficient method for spatial joins | |
| US20070094313A1 (en) | Architecture and method for efficient bulk loading of a PATRICIA trie | |
| US20110231404A1 (en) | File storage and retrieval method | |
| EP0563282B1 (en) | Paging process using extension tables | |
| Otoo | Linearizing the Directory Grovvth in Order Preserving Extendible Hashing | |
| US6076089A (en) | Computer system for retrieval of information | |
| JP2000181768A (ja) | デ―タ格納検索方式 | |
| EP0111689A2 (en) | Method of storing a B-tree type index file on rotating media devices | |
| Carter et al. | Performance Improvement in the Implementation of DBLEARN | |
| JPH07210563A (ja) | 索引処理方法 |