Duplikate schnell aus einem Array entfernen

130952
eddie
Array.prototype.unique = function() {
    var a = [], // uniques get placed into here
        b = 0; // counter to test if value is already in array 'a'

    for ( i = 0; i < this.length; i++ ) {
        var current = this[i]; // get a value from the original array

        for ( j = 0; j < a.length; j++ ) { // loop and check if value is in new array 
            if ( current != a[j] ) {
                b++; // if its not in the new array increase counter
            }
        }

        if ( b == a.length ) { // if the counter increased on all values 
                               // then its not in the new array yet
            a.push( current ); // put it in
        }

        b = 0; // reset counter
    }

    this.length = 0; // after new array is finished creating delete the original array
    for ( i = 0; i < a.length; i++ ) {
        this.push( a[i] ); // push all the new values into the original
    }

    return this; // return this to allow method chaining
}

Ich erwarte, dass dies ein langsamer Checker ist, vor allem weil es keine Sortierung gibt. Ich bin daran interessiert, meine Sortierfähigkeiten usw. zu verbessern, also dachte ich, ich würde eine frühe Überprüfung erhalten.

Antworten
22
Zugehörig zu [Wie kann ich eindeutige Listenelemente schnell finden?] (Http://codereview.stackexchange.com/questions/57581/how-can-i-quickly-find-unique-list-items) megawac vor 6 Jahren 0
Einzeilige Implementierung mit ES6: `Array.prototype.unique = function () {return [... new Set (this)]; } `Test:` [1,3,4,4,4,3,1,2,5,6,6,7] .unique () // [1, 3, 4, 2, 5, 6, 7 ] ` tanguy_k vor 3 Jahren 0

3 Antworten auf die Frage

19
janos

Mit der indexOfFunktion können Sie prüfen, ob ein Wert in einem Array vorhanden ist. Dies würde Ihren Code stark vereinfachen:

Array.prototype.unique = function() {
    var a = [];
    for ( i = 0; i < this.length; i++ ) {
        var current = this[i];
        if (a.indexOf(current) < 0) a.push(current);
    }

    this.length = 0;
    for ( i = 0; i < a.length; i++ ) {
        this.push( a[i] );
    }

    return this;
}

Am Ende ersetzen Sie den Inhalt des Arrays. Es ist besser, das ursprüngliche Array nicht zu mutieren, sondern das neue Array stattdessen mit eindeutigen Elementen zurückzugeben:

Array.prototype.unique = function() {
    var a = [];
    for ( i = 0; i < this.length; i++ ) {
        var current = this[i];
        if (a.indexOf(current) < 0) a.push(current);
    }
    return a;
}

Der Name aist eine sehr schlechte Wahl. uniquewäre besser gewesen.

Sie sollten die Schleifenvariable imit deklarieren let, um ihren Gültigkeitsbereich auf den aktuellen Block zu beschränken, sodass der Code wie folgt lautet:

Array.prototype.unique = function() {
    var unique = [];
    for (let i = 0; i < this.length; i++) {
        let current = this[i];
        if (unique.indexOf(current) < 0) unique.push(current);
    }
    return unique;
}

Schließlich gibt es eine elegantere Lösung für dieses Problem, indem Sie die Reduzierfunktion verwenden :

Array.prototype.unique = function() {
    return this.reduce(function(accum, current) {
        if (accum.indexOf(current) < 0) {
            accum.push(current);
        }
        return accum;
    }, []);
}

UPDATE (zur Beantwortung Ihrer Folgefrage)

Wenn Sie möchten, dass die Funktion einen Parameter verwendet, um zu entscheiden, ob das ursprüngliche Array geändert werden soll, können Sie Folgendes versuchen:

Array.prototype.unique = function(mutate) {
    var unique = this.reduce(function(accum, current) {
        if (accum.indexOf(current) < 0) {
            accum.push(current);
        }
        return accum;
    }, []);
    if (mutate) {
        this.length = 0;
        for (let i = 0; i < unique.length; ++i) {
            this.push(unique[i]);
        }
        return this;
    }
    return unique;
}
Ich habe ein wenig recherchiert und festgestellt, dass fast jede Javascript-Array-Funktion das ursprüngliche Array niemals ändern wird. Ich denke, es ist kohärenter, wenn Sie das ursprüngliche Array nicht berühren. Marco Acierno vor 6 Jahren 3
Ich wäre damit einverstanden, wenn ich nicht alleine arbeite und nicht zu 100% sicher bin, dass niemand sonst meine Implementierung davon verwenden würde. Ich denke, das wird gut. : D eddie vor 6 Jahren 0
Gute Antwort. Ihr "Reduzieren" könnte in einen "Filter" umgewandelt werden, da dies im Grunde das ist, was er tut. elclanrs vor 6 Jahren 1
@MarcoAcierno: Oberhalb meines Kopfes ändern zumindest Array.pop (), Array.splice () und Array.unshift () das ursprüngliche Array. hippietrail vor 4 Jahren 2
9
Emily L.

Falls es einige Duplikate gibt, hat Ihr Algorithmus \ $ \ mathcal {O} (n ^ 2) \ $ Runtime.

Wenn Javascript ein weit verbreitetes Set hätte

Was es leider noch nicht hat, dann könnte man eine wirklich schnelle Implementierung wie folgt machen:

Array.prototype.unique = function() {
    return [...(new Set(this))];
}

Dies wäre \ $ \ mathcal {O} (n \ cdot \ log (n)) \ $ für eine binäre Baumimplementierung gewesen oder \ $ \ mathcal {O} (n) \ $ für eine Hash-basierte Implementierung.

Sortier- und Abzugsreihenfolge

Wenn Sie das Array zuerst sortieren (wie von Ihnen vorgeschlagen), können Sie das Array durchlaufen und das erste Element und dann alle verbleibenden Elemente kopieren, die sich vom vorherigen Element unterscheiden. Dieser Algorithmus hat \ $ \ mathcal {O} (n \ cdot \ log (n)) \ $ Laufzeit. Die Sortierung dominiert hier die Laufzeit. Für kleine Listen ist der Code von Janos ausreichend. Wenn Sie Leistung für große Listen wünschen, benötigen Sie die Sortierung.

Diese Lösung behält die Reihenfolge der Elemente nicht bei, hat jedoch eine schnellere Laufzeit für größere Listen:

Array.prototype.unique = function() {
    var sorted = this;
    sorted.sort();
    return sorted.filter(function(value, index, arr){
        if(index < 1) 
            return true;
        else
            return value != arr[index-1];
    });
}
Wenn Sie Set verwenden, brauchen Sie das überhaupt nicht. Die MDN-Seite besagt, dass, wenn Sie ein Iterator-Objekt an den Konstruktor übergeben, diese hinzugefügt werden, so dass `var seen = new Set (this);` OK sein sollte, da ein Set keine doppelten Elemente hinzufügt Marco Acierno vor 6 Jahren 0
Oh, ich habe nicht einmal bemerkt, dass das Set die Reihenfolge der Einfügung beibehält. Ich bin es so gewohnt, dass dies bei Java und C ++ nicht der Fall ist. Guter Fang! Ich kann nicht testen, da ich momentan keine Zeit oder einen kompatiblen Browser habe. Dies sollte jedoch gemäß dem Beispiel auf der MDN-Site funktionieren. Emily L. vor 6 Jahren 0
Es funktioniert nicht in Google Chrome Canary, aber in Firefox funktioniert es OK. Entfernen Sie einfach den Teil "uneval" (erstellt einen String), "[... mySet]" erstellt ein Array aus dem Set. (http://i.imgur.com/GuwtZnT.png). Es wird einige Zeit dauern, bis wir es jeden Tag verwenden können, aber es ist schön, dies in Javascript zu sehen. (Nun, es ist immer noch eine schlechte Sprache.) Marco Acierno vor 6 Jahren 0
0
Rune FS

Hier ist ein Ansatz, der die Tatsache ausnutzt, dass ein Objekt auch als Hashmap verwendet werden kann. Der Wert von a wird nur für die Bestimmung der Eindeutigkeit verwendet

Array.prototype.unique = function() {
    var existing = {}, result = [], current;
    for ( i = 0; i < this.length; i++) {
        current = this[i];
        if(!existing.hasOwnProperty(current)) { 
           result.push(current);
           existing[current] = true; //any value will do
        }
    }
    return result;
}

Dies funktioniert in \ $ \ mathcal {O} (n) \ $, da es möglich ist, das resultierende Array zu erstellen, während das ursprüngliche Array durchlaufen wird. Ein auf Sortierung basierender Algorithmus hätte wahrscheinlich \ $ \ mathcal {O} (n \ cdot \ log (n)) \ $.

Dies bedeutet jedoch nicht zwangsläufig, dass diese Implementierung schneller ist, da die Kosten für das Einfügen eines Werts in den "Hash" möglicherweise hoch genug sind, sodass einige n diese Implementierung langsamer machen. Die Stärke liegt in der Einfachheit