Ordinamento di un array in base all'ordine di un altro array, rapidamente [chiuso]

Question

Ordinamento di un array in base all'ordine di un altro array, rapidamente [chiuso]

#1 da (3 voti)

-1

Ci sono due matrici di mappe. Il primo array contiene mappe di valori ID in un ordine specifico (ma non necessariamente in puro ordine ASC o DESC):

// pseudo code
first := [
    {"id": 1},
    {"id": 2},
    {"id": 3}
]

... e una matrice di dati non ordinata con valori ID corrispondenti, ma non nello stesso ordine:

second := [
    {"id": 3, "text": "hello"},
    {"id": 1, "text": "fizz"},
    {"id": 2, "text": "bar"}
]

Come posso ordinare l'array second in modo che le sue mappe siano nello stesso ordine dell'array first tramite i valori ID corrispondenti, ottenendo al contempo l'esecuzione del codice più veloce possibile?

(Si noti che l'ordinamento dell'array first non è noto prima del runtime.)

Il risultato desiderato in questo caso sarebbe:

desiredResult := [
    {"id": 1, "text": "fizz"},
    {"id": 2, "text": "bar"},
    {"id": 3, "text": "hello"}
]

algorithms optimization golang

posta Curtis La Graff 04.12.2015 - 20:12

fonte

1 risposta

Leggi altre domande sui tag algorithms optimization golang

Come selezionare i team con la differenza minima tra i livelli di conoscenza Qual è la differenza tra dimensione e lunghezza? [chiuso]

score 3 · Answer 1

assumerò che nel caso generale questi ID potrebbero essere stringhe e potrebbero essere in un ordine non naturale in first e second , poiché altrimenti le soluzioni banali suggerite nei commenti sarebbero adeguate .

One obvious solution is to walk through the lists linearly, rearranging the second array's elements along the way.

Suppongo che questo significhi che per ogni elemento in first , fai una ricerca lineare in second per l'elemento corrispondente e quindi inseriscila nella giusta posizione in result . Questo sarebbe un algoritmo O (n ^ 2).

Credo che puoi farlo in O (n) convertendo first in una mappa da id a indice. Quindi, presumendo iniziamo con questo (scriverò Javascript poiché sono migliore in quella lingua, ma presumo che funzioni anche in Go):

var first = [
  { "id": "biz" },
  { "id": "qux" },
  { "id": "foo" }
]

var second = [
  { "id": "foo", "text": "dabra" },
  { "id": "biz", "text": "abra" },
  { "id": "qux", "text": "ca" }
]

Vorrei scorrere oltre first per costruire questa mappa da id a posizioni nell'array finale:

var idToPositionMap = {
  "biz": 0,
  "qux": 1,
  "foo": 2
}

Quindi eseguirò l'iterazione su second , usando le ricerche in quella mappa per inserire elementi nell'array dei risultati:

second.map(function(item) {
   result[idToPositionMap[item.id]] = item;
});

Entrambi questi passaggi dovrebbero essere O (n), assumendo la ricerca con chiave è O (1) e iterando su un array è O (n), come dovrebbero essere, quindi il tempo totale è O (2n) = O (n ).

Sono abbastanza sicuro che O (n) è la migliore complessità temporale possibile per questa operazione, dal momento che è necessario toccare ogni elemento di ogni array, quindi qualsiasi ulteriore ottimizzazione dovrebbe coinvolgere dettagli specifici della lingua e probabilmente un sacco di profilazione.