Tag Archives: datastructures

ハッシュテーブル

ハッシュ テーブルを使用すると、挿入、削除、検索操作の平均パフォーマンス O(1) の連想配列 (ディクショナリ) データ構造を実装できます。

以下は、nodeJS でのハッシュ マップの最も単純な実装の例です。

どのように機能するのでしょうか?手に注意してください:

  • ハッシュ マップ内には配列があります
  • 配列要素内には、リンクされたリストの最初のノードへのポインタがあります
  • メモリはポインタの配列（たとえば、65535 要素）に割り当てられます
  • ハッシュ関数を実装しており、辞書キーが入力であり、出力では何でもできますが、最終的には配列要素のインデックスを返します

録音の仕組み:

  • 入り口にはキーペアがあります –値
  • ハッシュ関数はキーごとにインデックスを返します
  • インデックスを使用して配列からリンク リスト ノードを取得する
  • キーと一致するかどうかを確認します
  • 一致する場合は、値を置き換えます
  • 一致しない場合は、必要なキーを持つノードが見つかるまで、次のノードに進みます。
  • それでもノードが見つからない場合は、リンク リストの最後にノードを作成します

キーによる検索の仕組み:

  • 入り口にはキーペアがあります –値
  • ハッシュ関数はキーごとにインデックスを返します
  • インデックスを使用して配列からリンク リスト ノードを取得する
  • キーと一致するかどうかを確認します
  • 一致する場合は値を返します
  • 一致しない場合は、必要なキーを持つノードが見つかるまで、次のノードに進みます。

なぜ配列内にリンクされたリストが必要なのでしょうか?ハッシュ関数の計算時に衝突が発生する可能性があるため。この場合、いくつかの異なるキーと値のペアが配列内の同じインデックスに配置されます。この場合、必要なキーを見つけるためにリンク リストが走査されます。

ソース

https://ru.wikipedia.org/wiki/ハッシュ テーブル
https://www.youtube.com/watch?v=wg8hZxMRwcw

ソースコード

https://gitlab.com/demensdeum/data Structures

スタックマシンとRPN

単純なバイトコード インタープリターを実装する必要があるとします。このタスクを実装するにはどのようなアプローチを選択すればよいでしょうか?

データ構造 スタックは、単純なバイトコード マシンを実装する機能を提供します。スタック マシンの機能と実装については、欧米および国内のインターネット上の多くの記事で説明されています。Java 仮想マシンはスタック マシンの一例であることだけを述べておきます。

マシンの動作原理は単純で、データと操作コード (オペコード) を含むプログラムが入力に供給され、必要な操作はスタックによる操作を使用して実装されます。私のスタック マシンのバイトコード プログラムの例を見てみましょう。

пMVkcatS olleHП

出力では、文字列「Hello StackVM」を受け取ります。スタック マシンはプログラムを左から右に読み取り、オペコードがシンボル – に現れるとデータを 1 文字ずつスタックにロードします。スタックを使用してコマンドを実装します。

nodejs でのスタック マシンの実装例:

逆ポーランド記法 (RPN)

スタック マシンは、逆ポーランド記法 (後置記法) を使用するため、計算機の実装にも簡単に使用できます。
通常の中置記法の例:
2*2+3*4

RPN に変換します:
22*34*+

接尾辞レコードをカウントするには、スタック マシンを使用します。
2–スタックの先頭（スタック: 2）へ
2–スタックの先頭(スタック: 2,2)
*–スタックの先頭を2回取得し、その結果を乗算してスタックの先頭(スタック: 4)に送信します
3–スタックの先頭（スタック: 4、3）へ
4–スタックの一番上（スタック: 4、3、4）へ
*–スタックの先頭を 2 回取得し、その結果を乗算してスタックの先頭 (スタック: 4、12) に送信します。
+–スタックの先頭を 2 回取得し、結果を追加して、スタックの先頭 (スタック: 16) に送信します。

ご覧のとおり –操作 16 の結果はスタックに残ります。たとえば、スタック印刷オペコードを実装することで印刷できます。
p22*34*+P

P–スタック印刷開始オペコード、p –スタックの印刷を終了し、レンダリングのために最終行を送信するためのオペコード。
算術演算を中置演算から後置演算に変換するには、「Sorting Yard」と呼ばれるエドガー ダイクストラのアルゴリズムが使用されます。実装の例は上記、または以下の Nodejs マシン スタック プロジェクトのリポジトリで見ることができます。

ソース

https:/ /tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

ソースコード

https://gitlab.com/demensdeum/stackvm/< /p>