Algorithmen hinter JavaScript-Array-Methoden-js-Tutorial-php.cn

Algorithms Behind JavaScript Array Methods

Algorithmen hinter JavaScript-Array-Methoden.

JavaScript-Arrays verfügen über verschiedene integrierte Methoden, die die Manipulation und den Abruf von Daten in einem Array ermöglichen. Hier ist eine Liste der aus Ihrer Gliederung extrahierten Array-Methoden:

concat()
join()
fill()
includes()
indexOf()
reverse()
sort()
spleißen()
at()
copyWithin()
flat()
Array.from()
findLastIndex()
forEach()
jeder()
Einträge()
Werte()
toReversed() (erstellt eine umgekehrte Kopie des Arrays, ohne das Original zu ändern)
toSorted() (erstellt eine sortierte Kopie des Arrays, ohne das Original zu ändern)
toSpliced() (erstellt ein neues Array mit hinzugefügten oder entfernten Elementen, ohne das Original zu ändern)
with() (gibt eine Kopie des Arrays zurück, wobei ein bestimmtes Element ersetzt wurde)
Array.fromAsync()
Array.of()
map()
flatMap()
reduce()
reduceRight()
einige()
find()
findIndex()
findLast()

Lassen Sie mich die allgemeinen Algorithmen aufschlüsseln, die für jede JavaScript-Array-Methode verwendet werden:

1. concat()

Algorithmus: Lineares Anhängen/Zusammenführen
Zeitkomplexität: O(n), wobei n die Gesamtlänge aller Arrays ist
Verwendet intern die Iteration, um neue Arrays zu erstellen und Elemente zu kopieren

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

Nach dem Login kopieren

2. beitreten()

Algorithmus: Lineare Durchquerung mit String-Verkettung
Zeitkomplexität: O(n)
Durchläuft Array-Elemente und erstellt eine Ergebniszeichenfolge

// 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;
};

Nach dem Login kopieren

3. fill()

Algorithmus: Lineare Durchquerung mit Zuweisung
Zeitkomplexität: O(n)
Einfache Iteration mit Wertzuweisung

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

Nach dem Login kopieren

4. Includes()

Algorithmus: Lineare Suche
Zeitkomplexität: O(n)
Sequentieller Scan, bis ein Element gefunden oder das Ende erreicht ist

// 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;
};

Nach dem Login kopieren

5. indexOf()

Algorithmus: Lineare Suche
Zeitkomplexität: O(n)
Sequentieller Scan vom Start bis zum Finden einer Übereinstimmung

// 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;
};

Nach dem Login kopieren

6. reverse()

Algorithmus: Zwei-Zeiger-Swap
Zeitkomplexität: O(n/2)
Tauscht Elemente vom Anfang/Ende nach innen

// 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;
};

Nach dem Login kopieren

7. sort()

Algorithmus: Typischerweise TimSort (Hybrid aus Zusammenführungssortierung und Einfügungssortierung)
Zeitkomplexität: O(n log n)
Moderne Browser verwenden adaptive Sortieralgorithmen

// 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;
};

Nach dem Login kopieren

8. splice()

Algorithmus: Lineare Array-Modifikation
Zeitkomplexität: O(n)
Verschiebt Elemente und ändert das Array direkt

// 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;
};

Nach dem Login kopieren

9. at()

Algorithmus: Direkter Indexzugriff
Zeitkomplexität: O(1)
Einfache Array-Indizierung mit Grenzprüfung

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

Nach dem Login kopieren

10. copyWithin()

Algorithmus: Speicherkopie blockieren
Zeitkomplexität: O(n)
Kopier- und Verschiebungsvorgänge im internen Speicher

// 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;
};

Nach dem Login kopieren

11. flach()

Algorithmus: Rekursive Tiefendurchquerung
Zeitkomplexität: O(n) für einzelne Ebene, O(d*n) für Tiefe d
Reduziert verschachtelte Arrays rekursiv

// 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);
};

Nach dem Login kopieren

12. Array.from()

Algorithmus: Iteration und Kopieren
Zeitkomplexität: O(n)
Erstellt ein neues Array aus iterierbar

// 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;
};

Nach dem Login kopieren

13. findLastIndex()

Algorithmus: Umgekehrte lineare Suche
Zeitkomplexität: O(n)
Sequentieller Scan vom Ende bis zum Finden einer Übereinstimmung

// 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;
};

Nach dem Login kopieren

14. forEach()

Algorithmus: Lineare Iteration
Zeitkomplexität: O(n)
Einfache Iteration mit Callback-Ausführung

// 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);
    }
  }
};

Nach dem Login kopieren

15. jeder()

Algorithmus: Linearer Kurzschlussscan
Zeitkomplexität: O(n)
Stoppt bei der ersten falschen Bedingung

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

Nach dem Login kopieren

16. Einträge()

Algorithmus: Implementierung des Iteratorprotokolls
Zeitkomplexität: O(1) für die Erstellung, O(n) für die vollständige Iteration
Erstellt ein Iteratorobjekt

// 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;
};

Nach dem Login kopieren

17. Werte()

Algorithmus: Implementierung des Iteratorprotokolls
Zeitkomplexität: O(1) für die Erstellung, O(n) für die vollständige Iteration
Erstellt einen Iterator für Werte

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

Nach dem Login kopieren

18. toReversed()

Algorithmus: Kopieren mit umgekehrter Iteration
Zeitkomplexität: O(n)
Erstellt ein neues umgekehrtes Array

// 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;
};

Nach dem Login kopieren

19. toSorted()

Algorithmus: Kopieren, dann TimSort
Zeitkomplexität: O(n log n)
Erstellt eine sortierte Kopie mit der Standardsortierung

// 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;
};

Nach dem Login kopieren

20. toSpliced()

Algorithmus: Kopieren mit Änderung
Zeitkomplexität: O(n)
Erstellt eine geänderte Kopie

// 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;
};

Nach dem Login kopieren

21. mit()

Algorithmus: Flache Kopie mit einmaliger Änderung
Zeitkomplexität: O(n)
Erstellt eine Kopie mit einem geänderten Element

// 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;
};

Nach dem Login kopieren

22. Array.fromAsync()

Algorithmus: Asynchrone Iteration und Sammlung
Zeitkomplexität: O(n) asynchrone Operationen
Verarbeitet Versprechen und asynchrone Iterables

// 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;
};

Nach dem Login kopieren

23. Array.of()

Algorithmus: Direkte Array-Erstellung
Zeitkomplexität: O(n)
Erstellt ein Array aus Argumenten

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

Nach dem Login kopieren

24. Karte()

Algorithmus: Transformationsiteration
Zeitkomplexität: O(n)
Erstellt ein neues Array mit transformierten Elementen

// 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;
};

Nach dem Login kopieren

25. flatMap()

Algorithmus: Karte abflachen
Zeitkomplexität: O(n*m), wobei m die durchschnittliche Größe des zugeordneten Arrays ist
Kombiniert Mapping und Flattening

// 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);
};

Nach dem Login kopieren

26. Reduzieren()

Algorithmus: Lineare Akkumulation
Zeitkomplexität: O(n)
Sequentielle Akkumulation mit Rückruf

// 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;
};

Nach dem Login kopieren

27. ReduceRight()

Algorithmus: Umgekehrte lineare Akkumulation
Zeitkomplexität: O(n)
Akkumulation von rechts nach links

// 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;
};

Nach dem Login kopieren

28. einige()

Algorithmus: Linearer Kurzschlussscan
Zeitkomplexität: O(n)
Stoppt bei der ersten wahren Bedingung

// 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);
    }
  }
};

Nach dem Login kopieren

29. find()

Algorithmus: Lineare Suche
Zeitkomplexität: O(n)
Sequentieller Scan, bis die Bedingung erfüllt ist

// 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;
};

Nach dem Login kopieren

30. findIndex()

Algorithmus: Lineare Suche
Zeitkomplexität: O(n)
Sequentieller Scan nach übereinstimmender Bedingung

// 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 };
    }
  };
};

Nach dem Login kopieren

31. findLast()

Algorithmus: Umgekehrte lineare Suche
Zeitkomplexität: O(n)
Sequentieller Scan vom Ende

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

Nach dem Login kopieren

Ich habe vollständige Implementierungen aller 31 von Ihnen angeforderten Array-Methoden bereitgestellt.

? Vernetzen Sie sich mit mir auf LinkedIn:

Lassen Sie uns gemeinsam tiefer in die Welt des Software-Engineerings eintauchen! Ich teile regelmäßig Einblicke in JavaScript, TypeScript, Node.js, React, Next.js, Datenstrukturen, Algorithmen, Webentwicklung und vieles mehr. Egal, ob Sie Ihre Fähigkeiten verbessern oder an spannenden Themen zusammenarbeiten möchten, ich würde mich gerne mit Ihnen vernetzen und mit Ihnen wachsen.

Folge mir: Nozibul Islam

Das obige ist der detaillierte Inhalt vonAlgorithmen hinter JavaScript-Array-Methoden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!