Vier Methoden der Javascript-Array-Deduplizierung
Vier Algorithmen, um diesen Zweck zu erreichen:
Die erste Methode:
Array.prototype.unique1 = function () {
var n = []; //一个新的临时数组
for (var i = 0; i < this.length; i++) //遍历当前数组
{
//如果当前数组的第i已经保存进了临时数组，那么跳过，
//否则把当前项push到临时数组里面
if (n.indexOf(this[i]) == -1) n.push(this[i]);
}
return n;
}
Die zweite Methode:
Array.prototype.unique2 = function()
{
var n = {},r=[]; //n为hash表，r为临时数组
for(var i = 0; i < this.length; i++) //遍历当前数组
{
if (!n[this[i]]) //如果hash表中没有当前项
{
n[this[i]] = true; //存入hash表
r.push(this[i]); //把当前数组的当前项push到临时数组里面
}
}
return r;
}
var arr = [1, 'a', 'a', 'b', 'd', 'e', 'e', 1, 0]
alert(arr.unique2());
Die dritte Methode:
Array.prototype.unique3 = function()
{
var n = [this[0]]; //结果数组
for(var i = 1; i < this.length; i++) //从第二项开始遍历
{
//如果当前数组的第i项在当前数组中第一次出现的位置不是i，
//那么表示第i项是重复的，忽略掉。否则存入结果数组
if (this.indexOf(this[i]) == i) n.push(this[i]);
}
return n;
}
Die erste und dritte Methode verwenden beide die indexOf-Methode des Arrays. Der Zweck dieser Methode besteht darin, das erste Vorkommen des gespeicherten Parameters im Array zu finden. Offensichtlich durchläuft die js-Engine bei der Implementierung dieser Methode das Array, bis sie das Ziel findet. Diese Funktion verschwendet also viel Zeit. Die zweite Methode verwendet eine Hash-Tabelle. Speichern Sie die Vorkommen in einem Objekt in Form von Indizes. Indizierte Referenzen sind viel schneller als das Durchsuchen des Arrays mit indexOf.
Um die Effizienz dieser drei Methoden zu beurteilen, habe ich ein Testprogramm erstellt, um ein Array von Zufallszahlen mit einer Länge von 10.000 zu generieren, und dann mehrere Methoden verwendet, um die Ausführungszeit zu testen. Die Ergebnisse zeigen, dass die zweite Methode viel schneller ist als die beiden anderen Methoden. Hinsichtlich der Speichernutzung dürfte jedoch eher die zweite Methode zum Einsatz kommen, da eine zusätzliche Hash-Tabelle vorhanden ist. Das nennt man Raum für Zeit. Dies ist die Testseite, Sie können sie sich auch ansehen.
Die vierte Methode:
Array.prototype.unique4 = function()
{
this.sort();
var re=[this[0]];
for(var i = 1; i < this.length; i++)
{
if( this[i] !== re[re.length-1])
{
re.push(this[i]);
}
}
return re;
}
Die Idee dieser Methode besteht darin, zuerst das Array zu sortieren und dann die beiden zu vergleichen angrenzende Werte. Beim Sortieren wird die native JS-Sortiermethode verwendet. Die JS-Engine sollte intern die Schnellsortierung verwenden. Das endgültige Testergebnis ist, dass die Laufzeit dieser Methode im Durchschnitt etwa dreimal so hoch ist wie die der zweiten Methode, sie ist jedoch viel schneller als die erste und dritte Methode.
