4 Möglichkeiten, Duplikate aus JS-Arrays zu entfernen

Eine Frage, auf die sich Front-End-Interviewer vorbereiten müssen: So entfernen Sie Duplikate aus dem Array von Javascript. Soweit ich weiß, haben Baidu, Tencent, Shanda usw. diese Frage alle in Interviews gestellt. Diese Frage scheint einfach, birgt aber tatsächlich versteckte Gefahren. Bei dem Test geht es nicht nur um die Implementierung dieser Funktion, sondern auch um Ihr tiefgreifendes Verständnis für die Ausführung von Computerprogrammen.

Ich habe mir insgesamt drei Algorithmen ausgedacht, um diesen Zweck zu erreichen:

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

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

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 vorhandenen Werte 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. Im Hinblick auf die Speichernutzung ist es jedoch wahrscheinlicher, dass die zweite Methode verwendet wird, 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.

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 zwei benachbarte Werte zu vergleichen. 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.