アルゴリズムとデータ構造の紹介 (Javascript 版)

序章

アルゴリズムとデータ構造を理解することは、そうでない同業者よりもパフォーマンスを 10 倍向上させるために不可欠です。これは、問題を批判的に分析し、それらを解決するための最善の手段を考案するためです。これは、サーバーのリクエスト時間を高速化することや、最小限のディスク容量で大規模なデータ セットを保存する最適な方法を見つけることを意味する場合があります。

この記事は、アルゴリズムとデータ構造の基本的な概念と、JavaScript を使用してそれらを実装する方法を理解できるようにすることを目的としています。

アルゴリズムとはアルゴリズムは、タスクを実行するための段階的な一連の指示です。早起きに問題があり、締め切りに間に合わないとします。これをどのように解決しますか？あはは！アラームを設定します。それがアルゴリズムの外観です。

一方、データ構造は、データを効率的に格納する方法です。

データ構造とアルゴリズム (DSA) は非常に重要であるため、コンピューターの全体的なパフォーマンスにとって重要です。選択したアルゴリズムによって、実行時間 (Big O Notation) または効率が決まります。一般的な DSA には、二分探索、再帰、並べ替え、配列、連結リスト、ハッシュ テーブルなどがあります。

二分探索とは

国のディレクトリで名前を検索しているとします。 J で始まります。最初 (「A」の国から) から始めて、「J」の国のリストに到達するまでページをめくり続けることができます (これらの国はアルファベット順にソートされています)。国が「Z」で始まる場合は、ディレクトリの最後までめくります。これは、単純な検索アルゴリズムとして知られています。しかし、これが 100,000 を超える電話番号を含む電話帳ディレクトリであるとしたら、これは想像を絶するほど困難です。これをどのように最適化しますか？救助への二分探索。

二分探索アルゴリズムは、ソートされた要素のリストを入力として受け取り、探している要素がリスト内にある場合、二分探索はその要素が存在する位置を返し、それ以外の場合は null を返します。日本にたどり着くために段階的に進む代わりに、二分探索はこの配列を複数の部分に分割し、それに応じてそれぞれを検索します。

このように、検索は高速です。

配列

これらは、キーによってインデックス付けされた要素のコレクションです。配列要素は、コレクション内の識別子として機能するキーとともに、順番に格納されます。そのインデックスは 0 から始まります。

要素の取得またはソートには一定の時間 O(1) がかかるため、これらは非常に便利です。また、データの操作方法に追加の制限を課す他の多くのデータ構造を実装するためにも使用できます。たとえば、文字列は、文字の配列として実装できます。

これは、JavaScript での配列と二分探索の実装です。

 function binary_search(list, item) { let guess = list.find(element => element == item); if (guess) { return guess + "\ncountry index no: " + list.findIndex(country => country === guess); } return null + ": element is not in the array" } console.log(binary_search(country_list, 'Japan')); // Japan | country index no: 109 console.log(binary_search(country_list, 'Cookie')); // null: element is not in the array

ソートアルゴリズム

並べ替えは、プログラマが使用することはめったにありません。ほとんどの場合、それらがコーディングされている言語またはライブラリによって既に処理されています。たとえば、JavaScript 言語は、挿入ソート、ヒープ ソート、またはクイック ソートを使用して配列をソートします。

ヒープソートは、Javascript の array-filter メソッドに似ています。入力をソートされた領域とソートされていない領域に分割し、繰り返し要素をソートされた領域に移動します。以下に例を示します。

リンクされたリスト

リンクされたリストは、すべての要素がデータとリスト内の次の要素へのポインターの両方を含むデータ構造です。リンクされたリストの際立った特徴は、そのアイテムがメモリ内のどこにでも分散できることです。これは配列には当てはまりません。以下の例を参照してください。

ハッシュテーブルとは?

ハッシュ テーブルは、配列内の任意の要素のリストです。格納する要素またはそのキーは、配列内のインデックスとして使用されます。次に例を示します。

ハッシュ関数は、配置する要素のキーをハッシュに変換し、ハッシュされた要素をテーブル内の指定された場所にマップします。これらの各要素は、テーブル内の任意の要素のサブ配列にすることもできます。

再帰

再帰は、他の多くのアルゴリズムで使用されるコーディング手法です。これは長いコードへの近道であり、プログラマ以外のパフォーマンスは向上しない可能性があります。

宝のスーツケースを見つけたとします。このケースのロックを解除するには、他の小さなボックスが入っているボックスからキーを取得する必要があります。

1 つのアプローチは、検索するボックスの山のリストを作成し、これらのボックスのそれぞれに目を通すことです。鍵が見つかったら、それは素晴らしいことです。そうでない場合は、新しい空のボックスをパイル リストに追加して、後で検索します。

再帰により、見つかった新しい空のボックスを検索リストに追加するステップが削除されます。新しい空の見つかったボックスですぐに検索メソッドを呼び出します。これは Javascript の例です。

 const suitCase = new Map(); suitCase.set('box-0', '') .set('box-1', '') .set('box-2', '') .set('box-3', '') .set('box-4', 'key') .set('box-5', '') .set('box-6', ''); function search (suit) { for (let [key, value] of suit) { if (value === 'key') { console.log(`Found ${value} at ${key}!`); } } } search(suitCase); // prints Found key at box-4!

多田さん、鍵を見つけました！

要約すると、DSA はプログラマーとして効果的に考えるための優れた方法です。難しい問題を解決するためのツールを提供します。 GitHub リポジトリ リンクをクリックして、この記事で使用されているすべてのコード スニペットをダウンロードします。ハッピーハッキング！

GitHub コード リポジトリ