unique() für Arrays in Javascript

Question

Wie jeder weiß, gibt es keine eingebaute Funktion, um die Duplikate aus einem Array in Javascript zu entfernen. Ich habe bemerkt, dass dies auch in jQuery fehlt (die nur eine eindeutige Funktion für DOM-Auswahlen hat), und das am häufigsten verwendete Snippet überprüft das gesamte Array und eine Teilmenge davon für jedes Element (nicht sehr effizient, denke ich) :

for (var i = 0; i < arr.length; i++) 
    for (var j = i + 1; j < arr.length; j++) 
     if (arr[i] === arr[j]) 
      //whatever 

so machte ich meine eigene:

function unique (arr) { 
    var hash = {}, result = []; 
    for (var i = 0; i < arr.length; i++) 
     if (!(arr[i] in hash)) { //it works with objects! in FF, at least 
      hash[arr[i]] = true; 
      result.push(arr[i]); 
     } 
    return result; 
} 

ich frage mich, ob andere Algorithmus für diesen Fall als die beste akzeptiert es ist (oder wenn Sie irgendeine offensichtliche Fehler zu sehen, die behoben werden könnte), oder , was machst du, wenn du das in Javascript brauchst (ich bin mir bewusst, dass jQuery nicht das einzige Framework ist und einige andere haben dies bereits abgedeckt).

Answer 1

Mit dem Objekt Literal ist genau das, was ich tun würde. Eine Menge von Menschen vermisse diese Technik viel der Zeit, stattdessen für typische Array Spaziergänge als den ursprünglichen Code, den Sie gezeigt haben. Die einzige Optimierung wäre es, die arr.length Suche jedes Mal zu vermeiden. Abgesehen davon ist O (n) ungefähr so ​​gut wie du für die Eindeutigkeit und ist viel besser als das ursprüngliche O (n^2) Beispiel.

function unique(arr) { 
    var hash = {}, result = []; 
    for (var i = 0, l = arr.length; i < l; ++i) { 
     if (!hash.hasOwnProperty(arr[i])) { //it works with objects! in FF, at least 
      hash[ arr[i] ] = true; 
      result.push(arr[i]); 
     } 
    } 
    return result; 
} 

// * Edited to use hasOwnProperty per comments 

Zeit Komplexitäten

f() | unsorted | sorted | objects | scalar | library 
____________________________________________________________ 
unique | O(n) | O(n) | no | yes | n/a 
original | O(n^2) | O(n^2) | yes | yes | n/a 
uniq  | O(n^2) | O(n) | yes | yes | Prototype 
_.uniq | O(n^2) | O(n) | yes | yes | Underscore 

Wie bei den meisten Algorithmen zusammenzufassen, gibt es Kompromisse. Wenn Sie nur skalare Werte sortieren, sind Sie Modifikationen am ursprünglichen Algorithmus, die die optimale Lösung ergeben. Wenn Sie jedoch nicht skalare Werte sortieren müssen, ist die Verwendung der Methode uniq einer der genannten Bibliotheken die beste Wahl.

Answer 2

Ich denke, Ihre Version wird nicht funktionieren, wenn Sie Objekte oder Funktionen im Array haben, die String-Darstellung wie [Object object] geben. Weil Sie nur Zeichenfolgen als Schlüssel in Objekten haben können (im "hash" -Objekt hier). Sie müssen eine Schleife in das Ergebnis-Array durchführen, um festzustellen, ob der neue Eintrag bereits existiert. Es wird immer noch schneller als die erste Methode sein.

Prototyp JS hat eine "uniq" Methode, Sie können sich davon inspirieren lassen.

Answer 3

Ich bin kein Algorithmus-Experte, aber ich habe ein Auge auf underscore.js. Sie haben dies als eine Funktion namens uniq:

http://documentcloud.github.com/underscore/#uniq

ich den Code in ihre Bibliothek sah, und kopiert sie hier als Referenz (nicht mein Code, dieser Code gehört Underscore.js):

// Produce a duplicate-free version of the array. If the array has already 
// been sorted, you have the option of using a faster algorithm. 
_.uniq = function(array, isSorted) { 
    return _.reduce(array, [], function(memo, el, i) { 
     if (0 == i || (isSorted === true ? _.last(memo) != el : !_.include(memo, el))) memo.push(el); 
     return memo; 
    }); 
}; 

EDIT: Sie müssen durch den Rest der Unterstreichung.js Code gehen, und ich nahm fast diesen Code aus diesem Grund. Ich habe das Code-Snippet für den Fall gelassen, dass das noch nützlich ist.

Answer 4

Leider haben JS-Objekte keine Identität von der Sprache zugänglich - wie andere Poster erwähnt haben, wird die Verwendung von Objekten als Schlüssel in einem Wörterbuch fehlschlagen, wenn verschiedene Objekte gleiche Zeichenfolgen darstellen und keine id()-Funktion in der Sprache vorhanden ist.

Es gibt eine Möglichkeit, die Überprüfung der O (n^2) -Paare auf === Identität zu vermeiden, wenn Sie die Objekte ändern können.Wählen Sie eine zufällige Zeichenfolge, gehen Sie das Array einmal durch, um zu überprüfen, dass kein Objekt eine Eigenschaft mit diesem Namen hat, und geben Sie dann einfach arr[i][randomPropertyName]=1 für jede i ein. Wenn das nächste Objekt im Array diese Eigenschaft bereits besitzt, handelt es sich um ein Duplikat.

Leider funktioniert das Obige nur für veränderbare Objekte. Es schlägt fehl, für die Array-Werte, die nicht Eigenschaftseinstellung erlauben (zB ganze Zahlen, 42['random']=1 funktioniert einfach nicht :()

Answer 5

Spaß mit Spaß (fiktiven)

function uniqueNum(arr) { 
    return Object.keys(arr.reduce(
     function(o, x) {o[x]=1; return o;}, {})).map(Number); 
}