【04】チェーンテーブル
4783 ワード
【04】チェーンテーブル 1. チェーン時計とは? 2. なぜチェーン時計を使うのですか?すなわち、チェーンテーブルの特徴 3.1単鎖表 3.2循環チェーンテーブル 3.3双方向チェーンテーブル 3.4双方向循環チェーンテーブル 4. 配列とチェーンテーブルのどちらを選択しますか? 5. LRUバッファ淘汰ポリシーをチェーンテーブルと配列で別々に実装するにはどうすればいいですか? 6「ある文字列が水仙文字列であるかどうかを判断する」を単一チェーンテーブルでどのように実現しますか?(例えば上海の水道水は海上から) 7設計思想 8. 参考資料 9. 宣言 1.チェーン時計とは?は配列と同様にチェーンテーブルも線形テーブルである. メモリ構造から見ると、チェーンテーブルのメモリ構造は不連続なメモリ空間であり、ばらばらなメモリブロックのセットを直列に接続してデータ記憶を行うデータ構造である. チェーンテーブルの各メモリブロックは、ノードノードノードノードと呼ばれる.ノードは、データの格納に加えて、チェーン上の次のノードのアドレス、すなわち後続ポインタnextを記録する必要がある.
2.チェーンテーブルを使用する理由すなわちチェーンテーブルの特徴データ効率の高いO(1)レベルを挿入、削除します(ポインタの方向を変更するだけでいい)、ランダムアクセス効率の低いO(n)レベル(チェーンヘッダからチェーンテールまで遍歴する必要があります). は配列に比べてメモリ領域の消費量が大きい.データを格納するノードごとに後続ポインタを格納する余分な空間が必要であるためである.##3.共通チェーンテーブル:単一チェーンテーブル、循環チェーンテーブル及び双方向チェーンテーブル 3.1単鎖表
1)各ノードには1つのポインタ,すなわち後続のポインタしか含まれていない.2)単一チェーンテーブルには2つの特殊なノード,すなわちヘッダノードとテールノードがある.どうして特殊なの?チェーンテーブル全体をヘッダノードアドレスで表し、テールノードの後続ポインタは空のアドレスnullを指す.3)性能特徴:ノードの挿入と削除の時間的複雑度はO(1),検索の時間的複雑度はO(n)である.
3.2循環チェーンテーブル
1)末尾ノードの後続ポインタが先頭ノードを指すアドレスを除いては,単一チェーンテーブルと一致する.2)ジョセフ問題などの循環特性のあるデータを格納するのに適している.
3.3双方向チェーンテーブル
1)ノードは,データの格納に加えて,2つのポインタがそれぞれ前のノードアドレス(前駆ポインタprev)と次のノードアドレス(後続ポインタnext)を指す.2)先頭ノードの前駆ポインタprevと末尾ノードの後続ポインタはいずれも空のアドレスを指す.3)性能特徴:単一チェーンテーブルと比べて、同じデータを保存し、より多くのストレージスペースを消費する.単一チェーンテーブルよりも挿入、削除操作の効率が高いO(1)レベル.削除操作を例にとると、削除操作は2つのケースに分けられます.所与のデータ値は、対応ノード を削除する.所与のノードアドレス削除ノード.前者の場合、単一チェーンテーブルと双方向チェーンテーブルは、対応するノードを見つけて削除するために最初から最後まで巡回する必要があり、時間的複雑度はO(n)である.第2の場合、削除操作を行うには前駆ノードを見つける必要があり、単一チェーンテーブルはp->next=qまで遍歴し、時間複雑度はO(n)であり、双方向チェーンテーブルは直接前駆ノードを見つけることができ、時間複雑度はO(1)である.1つの順序付きチェーンテーブルの場合、双方向チェーンテーブルの値別クエリー効率は、単一チェーンテーブルよりも高くなります.前回検索した位置pを記録することができるため、検索する値とpのサイズの関係によって、前に検索するか後に検索するかを決定するので、平均半分のデータを検索するだけです.
3.4双方向循環チェーン表
先頭ノードの前駆ポインタは末尾ノードを指し,末尾ノードの後続ポインタは先頭ノードを指す.
4.配列とチェーンテーブルのどちらを選択しますか?挿入、削除およびランダムアクセスの時間複雑度配列:挿入、削除の時間複雑度はO(n)、ランダムアクセスの時間複雑度はO(1)である.チェーンテーブル:挿入・削除の時間的複雑度はO(1),ランダムアクセスの時間的複雑端はO(n)である. 配列欠点1)100 Mなどのメモリ領域が大きいが、メモリ領域に100 Mの連続空間がない場合、メモリ使用可能領域が100 Mを超えるにもかかわらず、申請に失敗する.2)サイズが固定されており、ストレージスペースが不足している場合は拡張が必要であり、いったん拡張するとデータのコピーが必要になるため、非常に時間がかかる. チェーンテーブルの欠点1)ポインタ情報を追加的に格納する必要があるため、メモリ領域の消費量がより大きい.2)チェーンテーブルの頻繁な挿入と削除操作により,頻繁なメモリ申請と解放が起こり,メモリフラグメントが発生しやすく,Java言語であれば頻繁なGC(自動ゴミ回収器)操作も発生する可能性がある. はどのように選択しますか?配列は簡単で使いやすく、実装には連続したメモリ空間を使用し、CPUのバッファメカニズムで配列中のデータをプリフェッチできるため、アクセス効率が高く、チェーンテーブルはメモリに連続して格納されていないため、CPUキャッシュに友好的ではなく、プリフェッチができない.コードがメモリの使用に非常に厳しい場合は、配列が適しています.
5.LRUバッファ淘汰ポリシーをチェーンテーブルと配列で別々に実装する方法
1)キャッシュとは?キャッシュはデータの読み取り性能を向上させる技術であり、ハードウェア設計、ソフトウェア開発において一般的なCPUキャッシュ、データベースキャッシュ、ブラウザキャッシュなど、広くない応用がある.2)キャッシュを使用する理由すなわち、キャッシュの特徴的なキャッシュのサイズは限られており、キャッシュが満タンになった場合、どのデータがクリーンアップされ、どのデータが保持されるべきか.キャッシュ・トーナメント・ポリシーが必要です.3)キャッシュ・トーナメント・ポリシーとは?キャッシュが満タンになったときにデータをクリーンアップする優先順位を指す.4)どのようなキャッシュ・トーナメント・ポリシーがありますか.一般的な3つには、先進先出しポリシーFIFO(First In,First Out)、最小使用ポリシーLFU(Least Frenquently Used)、最近最小使用ポリシーLRU(Least Recently Used)が含まれる.5)チェーンテーブル実現LRUキャッシュ淘汰戦略アクセスしたデータがキャッシュしたチェーンテーブルに保存されていない場合、直接チェーンテーブルテーブルヘッダにデータを挿入し、時間複雑度はO(1)である.アクセスしたデータが格納されたチェーンテーブルに存在する場合,そのデータに対応するノードをチェーンテーブルヘッダに挿入し,時間複雑度はO(n)とする.キャッシュがいっぱいになると、チェーンテーブルの末尾のデータからクリーンアップが開始され、時間的複雑度はO(1)である.6)配列実現LRUキャッシュ淘汰戦略方式1:最初の位置は最新のアクセスデータを保存し、最後の位置は優先的に削除アクセスしたデータがキャッシュの配列に存在しない場合、直接データを配列の最初の要素の位置に挿入し、この時配列のすべての要素は1つの位置を後方に移動し、時間の複雑度はO(n)である.アクセスしたデータがキャッシュされた配列に存在する場合、データが検索され、配列の最初の位置に挿入されます.この場合、配列要素も移動する必要があります.時間の複雑さはO(n)です.キャッシュがいっぱいになると,末尾のデータは消去され,時間的複雑度はO(1)となる.方式2:最初の位置は優先的にクリーンアップし、最後の位置は最新のアクセスデータを保存し、アクセスしたデータがキャッシュの配列に存在しない場合、直接データを配列に追加して現在最もある要素として時間の複雑度はO(1)である.アクセスしたデータがキャッシュされた配列に存在する場合、データが検索され、現在の配列の最後の要素の位置に挿入されます.この場合、配列要素も移動する必要があります.時間の複雑さはO(n)です.キャッシュがいっぱいになると、配列の最初の位置の要素がクリーンアップされ、残りの配列要素は全体的に1ビット前に移動する必要があり、時間の複雑さはO(n)である.(最適化:一度に一定数をクリーンアップすることで、クリーンアップ回数を低減し、パフォーマンスを向上させることができます.)
6単一チェーンテーブルで「ある文字列が水仙文字列であるかどうかを判断する」にはどうすればいいですか?(例えば上海の水道水は海上から)
方法1:1)前提:文字列が単一文字で単一チェーンテーブルに格納される.2)チェーンテーブルの文字を別のチェーンテーブルに逆順序で格納する.3)2つのチェーンテーブルを同期して巡回し,対応する文字が等しいか否かを比較し,等しい場合は水仙文字列であり,そうでない場合はそうではない.方法2:速慢指針法は回文列の最も重要なのは対称であるため、最も重要な問題はその中心を見つけて、速針で一歩ずつ2格歩いて、彼がチェーン時計の末端に着いたとき、遅針はちょうど中心に着いて、遅針は来たこの道でまた1つのことをして、彼は歩いたノードを逆方向にしました.中心点に新しいポインタを開いて戻るが、遅いポインタは前進し続ける.遅いポインタがチェーンテーブル全体を掃くと、これが回文列であると判断できる.そうしないと、早めに退出する.総じて時間複雑度は遅いポインタで遍歴するとO(n)であり、空間複雑度は3つの追加の補助しか開かないため、o(1)である.
7設計思想
時空置換思想:「空間で時間を変える」と「時間で空間を変える」メモリ空間が十分な場合、コードの実行速度をさらに追求すれば、空間の複雑度が比較的高く、時間の複雑度が比較的低いアルゴリズムとデータの構造を選択することができ、キャッシュは空間の時間を変える例である.メモリが不足している場合、コードが携帯電話や単片機に走っている場合は、逆に時間をかけて空間を変える考えが必要です.
8.参考資料王争先生は極客時間のコラム「データ構造とアルゴリズムの美しさ」 コラムのすべてのコメント 9.宣言
***本文はただ学習のために使用して、彼のために使用しないでください、例えば権益を侵害して、私に連絡して、すぐに削除してください.
2.チェーンテーブルを使用する理由すなわちチェーンテーブルの特徴
1)各ノードには1つのポインタ,すなわち後続のポインタしか含まれていない.2)単一チェーンテーブルには2つの特殊なノード,すなわちヘッダノードとテールノードがある.どうして特殊なの?チェーンテーブル全体をヘッダノードアドレスで表し、テールノードの後続ポインタは空のアドレスnullを指す.3)性能特徴:ノードの挿入と削除の時間的複雑度はO(1),検索の時間的複雑度はO(n)である.
3.2循環チェーンテーブル
1)末尾ノードの後続ポインタが先頭ノードを指すアドレスを除いては,単一チェーンテーブルと一致する.2)ジョセフ問題などの循環特性のあるデータを格納するのに適している.
3.3双方向チェーンテーブル
1)ノードは,データの格納に加えて,2つのポインタがそれぞれ前のノードアドレス(前駆ポインタprev)と次のノードアドレス(後続ポインタnext)を指す.2)先頭ノードの前駆ポインタprevと末尾ノードの後続ポインタはいずれも空のアドレスを指す.3)性能特徴:単一チェーンテーブルと比べて、同じデータを保存し、より多くのストレージスペースを消費する.単一チェーンテーブルよりも挿入、削除操作の効率が高いO(1)レベル.削除操作を例にとると、削除操作は2つのケースに分けられます.
3.4双方向循環チェーン表
先頭ノードの前駆ポインタは末尾ノードを指し,末尾ノードの後続ポインタは先頭ノードを指す.
4.配列とチェーンテーブルのどちらを選択しますか?
5.LRUバッファ淘汰ポリシーをチェーンテーブルと配列で別々に実装する方法
1)キャッシュとは?キャッシュはデータの読み取り性能を向上させる技術であり、ハードウェア設計、ソフトウェア開発において一般的なCPUキャッシュ、データベースキャッシュ、ブラウザキャッシュなど、広くない応用がある.2)キャッシュを使用する理由すなわち、キャッシュの特徴的なキャッシュのサイズは限られており、キャッシュが満タンになった場合、どのデータがクリーンアップされ、どのデータが保持されるべきか.キャッシュ・トーナメント・ポリシーが必要です.3)キャッシュ・トーナメント・ポリシーとは?キャッシュが満タンになったときにデータをクリーンアップする優先順位を指す.4)どのようなキャッシュ・トーナメント・ポリシーがありますか.一般的な3つには、先進先出しポリシーFIFO(First In,First Out)、最小使用ポリシーLFU(Least Frenquently Used)、最近最小使用ポリシーLRU(Least Recently Used)が含まれる.5)チェーンテーブル実現LRUキャッシュ淘汰戦略アクセスしたデータがキャッシュしたチェーンテーブルに保存されていない場合、直接チェーンテーブルテーブルヘッダにデータを挿入し、時間複雑度はO(1)である.アクセスしたデータが格納されたチェーンテーブルに存在する場合,そのデータに対応するノードをチェーンテーブルヘッダに挿入し,時間複雑度はO(n)とする.キャッシュがいっぱいになると、チェーンテーブルの末尾のデータからクリーンアップが開始され、時間的複雑度はO(1)である.6)配列実現LRUキャッシュ淘汰戦略方式1:最初の位置は最新のアクセスデータを保存し、最後の位置は優先的に削除アクセスしたデータがキャッシュの配列に存在しない場合、直接データを配列の最初の要素の位置に挿入し、この時配列のすべての要素は1つの位置を後方に移動し、時間の複雑度はO(n)である.アクセスしたデータがキャッシュされた配列に存在する場合、データが検索され、配列の最初の位置に挿入されます.この場合、配列要素も移動する必要があります.時間の複雑さはO(n)です.キャッシュがいっぱいになると,末尾のデータは消去され,時間的複雑度はO(1)となる.方式2:最初の位置は優先的にクリーンアップし、最後の位置は最新のアクセスデータを保存し、アクセスしたデータがキャッシュの配列に存在しない場合、直接データを配列に追加して現在最もある要素として時間の複雑度はO(1)である.アクセスしたデータがキャッシュされた配列に存在する場合、データが検索され、現在の配列の最後の要素の位置に挿入されます.この場合、配列要素も移動する必要があります.時間の複雑さはO(n)です.キャッシュがいっぱいになると、配列の最初の位置の要素がクリーンアップされ、残りの配列要素は全体的に1ビット前に移動する必要があり、時間の複雑さはO(n)である.(最適化:一度に一定数をクリーンアップすることで、クリーンアップ回数を低減し、パフォーマンスを向上させることができます.)
6単一チェーンテーブルで「ある文字列が水仙文字列であるかどうかを判断する」にはどうすればいいですか?(例えば上海の水道水は海上から)
方法1:1)前提:文字列が単一文字で単一チェーンテーブルに格納される.2)チェーンテーブルの文字を別のチェーンテーブルに逆順序で格納する.3)2つのチェーンテーブルを同期して巡回し,対応する文字が等しいか否かを比較し,等しい場合は水仙文字列であり,そうでない場合はそうではない.方法2:速慢指針法は回文列の最も重要なのは対称であるため、最も重要な問題はその中心を見つけて、速針で一歩ずつ2格歩いて、彼がチェーン時計の末端に着いたとき、遅針はちょうど中心に着いて、遅針は来たこの道でまた1つのことをして、彼は歩いたノードを逆方向にしました.中心点に新しいポインタを開いて戻るが、遅いポインタは前進し続ける.遅いポインタがチェーンテーブル全体を掃くと、これが回文列であると判断できる.そうしないと、早めに退出する.総じて時間複雑度は遅いポインタで遍歴するとO(n)であり、空間複雑度は3つの追加の補助しか開かないため、o(1)である.
7設計思想
時空置換思想:「空間で時間を変える」と「時間で空間を変える」メモリ空間が十分な場合、コードの実行速度をさらに追求すれば、空間の複雑度が比較的高く、時間の複雑度が比較的低いアルゴリズムとデータの構造を選択することができ、キャッシュは空間の時間を変える例である.メモリが不足している場合、コードが携帯電話や単片機に走っている場合は、逆に時間をかけて空間を変える考えが必要です.
8.参考資料
***本文はただ学習のために使用して、彼のために使用しないでください、例えば権益を侵害して、私に連絡して、すぐに削除してください.