gleichwertig, aber einzigartige Objekte aus einer JavaScript-Array Entfernen

Question

I ein Array von Objekten ähnlich den folgenden haben:

var routeArr = [ 
    {start: 1, end: 2}, 
    {start: 1, end: 3}, 
    {start: 1, end: 4}, 
    {start: 2, end: 1}, 
    {start: 3, end: 1}, 
    {start: 4, end: 1} 
]; 

Diese Objekte stellen die Anfangs- und Endpunkt der Linien und als solche {start: 1, end: 2} und {start: 2, end: 1} die gleichen Linie.

Ich versuche, alle doppelten Zeilen aus dem Array zu entfernen und kann keine effiziente oder elegante Möglichkeit finden, es zu tun. Ich habe eine verschachtelte Schleife versucht, aber mir wurde gesagt, dass das eine schlechte Übung ist (und ich bekomme Fehler mit meiner Implementierung, und es ist nur hässlich).

for(var i = 0, numRoutes = routeArr.length; i < numRoutes; i++) { 
    var primaryRoute = routeArr[i]; 

    for(var j = 0; j < numRoutes; j++) { 
     var secondRoute = routeArr[j]; 

     if(primaryRoute.start === secondRoute.end && primaryRoute.end === secondRoute.start) { 
      routeArr.splice(j, 1); 
      continue; 
     } 
    } 
} 

Kann jemand Vorschläge anbieten?

Answer 1

Erstellen Sie ein Objekt/Map in Javascript und behalten Sie die Indizes der eindeutigen Objekte, speichern Sie "min (Start, Ende): max (Start, Ende)" als Schlüssel und Index als Wert. Hier ist eine Implementierung Ihrer Frage in javascript:

// your initial array 
var routeArr = [ 
    {start: 1, end: 2}, 
    {start: 1, end: 3}, 
    {start: 1, end: 4}, 
    {start: 2, end: 1}, 
    {start: 3, end: 1}, 
    {start: 4, end: 1} 
]; 

// map where we will store key => value where key is a joined start,end of your array's item and value is an item index 
var keyToRouteIndexMap = {}; 

for (var i in routeArr){ 
    // calculating min and max from start and end to understand {start:1, end:2} and {start:2, end:1} object as duplicates 
    var min = Math.min(routeArr[i].start,routeArr[i].end); 
    var max = Math.max(routeArr[i].start,routeArr[i].end); 
    // unique key 
    var key = min+':'+max; 
    if (!keyToRouteIndexMap.hasOwnProperty(key)){ 
     keyToRouteIndexMap[key] = i; 
    } 
} 

for(var key in keyToRouteIndexMap){ 
    if(keyToRouteIndexMap.hasOwnProperty(key)){ 
     console.log(routeArr[keyToRouteIndexMap[key]]); 
    } 
} 

Answer 2

Hier wird eine allgemeine Lösung für das Problem der Beseitigung der doppelten Werte von JavaScript-Arrays:

/** 
* Takes an input array and returns a new array without identical elements. 
* 
* @param {array} input 
* @callback id identity function returning identical values for identical elements 
*/ 
function uniquify(input, id) { 
    result = []; 
    map = {}; 
    for (var i = 0, length = input.length; i < length; ++i) { 
     var element = input[i], identity = id(element); 
     if (!map.hasOwnProperty(identity)) { 
      result.push(element); 
      map[identity] = true; 
     } 
    } 
    return result; 
} 

Angewandt auf Ihre routeArr gegeben:

var routeArr = [ 
    {start: 1, end: 2}, 
    {start: 1, end: 3}, 
    {start: 1, end: 4}, 
    {start: 2, end: 1}, 
    {start: 3, end: 1}, 
    {start: 4, end: 1} 
]; 

routeArr = uniquify(routeArr, function(route) { 
    return route.start < route.end ? '' + route.start + ':' + route.end : '' + route.end + ':' + route.start; 
}); 

Answer 3

Sie können so tun. Ich denke, das ist sehr schnell, da es überhaupt keine Suchanfragen gibt. Eine Array.prototype.reduce() - Operation, um sowohl die Hash-Tabelle (Nachschlagetabelle) als auch das reduzierte Objekt gleichzeitig zu erstellen. Dann ordnen Sie die Objektschlüssel zu, um das Ergebnis zu erhalten. Hier ist es;

var routeArr = [ 
 
    {start: 1, end: 2}, 
 
    {start: 1, end: 3}, 
 
    {start: 1, end: 4}, 
 
    {start: 2, end: 1}, 
 
    {start: 3, end: 1}, 
 
    {start: 4, end: 1} 
 
], 
 

 
reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) && (p[c.start+"-"+c.end] = c); 
 
            return p;},{}), 
 
result = Object.keys(reduced).map(e => reduced[e]); 
 
console.log(result);

Nun, es einen zweiten Gedanken i die redundante Object.keys() Teil eliminiert. Nun ist dies nichts weiter als ein einziger Array.prototype.reduce() Durchlauf alles in nur O (n) abgeschlossen. Ich nehme an, dass dies hinsichtlich der Leistung so weit wie möglich gehen könnte. Hör zu.

var routeArr = [ 
 
    {start: 1, end: 2}, 
 
    {start: 1, end: 3}, 
 
    {start: 1, end: 4}, 
 
    {start: 2, end: 1}, 
 
    {start: 3, end: 1}, 
 
    {start: 4, end: 1} 
 
], 
 

 
    reduced = routeArr.reduce((p,c) => {!(p[c.start+"-"+c.end] || 
 
              p[c.end+"-"+c.start]) && 
 
              (p[c.start+"-"+c.end] = true, 
 
              p.result.push(c)); 
 
              return p; 
 
             },{"result":[]}); 
 
console.log(reduced.result);

Na ok ja, ich muss zugeben, es ist ein wenig kryptisch aussieht, aber es ist sehr einfach.

• Wir verwenden Array.prototype.reduce() Methode mit einem Anfangswert hier. Dies ist unser Anfangswert {"result":[]}. Beim Reduzieren unseres routeArr Arrays ist unser anfängliches Element nun ein Objekt mit einer einzelnen Eigenschaft namens result und Wert eines leeren Arrays.
• reduzieren wurde mit einer anonymen Callback-Funktion zur Verfügung gestellt, die zwei Argumente (p,c) steht für vorherige und c steht für aktuelle. Also im ersten Lauf p ist unser Initialisierungsobjekt, ich meine dies {"result":[]} und c ist das Element im Index 0 des Arrays (routeArr), die wir auf Reduzieren genannt haben. Also in der ersten Runde c ist {start: 1, end: 2}.
• Zu Beginn jeder Runde prüfen wir, ob unser Objekt eine Eigenschaft enthält, die die aktuellen Elemente in beiden Aufträgen repräsentiert. Also kommt der Check wie folgt: !(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) was bedeutet "ist es wahr, dass Sie keine String-Eigenschaft wie c.start-c.end oder c.end-c.start" haben. Also zum Beispiel in der ersten Um die Überprüfung geht es wie folgt: "Ist es wahr, dass Sie keine String-Eigenschaft wie" 1-2 "oder" 2-1 "haben. Wenn es (falsch) hat, tun wir nichts, aber wenn nicht, führen wir Folgendes aus Aktionen,..
• && (p[c.start+"-"+c.end] = true, p.result.push(c)); return p; OK die ersten && Beziehungen die beiden in den Pars Anweisungen der vorherigen Anweisung an die Bedingung wahr zu bewerten in a && b JS Motor Anweisung wird b nur bewerten, wenn a true ergibt also Sie es.. Wiederum in menschlicher Hinsicht ist dies der Fall. "Ist es wahr, dass Sie keine String-Eigenschaft wie" 1-2 "oder" 2-1 "haben und wir eine Eigenschaft" 1-2 "mit einem Wert true erzeugen . Wenn wir also in den nächsten Runden ein 1-2 oder 2-1 treffen, werden wir gar nichts tun. Dann schieben wir dieses aktuelle Objekt auf die Ergebniseigenschaft desselben Objekts (p.result), um ein eindeutiger Repräsentant aller seiner Duplikate oder Zwillinge zu werden. Dann geben wir für eine gesunde Fortsetzung der Reduktionszyklen zurück.

Ich hoffe, es ist klar.

Answer 4

Ich habe geschrieben, die Funktion unten, es zu tun ordentlich

var routeArr = [{ 
    start: 1, 
    end: 2 
}, { 
    start: 1, 
    end: 3 
}, { 
    start: 1, 
    end: 5 
}, { 
    start: 2, 
    end: 1 
}, { 
    start: 3, 
    end: 1 
}, { 
    start: 4, 
    end: 1 
}]; 

routeArr.IsDuplicate = function(obj) { 
    var i = this.length; 
    var count = 0 
    while (i--) { 
     if ((this[i].start === obj.start && this[i].end === obj.end) || (this[i].start === obj.end && this[i].end === obj.start)) { 
      count++; 
     } 
    } 
    return count>1; 
} 

for(var i = routeArr.length-1; i--;){ 
    if (routeArr.IsDuplicate(routeArr[i])) routeArr.splice(i, 1); 
} 

Answer 5

Ihre verschachtelte Schleife Methodik ist ‚ugly'- aber das ist nicht das Problem.

Ihre Implementierungsfehler resultieren aus der Tatsache, dass beide For-Schleifen davon ausgehen, dass sich die Array-Struktur nicht ändert, wenn Sie sie mutieren, was dazu führt, dass Sie einige Elemente im Array überspringen.

'i' und 'j' sind 'dumme' Inkrementierer - Die for-Schleife teilt dem Code nicht mit, dass er bei jeder Iteration zum nächsten Element im Array gehen soll. Er sagt also (array[last_index_i_used+1] spleiße etwas, das das Array, das du gerade betrachtest, ändert sich und das nächste Element in der Zeile wird übergeben.

Ich sehe viele phantastische Array-Methoden und ES6-Vorschläge, aber ich gehe von Ihrer Frage aus, dass Sie immer noch ein bisschen neu für JS sind und einige Zeit bauen können (nichts für ungut).

Versuchen Sie, eine rekursive Dekrementieren Funktion:

function uniquify(inputArray, ind){ 
    var checkStart = inputArray[ind].start, checkEnd =inputArray[ind].end 
    for (var i=(ind-1);i > -1; --i){ 
     var thisStart = inputArray[i].start, thisEnd = inputArray[i].end 
     if ((thisStart == checkStart || thisStart == checkEnd) && (thisEnd == checkStart || thisEnd == checkEnd)){ 

      inputArray.splice(i,1) 
     } 
    } 

    --ind 
    if (ind > -1){ 
     uniquify(inputArray,ind) 
    } 
} 
uniquify(routeArr,routeArr.length -1); 

Ich mag das besser als eine verschachtelte for-Schleife, wie Sie nie oft mehr den gleichen Wert schlagen sind, als Sie müssen, die unabhängig von der Größe konstante Leistung hält der Ihr Array.

Aber vielleicht möchten Sie sich fragen, ob "routeArr", was auch immer es tut, auf intelligente Weise tut - Im besten Fall verschwendet es Speicher und CPU, die Daten ineffizient speichern.