Detaillierte Beispiele verschiedener Ideen zur Deduplizierung von JavaScript-Arrays

Die Voraussetzung für die Datendeduplizierung besteht tatsächlich darin, dass Toolbibliotheken wie lodash über ausgereifte und vollständige Implementierungen verfügen und in Produktionsumgebungen ausgereift verwendet werden können. Dies hindert uns jedoch nicht daran, aus der Perspektive der Denkerweiterung zu sehen, wie die Entfernung von Duplikaten mithilfe mehrerer Ideen erreicht werden kann. In diesem Artikel werden Ihnen hauptsächlich einige Ideen zur Deduplizierung von JavaScript-Arrays vorgestellt.

Die erste ist die Implementierung der herkömmlichen doppelschichtigen kreisförmigen Vergleichsidee

function doubleLoopUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length, isExist; i < len; i++) {
    // 定义一个变量表示当前元素在 result 中是否存在。
    isExist = false;
    for (let j = 0, rLen = result.length; j < rLen; j++) {
      if (result[j] === arr[i]) {
        // 依次对result 中的元素 和 原数组元素进行比对。
        isExist = true;
        break;
      }
    }
    // 最后判断如果不存在，则将此元素插入result
    !isExist && result.push(arr[i]);
  }
  return result;
}

Verwenden Sie den integrierten IndexOf von js, um Duplikate zu entfernen

function indexOfUniq(arr) {
  let result = [];
  for (let i = 0, len = arr.length; i < len; i++) {
    // 用indexOf 简化了二层循环的流程
    if (result.indexOf(arr[i]) === -1) result.push(arr[i]);
  }
  return result;
}

Vergleichen vor und nach dem Sortieren Deduplizierung

function sortUniq(arr) {
  let result = [], last;
  // 这里解构是为了不对原数组产生副作用
  [ ...arr ].sort().forEach(item => {
    if (item != last) {
      result.push(item);
      last = item;
    }
  });
  return result;
}

Deduplizierung über HashTable

function hashUniq(arr) {
  let hashTable = arr.reduce((result, curr, index, array) => {
    result[curr] = true;
    return result;
  }, {})
  return Object.keys(hashTable).map(item => parseInt(item, 10));
}

ES6 SETZT eine Codezeile, um Deduplizierung zu erreichen

function toSetUniq(arr) {
  return Array.from(new Set(arr));
}

Splice-Deduplizierung (wird direkt ausgeführt das Array selbst, mit Nebenwirkungen )

function inPlaceUniq(arr) {
  let idx = 0;
  while (idx < arr.length) {
    let compare = idx + 1;
    while (compare < arr.length) {
      if (arr[idx] == arr[compare]) {
        arr.splice(compare, 1);
        continue;
      }
      ++compare
    }
    ++idx;
  }
  return arr;
}

Führen Sie abschließend einen einfachen Test unter nodejs durch, um zu sehen, welches effizienter ist~

let data = [];
for (var i = 0; i < 100000; i++) {
  data.push(Math.random())
}

// 实现一个性能测试的装饰器
function performanceTest(fn, descript) {
  var a = new Date().getTime();
  return function () {
    fn.apply(this, [].slice.call(arguments, 0));
    console.log(descript, new Date().getTime() - a)
  }
}

performanceTest(hashUniq, "hashTable")(data)
performanceTest(sortUniq, "sortUniq")(data)
performanceTest(toSetUniq, "toSetUniq")(data)
performanceTest(indexOfUniq, "indexOfUniq")(data)
performanceTest(doubleLoopUniq, "doubleLoopUniq")(data)
performanceTest(inPlaceUniq, "inPlaceUniq")(data)

Die Ergebnisse sind wie folgt

hashTable 168ms
sortUniq 332ms
toSetUniq 80ms
indexOfUniq 4280ms
doubleLoopUniq 13303ms
inPlaceUniq 9977ms

---

Erweiterte Gedanken: Wie entferne ich Duplikate, wenn die Elemente im Array Objekte sind?

Da es sich um einen Referenztyp handelt, wird deepEqual zwangsläufig verwendet. Obwohl diese Idee dieses Problem lösen kann, ist sie zwangsläufig nicht effizient genug.

Aus dem obigen Test geht auch hervor, dass die Deduplizierung über neues Set und hashTable am effizientesten ist.
Es besteht also kein Zweifel, dass wir auf der Grundlage dieser beiden Methoden transformieren müssen.
Andererseits versuche ich, sie zu verwenden, um den Zeitaufwand zu reduzieren JSON.stringify als Referenz Der Typ wird in einen Basistyp konvertiert.

function collectionUniq(collection) {
  let hashTable = {};
  collection.forEach(item => {
    hashTable[JSON.stringify(item)] = true;
  })
  return Object.keys(hashTable).map(item => JSON.parse(item))
}

Dann kommt hier das Problem. Wir alle wissen, dass die Attribute von Objekten ungeordnet sind. Wenn die Daten so sind, dann ist es GG.

let collection = [ { a: 1, b: 2, c: 3 }, { b: 2, c: 3, a: 1 } ]

Es gibt eine toHash-Idee Nachdem Sie eine grundlegende Deduplizierung für dieses Array durchgeführt haben, um die Genauigkeit sicherzustellen,
erst den JSON-String durchlaufen=>
Erhalten Sie die Unicode-Codierung jeder Zeichenfolge über charCodeAt() =>
Fügen Sie hinzu, um eine Gesamtzahl zu erhalten, und vergleichen Sie sie schließlich paarweise. Diejenigen mit gleichen Werten sind Duplikate, wodurch der Effekt der Deduplizierung erzielt wird.

function toHash(obj) {
  let power = 1;
  let res = 0;
  const string = JSON.stringify(obj, null, 2);
  for (let i = 0, l = string.length; i < l; i++) {
    switch (string[i]) {
      case '{':
        power *= 2
        break
      case '}':
        power /= 2
        break
      case ' ':
      case '\n':
      case '\r':
      case '\t':
      break
      default:
        res += string[i].charCodeAt(0) * power
    }
  }
  return res
}

Dies ist nur eine Grundidee für die Implementierung, und es gibt viel Raum für Verbesserungen. Um die Möglichkeit von Hash-Kollisionen zu verringern, können die Gewichte einiger Sonderzeichen erhöht oder verringert werden.

Der entscheidende Punkt besteht darin, sicherzustellen, dass die Wahrscheinlichkeit einer Kollision geringer ist als der Gewinn des Jackpots.

Verwandte Empfehlungen:

Freigabe mehrerer Methoden der JavaScript-Array-Deduplizierung

PHP-Implementierung des Array-Deduplizierungsmethodencodes

JS einfache Implementierung der Array-Deduplizierungsmethodenanalyse

Das obige ist der detaillierte Inhalt vonDetaillierte Beispiele verschiedener Ideen zur Deduplizierung von JavaScript-Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!