JavaScript 配列メソッドの背後にあるアルゴリズム-jsチュートリアル-php.cn

Algorithms Behind JavaScript Array Methods

JavaScript 配列メソッドの背後にあるアルゴリズム。

JavaScript 配列には、配列内のデータの操作と取得を可能にするさまざまな組み込みメソッドが付属しています。アウトラインから抽出された配列メソッドのリストは次のとおりです:

concat()
結合()
fill()
含む()
indexOf()
リバース()
ソート()
スプライス()
at()
copyWithin()
フラット()
Array.from()
findLastIndex()
forEach()
毎回()
エントリ()
値()
toReversed() (元の配列を変更せずに配列の逆コピーを作成します)
toSorted() (元の配列を変更せずに配列の並べ替えられたコピーを作成します)
toSpliced() (元の配列を変更せずに要素を追加または削除して新しい配列を作成します)
with() (特定の要素が置換された配列のコピーを返します)
Array.fromAsync()
Array.of()
マップ()
flatMap()
reduce()
reduceRight()
いくつか()
find()
findIndex()
findLast()

各 JavaScript 配列メソッドに使用される一般的なアルゴリズムを詳しく説明します。

1.concat()

アルゴリズム: 線形追加/マージ
時間計算量: O(n) (n はすべての配列の合計長です)
内部で反復を使用して新しい配列を作成し、要素をコピーします

// concat()
Array.prototype.myConcat = function(...arrays) {
  const result = [...this];
  for (const arr of arrays) {
    for (const item of arr) {
      result.push(item);
    }
  }
  return result;
};

ログイン後にコピー

2.結合()

アルゴリズム: 文字列連結による線形トラバーサル
時間計算量: O(n)
配列要素を反復処理し、結果の文字列を構築します

// join()
Array.prototype.myJoin = function(separator = ',') {
  let result = '';
  for (let i = 0; i < this.length; i++) {
    result += this[i];
    if (i < this.length - 1) result += separator;
  }
  return result;
};

ログイン後にコピー

3.fill()

アルゴリズム: 代入を伴う線形トラバース
時間計算量: O(n)
値の割り当てによる単純な反復

// fill()
Array.prototype.myFill = function(value, start = 0, end = this.length) {
  for (let i = start; i < end; i++) {
    this[i] = value;
  }
  return this;
};

ログイン後にコピー

4. include()

アルゴリズム: 線形探索
時間計算量: O(n)
要素が見つかるか終わりに達するまで順次スキャン

// includes()
Array.prototype.myIncludes = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement || (Number.isNaN(this[i]) && Number.isNaN(searchElement))) {
      return true;
    }
  }
  return false;
};

ログイン後にコピー

5.indexOf()

アルゴリズム: 線形探索
時間計算量: O(n)
開始から一致が見つかるまでの連続スキャン

// indexOf()
Array.prototype.myIndexOf = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement) return i;
  }
  return -1;
};

ログイン後にコピー

6. リバース()

アルゴリズム: 2 ポイントの交換
時間計算量: O(n/2)
要素を開始/終了から内側に向かって入れ替えます

// reverse()
Array.prototype.myReverse = function() {
  let left = 0;
  let right = this.length - 1;

  while (left < right) {
    // Swap elements
    const temp = this[left];
    this[left] = this[right];
    this[right] = temp;
    left++;
    right--;
  }

  return this;
};

ログイン後にコピー

7. ソート()

アルゴリズム: 通常は TimSort (マージソートと挿入ソートのハイブリッド)
時間計算量: O(n log n)
最新のブラウザは適応型並べ替えアルゴリズムを使用しています

// sort()
Array.prototype.mySort = function(compareFn) {
  // Implementation of QuickSort for simplicity
  // Note: Actual JS engines typically use TimSort
  const quickSort = (arr, low, high) => {
    if (low < high) {
      const pi = partition(arr, low, high);
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
    }
  };

  const partition = (arr, low, high) => {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      const compareResult = compareFn ? compareFn(arr[j], pivot) : String(arr[j]).localeCompare(String(pivot));
      if (compareResult <= 0) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
  };

  quickSort(this, 0, this.length - 1);
  return this;
};

ログイン後にコピー

8.スプライス()

アルゴリズム: 線形配列変更
時間計算量: O(n)
要素をシフトし、配列をその場で変更します

// splice()
Array.prototype.mySplice = function(start, deleteCount, ...items) {
  const len = this.length;
  const actualStart = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  const actualDeleteCount = Math.min(Math.max(deleteCount || 0, 0), len - actualStart);

  // Store deleted elements
  const deleted = [];
  for (let i = 0; i < actualDeleteCount; i++) {
    deleted[i] = this[actualStart + i];
  }

  // Shift elements if necessary
  const itemCount = items.length;
  const shiftCount = itemCount - actualDeleteCount;

  if (shiftCount > 0) {
    // Moving elements right
    for (let i = len - 1; i >= actualStart + actualDeleteCount; i--) {
      this[i + shiftCount] = this[i];
    }
  } else if (shiftCount < 0) {
    // Moving elements left
    for (let i = actualStart + actualDeleteCount; i < len; i++) {
      this[i + shiftCount] = this[i];
    }
  }

  // Insert new items
  for (let i = 0; i < itemCount; i++) {
    this[actualStart + i] = items[i];
  }

  this.length = len + shiftCount;
  return deleted;
};

ログイン後にコピー

9.at()

アルゴリズム: 直接インデックスアクセス
時間計算量: O(1)
境界チェックを備えた単純な配列のインデックス付け

// at()
Array.prototype.myAt = function(index) {
  const actualIndex = index >= 0 ? index : this.length + index;
  return this[actualIndex];
};

ログイン後にコピー

10.copyWithin()

アルゴリズム: ブロックメモリコピー
時間計算量: O(n)
内部メモリのコピーとシフト操作

// copyWithin()
Array.prototype.myCopyWithin = function(target, start = 0, end = this.length) {
  const len = this.length;
  let to = target < 0 ? Math.max(len + target, 0) : Math.min(target, len);
  let from = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  let final = end < 0 ? Math.max(len + end, 0) : Math.min(end, len);
  const count = Math.min(final - from, len - to);

  // Copy to temporary array to handle overlapping
  const temp = new Array(count);
  for (let i = 0; i < count; i++) {
    temp[i] = this[from + i];
  }

  for (let i = 0; i < count; i++) {
    this[to + i] = temp[i];
  }

  return this;
};

ログイン後にコピー

11.フラット()

アルゴリズム: 再帰的深さ優先トラバーサル
時間計算量: 単一レベルの場合は O(n)、深さ d の場合は O(d*n)
ネストされた配列を再帰的に平坦化します

// flat()
Array.prototype.myFlat = function(depth = 1) {
  const flatten = (arr, currentDepth) => {
    const result = [];
    for (const item of arr) {
      if (Array.isArray(item) && currentDepth < depth) {
        result.push(...flatten(item, currentDepth + 1));
      } else {
        result.push(item);
      }
    }
    return result;
  };

  return flatten(this, 0);
};

ログイン後にコピー

12. Array.from()

アルゴリズム: 反復とコピー
時間計算量: O(n)
反復可能な配列から新しい配列を作成します

// Array.from()
Array.myFrom = function(arrayLike, mapFn) {
  const result = [];
  for (let i = 0; i < arrayLike.length; i++) {
    result[i] = mapFn ? mapFn(arrayLike[i], i) : arrayLike[i];
  }
  return result;
};

ログイン後にコピー

13. findLastIndex()

アルゴリズム: 逆線形探索
時間計算量: O(n)
最後から一致が見つかるまで順次スキャン

// findLastIndex()
Array.prototype.myFindLastIndex = function(predicate) {
  for (let i = this.length - 1; i >= 0; i--) {
    if (predicate(this[i], i, this)) return i;
  }
  return -1;
};

ログイン後にコピー

14.forEach()

アルゴリズム: 線形反復
時間計算量: O(n)
コールバック実行による単純な反復

// forEach()
Array.prototype.myForEach = function(callback) {
  for (let i = 0; i < this.length; i++) {
    if (i in this) {  // Skip holes in sparse arrays
      callback(this[i], i, this);
    }
  }
};

ログイン後にコピー

15. 毎()

アルゴリズム: ショートリニアスキャン
時間計算量: O(n)
最初の false 条件で停止します

// concat()
Array.prototype.myConcat = function(...arrays) {
  const result = [...this];
  for (const arr of arrays) {
    for (const item of arr) {
      result.push(item);
    }
  }
  return result;
};

ログイン後にコピー

16. エントリー()

アルゴリズム: イテレータープロトコルの実装
時間計算量: 作成の場合は O(1)、完全な反復の場合は O(n)
反復子オブジェクトを作成します

// join()
Array.prototype.myJoin = function(separator = ',') {
  let result = '';
  for (let i = 0; i < this.length; i++) {
    result += this[i];
    if (i < this.length - 1) result += separator;
  }
  return result;
};

ログイン後にコピー

17. 値()

アルゴリズム: イテレータープロトコルの実装
時間計算量: 作成の場合は O(1)、完全な反復の場合は O(n)
値のイテレータを作成します

// fill()
Array.prototype.myFill = function(value, start = 0, end = this.length) {
  for (let i = start; i < end; i++) {
    this[i] = value;
  }
  return this;
};

ログイン後にコピー

18.toReversed()

アルゴリズム: 逆反復によるコピー
時間計算量: O(n)
新しい反転配列を作成します

// includes()
Array.prototype.myIncludes = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement || (Number.isNaN(this[i]) && Number.isNaN(searchElement))) {
      return true;
    }
  }
  return false;
};

ログイン後にコピー

19. toSorted()

アルゴリズム: コピーして TimSort
時間計算量: O(n log n)
標準の並べ替えを使用して並べ替えられたコピーを作成します

// indexOf()
Array.prototype.myIndexOf = function(searchElement, fromIndex = 0) {
  const startIndex = fromIndex >= 0 ? fromIndex : Math.max(0, this.length + fromIndex);
  for (let i = startIndex; i < this.length; i++) {
    if (this[i] === searchElement) return i;
  }
  return -1;
};

ログイン後にコピー

20. toSpliced()

アルゴリズム: 変更を加えてコピー
時間計算量: O(n)
変更されたコピーを作成します

// reverse()
Array.prototype.myReverse = function() {
  let left = 0;
  let right = this.length - 1;

  while (left < right) {
    // Swap elements
    const temp = this[left];
    this[left] = this[right];
    this[right] = temp;
    left++;
    right--;
  }

  return this;
};

ログイン後にコピー

21.()付き

アルゴリズム: 単一の変更を伴う浅いコピー
時間計算量: O(n)
1 つの要素を変更してコピーを作成します

// sort()
Array.prototype.mySort = function(compareFn) {
  // Implementation of QuickSort for simplicity
  // Note: Actual JS engines typically use TimSort
  const quickSort = (arr, low, high) => {
    if (low < high) {
      const pi = partition(arr, low, high);
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
    }
  };

  const partition = (arr, low, high) => {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      const compareResult = compareFn ? compareFn(arr[j], pivot) : String(arr[j]).localeCompare(String(pivot));
      if (compareResult <= 0) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
  };

  quickSort(this, 0, this.length - 1);
  return this;
};

ログイン後にコピー

22. Array.fromAsync()

アルゴリズム: 非同期反復と収集
時間計算量: O(n) 非同期操作
Promise と非同期イテラブルを処理します

// splice()
Array.prototype.mySplice = function(start, deleteCount, ...items) {
  const len = this.length;
  const actualStart = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  const actualDeleteCount = Math.min(Math.max(deleteCount || 0, 0), len - actualStart);

  // Store deleted elements
  const deleted = [];
  for (let i = 0; i < actualDeleteCount; i++) {
    deleted[i] = this[actualStart + i];
  }

  // Shift elements if necessary
  const itemCount = items.length;
  const shiftCount = itemCount - actualDeleteCount;

  if (shiftCount > 0) {
    // Moving elements right
    for (let i = len - 1; i >= actualStart + actualDeleteCount; i--) {
      this[i + shiftCount] = this[i];
    }
  } else if (shiftCount < 0) {
    // Moving elements left
    for (let i = actualStart + actualDeleteCount; i < len; i++) {
      this[i + shiftCount] = this[i];
    }
  }

  // Insert new items
  for (let i = 0; i < itemCount; i++) {
    this[actualStart + i] = items[i];
  }

  this.length = len + shiftCount;
  return deleted;
};

ログイン後にコピー

23. Array.of()

アルゴリズム: 配列の直接作成
時間計算量: O(n)
引数から配列を作成します

// at()
Array.prototype.myAt = function(index) {
  const actualIndex = index >= 0 ? index : this.length + index;
  return this[actualIndex];
};

ログイン後にコピー

24. マップ()

アルゴリズム: 変換反復
時間計算量: O(n)
変換された要素を含む新しい配列を作成します

// copyWithin()
Array.prototype.myCopyWithin = function(target, start = 0, end = this.length) {
  const len = this.length;
  let to = target < 0 ? Math.max(len + target, 0) : Math.min(target, len);
  let from = start < 0 ? Math.max(len + start, 0) : Math.min(start, len);
  let final = end < 0 ? Math.max(len + end, 0) : Math.min(end, len);
  const count = Math.min(final - from, len - to);

  // Copy to temporary array to handle overlapping
  const temp = new Array(count);
  for (let i = 0; i < count; i++) {
    temp[i] = this[from + i];
  }

  for (let i = 0; i < count; i++) {
    this[to + i] = temp[i];
  }

  return this;
};

ログイン後にコピー

25. flatMap()

アルゴリズム: マップの平坦化
時間計算量: O(n*m) ここで、m はマップされた配列の平均サイズです
マッピングとフラット化を組み合わせます

// flat()
Array.prototype.myFlat = function(depth = 1) {
  const flatten = (arr, currentDepth) => {
    const result = [];
    for (const item of arr) {
      if (Array.isArray(item) && currentDepth < depth) {
        result.push(...flatten(item, currentDepth + 1));
      } else {
        result.push(item);
      }
    }
    return result;
  };

  return flatten(this, 0);
};

ログイン後にコピー

26.reduce()

アルゴリズム: 線形累積
時間計算量: O(n)
コールバックによる逐次蓄積

// Array.from()
Array.myFrom = function(arrayLike, mapFn) {
  const result = [];
  for (let i = 0; i < arrayLike.length; i++) {
    result[i] = mapFn ? mapFn(arrayLike[i], i) : arrayLike[i];
  }
  return result;
};

ログイン後にコピー

27.reduceRight()

アルゴリズム: 逆線形累積
時間計算量: O(n)
右から左への累積

// findLastIndex()
Array.prototype.myFindLastIndex = function(predicate) {
  for (let i = this.length - 1; i >= 0; i--) {
    if (predicate(this[i], i, this)) return i;
  }
  return -1;
};

ログイン後にコピー

28. いくつか()

アルゴリズム: ショートリニアスキャン
時間計算量: O(n)
最初の true 条件で停止します

// forEach()
Array.prototype.myForEach = function(callback) {
  for (let i = 0; i < this.length; i++) {
    if (i in this) {  // Skip holes in sparse arrays
      callback(this[i], i, this);
    }
  }
};

ログイン後にコピー

29.find()

アルゴリズム: 線形探索
時間計算量: O(n)
条件が満たされるまで順次スキャン

// every()
Array.prototype.myEvery = function(predicate) {
  for (let i = 0; i < this.length; i++) {
    if (i in this && !predicate(this[i], i, this)) {
      return false;
    }
  }
  return true;
};

ログイン後にコピー

30.findIndex()

アルゴリズム: 線形探索
時間計算量: O(n)
一致条件の連続スキャン

// entries()
Array.prototype.myEntries = function() {
  let index = 0;
  const array = this;

  return {
    [Symbol.iterator]() {
      return this;
    },
    next() {
      if (index < array.length) {
        return { value: [index, array[index++]], done: false };
      }
      return { done: true };
    }
  };
};

ログイン後にコピー

31.findLast()

アルゴリズム: 逆線形探索
時間計算量: O(n)
最後から順にスキャン

// concat()
Array.prototype.myConcat = function(...arrays) {
  const result = [...this];
  for (const arr of arrays) {
    for (const item of arr) {
      result.push(item);
    }
  }
  return result;
};

ログイン後にコピー

リクエストされた 31 個の配列メソッドすべての完全な実装を提供しました。

? LinkedIn で私とつながりましょう:

一緒にソフトウェアエンジニアリングの世界を深く掘り下げてみましょう!私は、JavaScript、TypeScript、Node.js、React、Next.js、データ構造、アルゴリズム、Web 開発などに関する洞察を定期的に共有しています。スキルを向上させたいと考えている場合でも、エキサイティングなトピックで共同作業したいと考えている場合でも、私はあなたとつながり、一緒に成長したいと思っています。

フォローしてください: ノジブル・イスラム

以上がJavaScript 配列メソッドの背後にあるアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。