JPS60160444A - リスト処理方法 - Google Patents
リスト処理方法Info
- Publication number
- JPS60160444A JPS60160444A JP1516584A JP1516584A JPS60160444A JP S60160444 A JPS60160444 A JP S60160444A JP 1516584 A JP1516584 A JP 1516584A JP 1516584 A JP1516584 A JP 1516584A JP S60160444 A JPS60160444 A JP S60160444A
- Authority
- JP
- Japan
- Prior art keywords
- list
- elements
- associative memory
- processing method
- memory
- 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
Landscapes
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔発明の利用分野〕
本発明はリスト構造をしたデータのリスト処理方法に関
する。
する。
リストの構造は、例えば、「リスト処理とアーキテクチ
ャ」、情報処理学会、ＶＯＬ、２３、ＮＯ，８に示され
ている。姓名９年令、性別からなる第１図のリストは、
第２図の如き構造をもって表わすことができる。とれを
２進木で表現すると第３図のようになる。いま、第１図
のリストにおいて第２番目の要素の中の第３番目の要素
、即ち「男」をアクセスするとする。この時、従来方式
では、メモリ上におかれたセルを順次ａ、ｂ。
ャ」、情報処理学会、ＶＯＬ、２３、ＮＯ，８に示され
ている。姓名９年令、性別からなる第１図のリストは、
第２図の如き構造をもって表わすことができる。とれを
２進木で表現すると第３図のようになる。いま、第１図
のリストにおいて第２番目の要素の中の第３番目の要素
、即ち「男」をアクセスするとする。この時、従来方式
では、メモリ上におかれたセルを順次ａ、ｂ。
ｇ＋Ｊ’と辿って「男」に達する。このため、セルを５
回読み出さなければならず、要素の読み出しに階間を要
するという欠点がある。
回読み出さなければならず、要素の読み出しに階間を要
するという欠点がある。
本発明の目的は、上記欠点を解決するために、リスト要
素のアクセスを高速で行うリスト処理方法を提供するこ
とにある。
素のアクセスを高速で行うリスト処理方法を提供するこ
とにある。
上記目的を達成するためには、目的の要素を直接アクセ
スして、アクセスに要する時間を著しく減らす必要があ
る。通常のメモリの場合、アドレスによってアクセスさ
れるため、セルを辿っていかなければならないが、計算
機のなかでも特に高速性を要する処理部分では、目的の
要素に対応する数字又は文字列によって直接アクセスが
可能な連想メモリが使われている。
スして、アクセスに要する時間を著しく減らす必要があ
る。通常のメモリの場合、アドレスによってアクセスさ
れるため、セルを辿っていかなければならないが、計算
機のなかでも特に高速性を要する処理部分では、目的の
要素に対応する数字又は文字列によって直接アクセスが
可能な連想メモリが使われている。
記号処理等におけるリストの処理では、同一のリストを
繰シ返し操作することが頻繁に生ずるため、最初にリス
ト操作し、複数のセルを辿っである要素をアクセスした
ときに、その過程で経由した全セルの要素を連想メモリ
に格納し、次回以降に経路上の要素をアクセスする際、
これを連想メモリから直接アクセスすることを特徴とす
る。
繰シ返し操作することが頻繁に生ずるため、最初にリス
ト操作し、複数のセルを辿っである要素をアクセスした
ときに、その過程で経由した全セルの要素を連想メモリ
に格納し、次回以降に経路上の要素をアクセスする際、
これを連想メモリから直接アクセスすることを特徴とす
る。
以下、本発明の一実施例を図面を用いて詳細に説明する
。
。
第４図は、連想メモリを有する計算機の一実施例を示す
構成図である。記号処理においては、Ｌｉ ｓｐ等の言
語で記述されたプログラムが、第４図で示される計算機
によって実行される。第１図のリストは、第４図に示さ
れている主記憶（ＭＳ）１上に、第２図の構造を用いて
格納されている。
構成図である。記号処理においては、Ｌｉ ｓｐ等の言
語で記述されたプログラムが、第４図で示される計算機
によって実行される。第１図のリストは、第４図に示さ
れている主記憶（ＭＳ）１上に、第２図の構造を用いて
格納されている。
いま、例えば、第１図のリストを操作して、第２番目の
要素の中の第２番目の要素ｑを読み出すとする。第１図
のリストは、第３図の２進木で表わされ、２進木をらる
ノードから右に進む場合を１″、左に進む場合を＠０″
で表わし、この要素ｑ１即ち「３６オ」は、「１１＃→
１０＃→１１＃→″″０”」略して＠１０１０”の数字
列で表わすことができる。したがって、この要素ｑ「３
６オ」は、”１０１０″パターンをキーとして、第５図
のように連想メモ！Ｊ（ＡＳ）２上に表わすことができ
る。
要素の中の第２番目の要素ｑを読み出すとする。第１図
のリストは、第３図の２進木で表わされ、２進木をらる
ノードから右に進む場合を１″、左に進む場合を＠０″
で表わし、この要素ｑ１即ち「３６オ」は、「１１＃→
１０＃→１１＃→″″０”」略して＠１０１０”の数字
列で表わすことができる。したがって、この要素ｑ「３
６オ」は、”１０１０″パターンをキーとして、第５図
のように連想メモ！Ｊ（ＡＳ）２上に表わすことができ
る。
第１図のリストの第２番目の要素の中の第２番目の要素
ｑを、連想メモリに対して１０１０″のキーを用いてア
クセスし、このキーに対応するデータが登録されていな
かった場合には、従来方法と同様に、主記憶（ＭＳ）１
上に格納されている第２図のセルをａ −＋ ｂ −＋
ｇ −＋ ｈ −） ｑと辿って、目的の要素ｑアク
セスする。このように、主記憶上のセルを順次辿っであ
る要素を初めてアクセスした場合に、この要素を第３図
の２進木の経路を示す記号パターンをキーとして、連想
メモリに書き込む。（要素ｑ「３６オ」では、’１０１
０″をキーとして書き込む。） この辿シの際、経路上のセルから反対方向に進んで辿シ
つける要素ｐｒｓＪをも、その経路を数字列２０″１０
０″をキーとして同時に連想メモリに格納する。
ｑを、連想メモリに対して１０１０″のキーを用いてア
クセスし、このキーに対応するデータが登録されていな
かった場合には、従来方法と同様に、主記憶（ＭＳ）１
上に格納されている第２図のセルをａ −＋ ｂ −＋
ｇ −＋ ｈ −） ｑと辿って、目的の要素ｑアク
セスする。このように、主記憶上のセルを順次辿っであ
る要素を初めてアクセスした場合に、この要素を第３図
の２進木の経路を示す記号パターンをキーとして、連想
メモリに書き込む。（要素ｑ「３６オ」では、’１０１
０″をキーとして書き込む。） この辿シの際、経路上のセルから反対方向に進んで辿シ
つける要素ｐｒｓＪをも、その経路を数字列２０″１０
０″をキーとして同時に連想メモリに格納する。
その後、第１図のリストを再び操作して、第２番目の要
素の中の第１番目の要素ｐを読み出す場合には、従来方
法では再び主記憶（ＭＳ）１上のセルを辿らなければな
らないのに対し、第５図で水子ように、”１００″をキ
ーとして連想メモリよシ直ちに要素ｐｒＳＪを２９とし
て取シ出ずことができる。なお、要素ｑ「３６オ」とい
う要素が連想メモリよシ読み出せることは言うまでもな
い。
素の中の第１番目の要素ｐを読み出す場合には、従来方
法では再び主記憶（ＭＳ）１上のセルを辿らなければな
らないのに対し、第５図で水子ように、”１００″をキ
ーとして連想メモリよシ直ちに要素ｐｒＳＪを２９とし
て取シ出ずことができる。なお、要素ｑ「３６オ」とい
う要素が連想メモリよシ読み出せることは言うまでもな
い。
第１図のリストの第２番目の要素の中の第２番目の要素
ｑ「３６オ」を読み出した際に、第６図に示すように、
経路からはずれたノードＣおよびノードｉへのポインタ
をも連想メモリに格納し、経路上にない要素へのアクセ
スに対して経路上の同一部分を辿る必要をなくして、読
み出し時間を短縮することができる。
ｑ「３６オ」を読み出した際に、第６図に示すように、
経路からはずれたノードＣおよびノードｉへのポインタ
をも連想メモリに格納し、経路上にない要素へのアクセ
スに対して経路上の同一部分を辿る必要をなくして、読
み出し時間を短縮することができる。
いま、例えば、数字列３ｏ”１１００”に対応する要素
５ｒＫＪをアクセスする場合を示す。数字列３０ ”１
１００’ を、”１”、”１０１”、’１００”。
５ｒＫＪをアクセスする場合を示す。数字列３０ ”１
１００’ を、”１”、”１０１”、’１００”。
”１０１０″ と左から比較して、最長の一致が得られ
た＃１＃に対応する、セルＣへのポインタ３９が、連想
メモリ（ＡＳ）２から出力される。これを得て、セルＣ
から、０″→″０“と辿って要素ｒＫＪに達することが
できる。
た＃１＃に対応する、セルＣへのポインタ３９が、連想
メモリ（ＡＳ）２から出力される。これを得て、セルＣ
から、０″→″０“と辿って要素ｒＫＪに達することが
できる。
本発明によれば、一度アクセスした要素への経路上の全
要素と、経路からはずれたセルへのポインタが連想メモ
リに格納されているため、同一リストの要素の再読み出
しに対して、その処理時間を短縮するという効果がある
。例えば、ｎ個の要素からなるリストの最終リストを読
み出して、全要素を連想メモリに格納し、その後全要素
を読み出したとすると、全処理時間は、１セルの読み出
っていた時間（２ｎ−１）ｔに短縮される。その
要素と、経路からはずれたセルへのポインタが連想メモ
リに格納されているため、同一リストの要素の再読み出
しに対して、その処理時間を短縮するという効果がある
。例えば、ｎ個の要素からなるリストの最終リストを読
み出して、全要素を連想メモリに格納し、その後全要素
を読み出したとすると、全処理時間は、１セルの読み出
っていた時間（２ｎ−１）ｔに短縮される。その
第１図はリストの一例ケ示す図、第２図は第１図のリス
ト構造を示す図、第３図は第２図のリストを２進水で表
現した図、第４図は連想メモリを有する計算機の一実施
例を示す構成図、第５図。 第６図は連想メモリにおけるキーと出力結果の関係を説
明するだめの図である。 Ｂ −−Ａ・・・セル、ｍｚｕ・・・要素、Ｎ工Ｌ・・
・空リスト、１・・・主記憶（ＭＳ）、２・・・連想メ
モ！Ｊ（Ａｓ）、３・・・演算処理装置（ＢＰｕ）、４
・・・チャネル制御（ＣＩ−Ｉ Ｃ） 、訃・・チャネ
ル（ＣＨ）、６・・・入出力装ｆｔ（Ｉｌｏ）、７・・
・コンソールサービスグロセ第 １ 図 （丁 ４１才 男）（５３６オ男）（Ｋｌ’ｉ才なり￥
５３図 第１頁の続き ＠発明者岩崎 正量 ＠発明者井門 徳安 国分寺市東恋ケ窪１丁目２８幡地 株式会社日立製作所
中央研究所内 国分寺市東恋ケ窪１丁目２８幡地 株式会社日立製作所
中央研究所内
ト構造を示す図、第３図は第２図のリストを２進水で表
現した図、第４図は連想メモリを有する計算機の一実施
例を示す構成図、第５図。 第６図は連想メモリにおけるキーと出力結果の関係を説
明するだめの図である。 Ｂ −−Ａ・・・セル、ｍｚｕ・・・要素、Ｎ工Ｌ・・
・空リスト、１・・・主記憶（ＭＳ）、２・・・連想メ
モ！Ｊ（Ａｓ）、３・・・演算処理装置（ＢＰｕ）、４
・・・チャネル制御（ＣＩ−Ｉ Ｃ） 、訃・・チャネ
ル（ＣＨ）、６・・・入出力装ｆｔ（Ｉｌｏ）、７・・
・コンソールサービスグロセ第 １ 図 （丁 ４１才 男）（５３６オ男）（Ｋｌ’ｉ才なり￥
５３図 第１頁の続き ＠発明者岩崎 正量 ＠発明者井門 徳安 国分寺市東恋ケ窪１丁目２８幡地 株式会社日立製作所
中央研究所内 国分寺市東恋ケ窪１丁目２８幡地 株式会社日立製作所
中央研究所内
Claims (1)
- １．２進水上の分岐構造を表わす記号列によってリスト
の要素を読み出すリスト処理方法において、リストのめ
る要素の最初のアクセス時に、該要素に到る経路上の全
要素を連想メモリに格納し、リストの要素の読み出しに
際して、該要素に到る２進木上の分岐構造を表わす記号
列を、既に連想メモリ上に格納されている要素に対する
２進木上の分岐構造と比較し、最初に不一致の見られた
ノードからリストの辿シを開始することを特徴とするリ
スト処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1516584A JPS60160444A (ja) | 1984-02-01 | 1984-02-01 | リスト処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1516584A JPS60160444A (ja) | 1984-02-01 | 1984-02-01 | リスト処理方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS60160444A true JPS60160444A (ja) | 1985-08-22 |
Family
ID=11881183
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1516584A Pending JPS60160444A (ja) | 1984-02-01 | 1984-02-01 | リスト処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS60160444A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6361335A (ja) * | 1986-09-01 | 1988-03-17 | Matsushita Electric Ind Co Ltd | デ−タ処理装置 |
| JPS6365523A (ja) * | 1986-09-05 | 1988-03-24 | Matsushita Electric Ind Co Ltd | デ−タ処理装置 |
-
1984
- 1984-02-01 JP JP1516584A patent/JPS60160444A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6361335A (ja) * | 1986-09-01 | 1988-03-17 | Matsushita Electric Ind Co Ltd | デ−タ処理装置 |
| JPS6365523A (ja) * | 1986-09-05 | 1988-03-24 | Matsushita Electric Ind Co Ltd | デ−タ処理装置 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5519840A (en) | Method for implementing approximate data structures using operations on machine words | |
| US7231383B2 (en) | Search engine for large-width data | |
| EP0069525A1 (en) | Data processing system | |
| JPS61210477A (ja) | ベクトル型連想メモリシステム | |
| US5379407A (en) | Error handling in a state-free system | |
| JPS60160444A (ja) | リスト処理方法 | |
| KR890002772A (ko) | 논리형 언어의 데이타 처리 시스템 | |
| Kollias | An estimate of seek time for batched searching of random or index sequential structured files | |
| JPS6049931B2 (ja) | 情報検索方式 | |
| JPS59146339A (ja) | 情報検索方式 | |
| Wilkes | Associative tabular data structures | |
| SU1206810A1 (ru) | Устройство дл поиска информации | |
| JPS59144949A (ja) | 検索装置 | |
| JPH0283640A (ja) | データベース更新方法 | |
| JPS6214919B2 (ja) | ||
| JPS61177700A (ja) | 複合連想メモリ | |
| JPH0333978A (ja) | ファイルシステムの検索装置 | |
| JPS63223871A (ja) | 辞書作成システム | |
| JPS62217495A (ja) | 連想記憶装置 | |
| EP1141951A2 (en) | A digital memory structure and device, and methods for the management thereof | |
| JPH03139746A (ja) | 主記憶装置 | |
| JPS63118958A (ja) | 索引フアイル記憶装置 | |
| Fan | A study of searching and sorting methods using binary trees | |
| JPH04350741A (ja) | 索引順編成ファイルのアクセス高速化方法 | |
| JPS589452B2 (ja) | フア−ムウエアホウシキ |