こんにちは、私は東京からのフルスタックWebデベロッパーであるTUANです。
今後の便利で面白い記事を見逃さないように、私のブログをフォローしてください。
開発者として、アルゴリズムという概念はおそらくご存知だと思います。ただ、データ構造やアルゴリズムが苦手な方は心配しないでください。この記事では、開発者が知っておくべき6つの主要なアルゴリズムを説明します。これらの6つのアルゴリズムはほとんどの場合、開発プロセスで遭遇するすべての問題を解決することができます。
1. ソートアルゴリズム
ソートとは、リスト内の項目を特定の順序で並べることを言います。一般的なソートアルゴリズムには以下があります:
バブルソート
バブルソートは最も基本的なソートアルゴリズムです。隣り合った要素が並び順が異なる場合、繰り返し交換することで動作します。
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
console.log(bubbleSort([5, 3, 8, 2, 1, 4])); // [1, 2, 3, 4, 5, 8]
マージソート
マージソートは「分割して統治する」戦略を使用します。配列を二つの半分に分け、それぞれをソートし、その後、ソートされた半分をマージします。
function mergeSort(arr) {
if (arr.length < 2) return arr;
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
}
console.log(mergeSort([5, 3, 8, 2, 1, 4])); // [1, 2, 3, 4, 5, 8]
クイックソート
クイックソートは人気のあるソートアルゴリズムです。n要素の配列をソートする場合、平均でn log nの比較を行います。もっと効率的で高速なソートアルゴリズムです。
function quickSort(arr) {
if (arr.length < 2) return arr;
let pivot = arr[arr.length - 1];
let left = [];
let right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
console.log(quickSort([5, 3, 8,2, 1, 4])); // [1, 2, 3, 4, 5, 8]
ヒープソート
ヒープソートは配列要素を完全な2分木の一種であるヒープとして視覚化します。配列をヒープにする作業を繰り返し、配列がソートされるまで続けます。
function heapSort(arr) {
let n = arr.length;
for (let i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (let i = n - 1; i >= 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
let l = 2 * i + 1;
let r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
console.log(heapSort([5, 3, 8, 2, 1, 4])); // [1, 2, 3, 4, 5, 8]
2. 探索アルゴリズム
探索とは、データセット内の要素を見つけることを意味します。一般的な探索アルゴリズムには以下があります:
バイナリサーチ
バイナリサーチは「分割して統治する」戦略を使用します。ソート済みリストを二つの半分に分け、ターゲットの値を中央の要素と比較します。一致する場合、中央要素の位置を返します。
function binarySearch(arr, x) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (arr[middle] === x) {
return middle;
} else if (arr[middle] < x) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5, 8], 4)); // 3
幅優先探索（BFS）
幅優先探索は、ルートノードから始まり、すべての隣接ノードを調べるグラフ探索アルゴリズムです。
function breadthFirstSearch(root, target) {
let queue = [root];
while (queue.length) {
let node = queue.shift();
if (node.value === target) return node;
queue.push(...node.children);
}
return null;
}
深さ優先探索（DFS）
深さ優先探索は、グラフの最初のノードから始まり、目標ノードまたは子ノードがないノードを発見するまで深く掘り下げるグラフ探索アルゴリズムです。
function depthFirstSearch(node, target) {
if (node.value === target) return node;
for (let child of node.children) {
let found = depthFirstSearch(child, target);
if (found) return found;
}
return null;
}
3. 動的計画法
動的計画法（DP）は、問題を細かい部分問題に分解し、それぞれを独立に解決し、全体の問題の最適解は部分問題の最適解に依存するという事実を利用し、最適化問題を解決するアルゴリズム手法です。共通の例は、n番目のフィボナッチ数を計算する問題です。
function fibonacci(n) {
let dp = [];
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(fibonacci(5)); // 5
この例では、部分問題の結果（n番目までのフィボナッチ数）を保存するために配列dpを使用します。これにより、冗長な計算を回避し、アルゴリズムの時間複雑度を大幅に削減します。
4. 再帰アルゴリズム
再帰は、解決策が同じ問題の小さいインスタンスの解決策に依存する問題解決手法です。再帰の代表例は階乗の計算です。
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120
5. 分割統治法
分割統治法は、問題を小さい部分問題に分割し、それぞれの部分問題を独立に解決する一般的なアルゴリズム戦略です。分割統治法アルゴリズムの例は、2次元空間内の点の集合から最も近い点のペアを見つける問題です。
function closestPair(points) {
let minDistance = Number.MAX_SAFE_INTEGER;
let closestPair = [];
points.sort((a, b) => a.x - b.x);
for (let i = 0; i < points.length - 1; i++) {
for (let j = i + 1; j < points.length; j++) {
let distance = Math.sqrt(
(points[i].x - points[j].x) ** 2 + (points[i].y - points[j].y) ** 2
);
if (distance < minDistance) {
minDistance = distance;
closestPair = [points[i], points[j]];
}
}
}
return closestPair;
}
console.log(
closestPair([
{ x: 0, y: 0 },
{ x: 3, y: 4 },
{ x: 1, y: 1 },
{ x: 2, y: 2 },
{ x: 5, y: 6 },
])
);
この例では、アルゴリズムはまず点をx座標でソートします。その後、各点に対して、その点がソートされた配列の後に続くすべての点との距離を比較し、もしもっと近い点のペアが見つかった場合、最小距離と最も近い点のペアを更新します。
ハッシュマップ
ハッシュマップは、キーと値のペアを格納し、挿入、削除、検索を常にO(1)の時間で行うことができるデータ構造です。それは、キーを取ってハッシュ関数を適用し、それが配列のインデックスを返すという方法で動作します。そのインデックスの要素はバケットと呼ばれます。値はそのバケットに格納されます。
class HashMap {
constructor() {
this.buckets = Array(10)
.fill(null)
.map(() => []);
this.keys = this.keys = {};
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.buckets.length;
}
set(key, value) {
let index = this.hash(key);
for (let bucket of this.buckets[index]) {
if (bucket[0] === key) {
bucket[1] = value;
return;
}
}
this.buckets[index].push([key, value]);
this.keys[key] = value;
}
get(key) {
let index = this.hash(key);
for (let bucket of this.buckets[index]) {
if (bucket[0] === key) {
return bucket[1];
}
}
return null;
}
delete(key) {
let index = this.hash(key);
let i = 0;
for (let bucket of this.buckets[index]) {
if (bucket[0] === key) {
this.buckets[index].splice(i, 1);
delete this.keys[key];
return;
}
i++;
}
}
}
let map = new HashMap();
map.set("name", "John Smith");
map.set("age", 30);
console.log(map.get("name")); // "John Smith"
console.log(map.get("age")); // 30
map.delete("name");
console.log(map.get("name")); // null
この例では、buckets、keysをプロパティとして持つHashMapクラスを作成しました。そして、hash、set、get、deleteをメソッドに持っています。hashメソッドは、入力としてキーを取り、それを数値に変換し、配列内の対応するバケットのインデックスを返す。set、get、deleteメソッドは、適切なバケットを見つけるためにhashメソッドを使用し、それからキーと値のペアを追加、取得、削除します。
ハッシュマップは、キャッシング、辞書の実装、大量のデータの格納など、多くのシナリオで使用される強力なデータ構造です。ハッシュマップの使い方を知っていることは、開発者として遭遇する多くの問題で役立ちます。
結論
6つの主要アルゴリズムの理解とマスタリングは、すべての開発者にとって重要です。
6つのアルゴリズムは次のとおりです：
- ソートアルゴリズム：バブルソート、マージソート、クイックソート、ヒープソート
- 探索アルゴリズム：バイナリサーチ、幅優先探索、深さ優先探索
- 動的計画法
- 再帰
- 分割統治法
これらのアルゴリズムは、コンピュータサイエンスの基本的な構成要素であり、データのソートや検索から複雑な問題の最適化まで、様々な問題に使用されます。これらのアルゴリズムを理解し、実践することで、開発スキルが向上し、より効率的で効果的なプログラマーになることができます。さらに、これらのアルゴリズムを学ぶことで、プログラミング言語に関係なく役立つコンピュータサイエンスの基礎知識を得ることができます。
ハッシュマップの理解と使用は、開発者にとっても重要なスキルであり、大量のデータを効率的に格納、取得、変更するために役立つデータ構造です。
これらのアルゴリズムはそれぞれの用途、強み、弱点を持っています。それらをすべてマスタリングすることで、開発のキャリアに遭遇する特定の問題に対して適切なアルゴリズムを選ぶことができるようになります。
いつものように、この記事を楽しんで新しいことを学んでいただけたと思います。
ありがとうございました。次の記事でお会いしましょう！
この記事が気に入ったら、いいねをして購読してサポートしてください。ありがとうございます。