Algorithmes derrière les méthodes de tableau JavaScript-js tutoriel-php.cn

Algorithms Behind JavaScript Array Methods

Algorithmes derrière les méthodes de tableau JavaScript.

Les tableaux JavaScript sont livrés avec diverses méthodes intégrées qui permettent la manipulation et la récupération des données dans un tableau. Voici une liste de méthodes de tableau extraites de votre plan :

concat()
rejoindre()
remplissage()
inclut()
indexOf()
inverse()
trier()
épissure()
à()
copyWithin()
plat()
Array.from()
findLastIndex()
pourEach()
chaque()
entrées()
valeurs()
toReversed() (crée une copie inversée du tableau sans modifier l'original)
toSorted() (crée une copie triée du tableau sans modifier l'original)
toSpliced() (crée un nouveau tableau avec des éléments ajoutés ou supprimés sans modifier l'original)
with() (renvoie une copie du tableau avec un élément spécifique remplacé)
Array.fromAsync()
Array.of()
carte()
flatMap()
réduire()
réduireRight()
certains()
trouver()
findIndex()
findLast()

Permettez-moi de détailler les algorithmes courants utilisés pour chaque méthode de tableau JavaScript :

1. concaténer()

Algorithme : ajout/fusion linéaire
Complexité temporelle : O(n) où n est la longueur totale de tous les tableaux
Utilise en interne l'itération pour créer un nouveau tableau et copier des éléments

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

Copier après la connexion

2. rejoindre()

Algorithme : Parcours linéaire avec concaténation de chaînes
Complexité temporelle : O(n)
Parcourt les éléments du tableau et crée la chaîne de résultat

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

Copier après la connexion

3. remplir()

Algorithme : Parcours linéaire avec affectation
Complexité temporelle : O(n)
Itération simple avec attribution de valeur

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

Copier après la connexion

4. inclut()

Algorithme : Recherche linéaire
Complexité temporelle : O(n)
Analyse séquentielle jusqu'à ce que l'élément soit trouvé ou la fin atteinte

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

Copier après la connexion

5. indexDe()

Algorithme : Recherche linéaire
Complexité temporelle : O(n)
Analyse séquentielle du début jusqu'à ce que la correspondance soit trouvée

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

Copier après la connexion

6. inverse()

Algorithme : échange à deux points
Complexité temporelle : O(n/2)
Échange les éléments du début/de la fin vers l'intérieur

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

Copier après la connexion

7. trier()

Algorithme : généralement TimSort (hybride de tri par fusion et de tri par insertion)
Complexité temporelle : O(n log n)
Les navigateurs modernes utilisent des algorithmes de tri adaptatifs

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

Copier après la connexion

8. épissure()

Algorithme : Modification du réseau linéaire
Complexité temporelle : O(n)
Déplace les éléments et modifie le tableau sur place

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

Copier après la connexion

9. à()

Algorithme : Accès direct à l'index
Complexité temporelle : O(1)
Indexation simple des tableaux avec vérification des limites

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

Copier après la connexion

10. copyWithin()

Algorithme : Bloquer la copie de la mémoire
Complexité temporelle : O(n)
Opérations de copie et de décalage de la mémoire interne

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

Copier après la connexion

11. plat()

Algorithme : parcours récursif en profondeur d'abord
Complexité temporelle : O(n) pour un seul niveau, O(d*n) pour la profondeur d
Aplatit récursivement les tableaux imbriqués

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

Copier après la connexion

12. Tableau.from()

Algorithme : Itération et copie
Complexité temporelle : O(n)
Crée un nouveau tableau à partir d'un itérable

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

Copier après la connexion

13. findLastIndex()

Algorithme : Recherche linéaire inversée
Complexité temporelle : O(n)
Analyse séquentielle de la fin jusqu'à ce que la correspondance soit trouvée

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

Copier après la connexion

14. pourChaque()

Algorithme : Itération linéaire
Complexité temporelle : O(n)
Itération simple avec exécution de rappel

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

Copier après la connexion

15. chaque()

Algorithme : Balayage linéaire en court-circuit
Complexité temporelle : O(n)
S'arrête à la première fausse condition

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

Copier après la connexion

16. entrées()

Algorithme : Implémentation du protocole itérateur
Complexité temporelle : O(1) pour la création, O(n) pour l'itération complète
Crée un objet itérateur

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

Copier après la connexion

17. valeurs()

Algorithme : Implémentation du protocole itérateur
Complexité temporelle : O(1) pour la création, O(n) pour l'itération complète
Crée un itérateur pour les valeurs

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

Copier après la connexion

18. toReversed()

Algorithme : Copie avec itération inverse
Complexité temporelle : O(n)
Crée un nouveau tableau inversé

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

Copier après la connexion

19. àTrié()

Algorithme : Copier puis TimSort
Complexité temporelle : O(n log n)
Crée une copie triée à l'aide du tri standard

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

Copier après la connexion

20. àSpliced()

Algorithme : Copie avec modification
Complexité temporelle : O(n)
Crée une copie modifiée

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

Copier après la connexion

21. avec()

Algorithme : copie superficielle avec une seule modification
Complexité temporelle : O(n)
Crée une copie avec un élément modifié

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

Copier après la connexion

22. Tableau.fromAsync()

Algorithme : Itération et collecte asynchrones
Complexité temporelle : opérations asynchrones O(n)
Gère les promesses et les itérables asynchrones

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

Copier après la connexion

23. Tableau.de()

Algorithme : Création directe de tableaux
Complexité temporelle : O(n)
Crée un tableau à partir d'arguments

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

Copier après la connexion

24. carte()

Algorithme : Itération de transformation
Complexité temporelle : O(n)
Crée un nouveau tableau avec des éléments transformés

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

Copier après la connexion

25. flatMap()

Algorithme : Carte aplatie
Complexité temporelle : O(n*m) où m est la taille moyenne du tableau mappé
Combine le mappage et l'aplatissement

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

Copier après la connexion

26. réduire()

Algorithme : Accumulation linéaire
Complexité temporelle : O(n)
Accumulation séquentielle avec rappel

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

Copier après la connexion

27. réduireDroite()

Algorithme : Accumulation linéaire inversée
Complexité temporelle : O(n)
Accumulation de droite à gauche

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

Copier après la connexion

28. certains()

Algorithme : Balayage linéaire en court-circuit
Complexité temporelle : O(n)
S'arrête à la première condition vraie

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

Copier après la connexion

29. trouver()

Algorithme : Recherche linéaire
Complexité temporelle : O(n)
Analyse séquentielle jusqu'à ce que la condition soit remplie

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

Copier après la connexion

30. findIndex()

Algorithme : Recherche linéaire
Complexité temporelle : O(n)
Analyse séquentielle pour la condition correspondante

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

Copier après la connexion

31. trouverDernier()

Algorithme : Recherche linéaire inversée
Complexité temporelle : O(n)
Analyse séquentielle depuis la fin

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

Copier après la connexion

J'ai fourni des implémentations complètes des 31 méthodes de tableau que vous avez demandées.

? Connectez-vous avec moi sur LinkedIn :

Plongeons ensemble plus profondément dans le monde du génie logiciel ! Je partage régulièrement des informations sur JavaScript, TypeScript, Node.js, React, Next.js, les structures de données, les algorithmes, le développement Web et bien plus encore. Que vous cherchiez à améliorer vos compétences ou à collaborer sur des sujets passionnants, j'aimerais entrer en contact et grandir avec vous.

Suivez-moi : Nozibul Islam

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!