Rimozione oggetti equivalenti ma unici da un array JavaScript

Question

Ho un array di oggetti simili alle seguenti:

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

Questi oggetti rappresentano il punto di inizio e fine delle righe e, come tale, {start: 1, end: 2} e {start: 2, end: 1} rappresentano la stessa linea.

Sto cercando di rimuovere tutte le linee duplicate dalla matrice e non riesce a trovare un modo efficace o elegante per farlo. Ho provato un ciclo annidato ma, mi è stato detto che è una cattiva pratica (e sto ricevendo errori con la mia implementazione, ed è solo brutto).

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

Qualcuno può offrire suggerimenti?

Answer 1

Creare un oggetto/mappa in javascript e mantenere gli indici degli oggetti univoci, memorizzare "min (inizio, fine): max (inizio, fine)" come chiave e indice come valore. Ecco un'implementazione della vostra domanda 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

Ecco una soluzione generale al problema della rimozione dei valori duplicati da array javascript:

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

applicati sulla data routeArr:

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

Si può fare in questo modo. Immagino che questo sia molto veloce poiché non ci sono ricerche. Un'operazione Array.prototype.reduce() per costruire contemporaneamente la tabella hash (tabella di ricerca) e l'oggetto ridotto. Quindi mappare le chiavi dell'oggetto per ottenere il risultato. Ecco qui;

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

Ebbene dare una seconda riflessione ho eliminato la porzione ridondante Object.keys(). Ora, questo non è altro che un singolo Array.prototype.reduce() pass completato nel solo O (n). Suppongo che questo potrebbe essere il massimo delle prestazioni. Controlla.

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

Ebbene sì ok Sono d'accordo sembra un po 'criptico, ma è molto semplice.

• Stiamo utilizzando il metodo Array.prototype.reduce() con un valore iniziale qui. Questo è il nostro valore iniziale {"result":[]}. Quando riduciamo il nostro array routeArr, il nostro elemento iniziale con cui iniziare è ora un oggetto con una singola proprietà denominata risultato e valore di una matrice vuota.
• riduzione è stato fornito con una funzione di callback anonimo che accetta due argomenti (p,c)p sta per precedente e c sta per corrente. Quindi, nella prima esecuzione, p è il nostro oggetto di inizializzazione, voglio dire che questo {"result":[]} e c è l'elemento nell'indice 0 dell'array (routeArr) che abbiamo chiamato riduci. Quindi nel primo turno c è {start: 1, end: 2}.
• All'inizio di ogni round controlliamo se l'oggetto p contiene una proprietà che rappresenta i valori degli elementi correnti in entrambi gli ordini. Quindi il controllo arriva come questo !(p[c.start+"-"+c.end] || p[c.end+"-"+c.start]) che in termini umani significa "è vero che non hai una proprietà stringa come c.start-c.end o c.end-c.start". Quindi per esempio nella prima round the check è come "è vero che non hai una proprietà stringa come" 1-2 "o" 2-1 ". Se ha (false) non facciamo nulla ma se non lo è, eseguiamo il seguente azioni,..
• && (p[c.start+"-"+c.end] = true, p.result.push(c)); return p; OK primi && lega le due istruzioni nelle parentesi alla condizione dell'istruzione precedente per valutare a true nel motore JS a && b istruzioni valuteranno solo b se a viene valutata a true Così avete ottenuto.. Ancora una volta in termini umani questo è ciò che accade ". È vero che non hai una proprietà stringa come" 1-2 "o" 2-1 "diventa vero e creiamo una proprietà" 1-2 "con un valore true . Quindi nei prossimi turni se incontriamo un 1-2 o un 2-1 non faremo nulla. Quindi spostiamo questo oggetto corrente nella proprietà result dello stesso oggetto (p.result) per diventare un rappresentante unico di tutti i suoi duplicati o gemelli. Quindi restituiamo p per una buona continuazione dei cicli di riduzione.

Spero sia chiaro.

Answer 4

ho scritto la funzione qui sotto per farlo ordinatamente

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

vostra metodologia ciclo nidificato è 'ugly'- ma che non è il problema.

Gli errori di implementazione derivano dal fatto che entrambi i cicli for presuppongono che la struttura dell'array non cambierà mentre la si sta modificando, causando la possibilità di saltare alcuni elementi dell'array.

"i" e "j" sono incrementi "stupidi" - Quel ciclo for non indica al codice di passare all'elemento successivo nell'array con ogni iterazione, lo dice per andare a (array[last_index_i_used+1] - Quindi quando si unire qualcosa alla matrice che stai osservando cambia, e il prossimo elemento in linea viene passato sopra.

Vedo un sacco di fantastici metodi di array e suggerimenti ES6, ma dalla tua domanda presumo che tu sia ancora un po 'nuovo a JS, e potresti usare alcuni elementi fondamentali per la costruzione del tempo (senza offesa intesa).

Prova una funzione di decremento ricorsiva:

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

mi piace che meglio di un nidificato ciclo for come si sono mai colpendo lo stesso valore più spesso di quanto è necessario, che mantiene prestazioni costanti indipendentemente dalle dimensioni di il tuo array.

Ma potreste chiedervi se qualunque cosa stia definendo 'routeArr' sta facendo tutto ciò che sta facendo in un modo che è intelligente - nel migliore dei casi, sembra che sprechi memoria e CPU che memorizzano i dati in modo inefficiente.