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

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

1. concat()
2. 結(jié)合()
3. fill()
4. 含む()
5. indexOf()
6. リバース()
7. ソート()
8. スプライス()
9. at()
10. copyWithin()
11. フラット()
12. Array.from()
13. findLastIndex()
14. forEach()
15. 毎回()
16. エントリ()
17. 値()
18. toReversed() (元の配列を変更せずに配列の逆コピーを作成します)
19. toSorted() (元の配列を変更せずに配列の並べ替えられたコピーを作成します)
20. toSpliced() (元の配列を変更せずに要素を追加または削除して新しい配列を作成します)
21. with() (特定の要素が置換された配列のコピーを返します)
22. Array.fromAsync()
23. Array.of()
24. マップ()
25. flatMap()
26. reduce()
27. reduceRight()
28. いくつか()
29. find()
30. findIndex()
31. findLast()

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

1.concat()

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

// 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.結(jié)合()

• アルゴリズム: 文字列連結(jié)による線形トラバーサル
• 時(shí)間計(jì)算量: O(n)
• 配列要素を反復(fù)処理し、結(jié)果の文字列を構(gòu)築します

// 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()

• アルゴリズム: 代入を伴う線形トラバース
• 時(shí)間計(jì)算量: O(n)
• 値の割り當(dāng)てによる?yún)g純な反復(fù)

// 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()

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

// 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()

• アルゴリズム: 線形探索
• 時(shí)間計(jì)算量: 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 ポイントの交換
• 時(shí)間計(jì)算量: O(n/2)
• 要素を開始/終了から內(nèi)側(cè)に向??かって入れ替えます

// 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 (マージ ソートと挿入ソートのハイブリッド)
• 時(shí)間計(jì)算量: 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.スプライス()

• アルゴリズム: 線形配列変更
• 時(shí)間計(jì)算量: 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()

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

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

10.copyWithin()

• アルゴリズム: ブロックメモリコピー
• 時(shí)間計(jì)算量: O(n)
• 內(nèi)部メモリのコピーとシフト操作

// 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.フラット()

• アルゴリズム: 再帰的深さ優(yōu)先トラバーサル
• 時(shí)間計(jì)算量: 単一レベルの場合は 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()

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

// 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()

• アルゴリズム: 逆線形探索
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 線形反復(fù)
• 時(shí)間計(jì)算量: O(n)
• コールバック実行による?yún)g純な反復(fù)

// 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. 毎()

アルゴリズム: ショートリニアスキャン
時(shí)間計(jì)算量: 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. エントリー()

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

// 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. 値()

• アルゴリズム: イテレータープロトコルの実裝
• 時(shí)間計(jì)算量: 作成の場合は O(1)、完全な反復(fù)の場合は 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()

• アルゴリズム: 逆反復(fù)によるコピー
• 時(shí)間計(jì)算量: 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
• 時(shí)間計(jì)算量: O(n log n)
• 標(biāo)準(zhǔ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()

• アルゴリズム: 変更を加えてコピー
• 時(shí)間計(jì)算量: 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.()付き

• アルゴリズム: 単一の変更を伴う淺いコピー
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 非同期反復(fù)と収集
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 配列の直接作成
• 時(shí)間計(jì)算量: O(n)
• 引數(shù)から配列を作成します

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

24. マップ()

• アルゴリズム: 変換反復(fù)
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: マップの平坦化
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 線形累積
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 逆線形累積
• 時(shí)間計(jì)算量: 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. いくつか()

• アルゴリズム: ショートリニアスキャン
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 線形探索
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 線形探索
• 時(shí)間計(jì)算量: 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()

• アルゴリズム: 逆線形探索
• 時(shí)間計(jì)算量: 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 個(gè)の配列メソッドすべての完全な実裝を提供しました。

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

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

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

以上がJavaScript 配列メソッドの背後にあるアルゴリズムの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。