Big O Notation を使用した JavaScript の配列とオブジェクトのパフォーマンスの詳細-jsチュートリアル-php.cn

A Deep Dive into the Performance of Arrays and Objects in JavaScript Using Big O Notation

JavaScript の配列とオブジェクトはプログラミングの基礎です。これらは、情報を保存、操作、取得するための基本的なデータ構造を提供します。しかし、データが増大するにつれて、そのパフォーマンス特性を理解することが重要になります。 Big O Notation は、時間計算量の分析に役立ち、大規模な効率的なコードを保証します。

この詳細なガイドでは、配列とオブジェクトの一般的な操作を調査し、それらの Big O の複雑さを分析し、実際の使用法を示す例を提供します。

ビッグオー記法とは何ですか?

Big O Notation は、入力サイズの増加に応じてアルゴリズムまたは操作のパフォーマンスがどのように変化するかを記述します。主に最悪のシナリオに焦点を当てており、開発者がスケーラビリティを評価するのに役立ちます。

主要な複雑さのクラス

O(1): 一定時間、パフォーマンスは入力サイズに依存しません。
O(log n): 対数時間。入力サイズが半分になるとパフォーマンスが向上します。
O(n): 線形時間、パフォーマンスは入力サイズに比例して増加します。
O(n²): 二次時間。入力が大きいとパフォーマンスが大幅に低下します。
O(2ⁿ): 指数関数的な時間であり、大規模なデータセットには非現実的です。

これらの複雑さを理解することで、データ構造を選択したりアルゴリズムを設計したりする際に、より適切な意思決定を行うことができます。

?もっと深く潜ってみたいですか？ JavaScript における Big O 表記法と時間計算量の理解に関する私の以前の記事をチェックしてください: 続きを読む

JavaScript 配列: 操作と複雑さ

JavaScript の配列は順序付けされたコレクションであり、シーケンシャルデータに最適です。その操作の複雑さはタスクに応じて異なります。

1. インデックスによる要素へのアクセス

オペレーション: arr[インデックス]
複雑さ: O(1)

配列を使用すると、インデックスを使用して要素に直接アクセスできるため、この操作が定数時間になります。

例:

const fruits = ['apple', 'banana', 'cherry'];
console.log(fruits[1]); // Output: banana

ログイン後にコピー

2. 要素の追加

プッシュ (末尾に追加): arr.push(element)
- 複雑さ: ほとんどの場合、O(1)。

JavaScript 配列は動的にサイズ変更されるため、追加は効率的です。

シフト解除 (前面に追加): arr.unshift(element)
- 複雑さ: O(n).

既存のすべての要素は、右に 1 位置移動します。

例:

const fruits = ['apple', 'banana', 'cherry'];
console.log(fruits[1]); // Output: banana

ログイン後にコピー

3. 要素の削除

ポップ (末尾から削除): arr.pop()
- 複雑さ: O(1).

要素をシフトする必要はありません。

Shift (前面から削除): arr.shift()
- 複雑さ: O(n).

すべての要素が移動して最初の位置を埋めます。

例:

const numbers = [1, 2, 3];
numbers.push(4); // [1, 2, 3, 4]
numbers.unshift(0); // [0, 1, 2, 3, 4]

ログイン後にコピー

4. 要素の検索

線形検索: arr.indexOf(要素) または arr.includes(要素)
- 複雑さ: O(n).

最悪の場合には各要素をチェックする必要があります。

例:

const animals = ['cat', 'dog', 'fish'];
animals.pop();   // ['cat', 'dog']
animals.shift(); // ['dog']

ログイン後にコピー

5. 仕分け

オペレーション: arr.sort(comparator)
- 複雑さ: O(n log n).

並べ替えには比較と部分的な並べ替えが含まれるため、計算コストが高くなります。

例:

const colors = ['red', 'blue', 'green'];
console.log(colors.indexOf('green')); // 2

ログイン後にコピー

JavaScript オブジェクト: 操作と複雑さ

オブジェクトは、高速な検索、挿入、削除のために設計されたキーと値のストアです。これらは順序付けられていないため、配列とは異なります。

1. プロパティへのアクセス

オペレーション: obj[key]
複雑さ: O(1).

オブジェクトにより、キーを介してプロパティに直接アクセスできます。

例:

const numbers = [4, 2, 7, 1];
numbers.sort((a, b) => a - b); // [1, 2, 4, 7]

ログイン後にコピー

2. プロパティの追加または更新

オペレーション: obj[key] = 値
複雑さ: O(1).

プロパティの追加または更新は高速です。

例:

const user = { name: 'Alice', age: 25 };
console.log(user.name); // Alice

ログイン後にコピー

3. プロパティの削除

オペレーション: obj[key] を削除します
複雑さ: O(1).

プロパティに削除のマークを付けると効率的です。

例:

const user = {};
user.name = 'Alice'; // { name: 'Alice' }
user.age = 25;       // { name: 'Alice', age: 25 }

ログイン後にコピー

4. キーの検索

オペレーション: obj の 'key'
複雑さ: O(1).

オブジェクトはキー検索用に最適化されています。

例:

const user = { name: 'Alice', age: 25 };
delete user.age; // { name: 'Alice' }

ログイン後にコピー

5. プロパティの反復処理

操作: for (オブジェクトにキーを入力させます)
複雑さ: O(n).

各キーがアクセスされます。n はプロパティの数です。

例:

const fruits = ['apple', 'banana', 'cherry'];
console.log(fruits[1]); // Output: banana

ログイン後にコピー

JavaScript 配列メソッドのビッグオー

Method	Description	Time Complexity
arr[index]	Access by index	O(1)
arr.push(value)	Add element to the end	O(1)
arr.pop()	Remove element from the end	O(1)
arr.unshift(value)	Add element to the start	O(n)
arr.shift()	Remove element from the start	O(n)
arr.slice(start, end)	Create a subarray	O(n)
arr.splice(index, ...)	Add/remove elements	O(n)
arr.concat(array)	Merge two arrays	O(n)
arr.indexOf(value)	Find index of first occurrence	O(n)
arr.includes(value)	Check if value exists	O(n)
arr.sort()	Sort the array	O(n log n)
arr.reverse()	Reverse the array	O(n)
arr.forEach(callback)	Iterate over elements	O(n)
arr.map(callback)	Transform elements into a new array	O(n)
arr.filter(callback)	Filter elements into a new array	O(n)
arr.reduce(callback)	Reduce array to a single value	O(n)

JavaScript オブジェクトメソッドのビッグオー

Method	Description	Time Complexity
obj[key]	Access a property by key	O(1)
obj[key] = value	Add or update a property	O(1)
delete obj[key]	Remove a property	O(1)
'key' in obj	Check if a key exists	O(1)
Object.keys(obj)	Get all keys	O(n)
Object.values(obj)	Get all values	O(n)
Object.entries(obj)	Get all key-value pairs	O(n)
for (let key in obj)	Iterate over properties	O(n)