[algorithm] Milioni di punti 3D: come trovare i 10 più vicini a un dato punto?


Answers

Se le milioni di voci sono già in un file, non è necessario caricarle tutte in una struttura dati in memoria. Mantieni un array con i dieci punti migliori trovati finora e analizza i milioni di punti, aggiornando la tua lista dei primi dieci man mano che procedi.

Questo è O (n) nel numero di punti.

Question

Un punto in 3-d è definito da (x, y, z). La distanza d tra due punti qualsiasi (X, Y, Z) e (x, y, z) è d = Sqrt [(Xx) ^ 2 + (Yy) ^ 2 + (Zz) ^ 2]. Ora ci sono un milione di voci in un file, ogni voce è un punto nello spazio, in nessun ordine specifico. Dato qualsiasi punto (a, b, c) trova i 10 punti più vicini ad esso. Come memorizzerai il milione di punti e come recupereresti quei 10 punti da quella struttura dati.




Penso che questa sia una domanda complicata che mette alla prova se non cerchi di strafare.

Considera l'algoritmo più semplice che le persone hanno già dato in precedenza: tieni un tavolo con dieci candidati migliori e passa attraverso tutti i punti uno per uno. Se trovi un punto più vicino di uno dei dieci meglio-così-lontano, sostituiscilo. Qual è la complessità? Bene, dobbiamo esaminare ogni punto dal file una volta , calcolare la sua distanza (o il quadrato della distanza effettiva) e confrontarlo con il decimo punto più vicino. Se è meglio, inseriscilo nella posizione appropriata nella tabella 10-meglio-così-lontano.

Allora, qual è la complessità? Guardiamo ogni punto una volta, quindi sono n calcoli della distanza e n confronti. Se il punto è migliore, dobbiamo inserirlo nella giusta posizione, questo richiede ulteriori confronti, ma è un fattore costante poiché la tabella dei migliori candidati ha una dimensione costante 10.

Finiamo con un algoritmo che viene eseguito in tempo lineare, O (n) nel numero di punti.

Ma ora considera quale è il limite inferiore su un tale algoritmo? Se non vi è alcun ordine nei dati di input, dobbiamo esaminare ciascun punto per vedere se non è uno dei più vicini. Quindi, per quanto posso vedere, il limite inferiore è Omega (n) e quindi l'algoritmo di cui sopra è ottimale.




Questa non è una domanda a casa, vero? ;-)

Il mio pensiero: iterare su tutti i punti e metterli in un ammasso minimo o in una coda di priorità limitata, in base alla distanza dal bersaglio.




Calcola la distanza per ognuno di essi e seleziona (1..10, n) in O (n). Quello sarebbe l'algoritmo ingenuo che immagino.




Algoritmo semplice:

Memorizza i punti come un elenco di tuple e scansiona sopra i punti, calcolando la distanza e mantenendo un elenco "più vicino".

Più creativo:

Raggruppa i punti in regioni (come il cubo descritto da "0,0,0" a "50,50,50" o "0,0,0" a "-20, -20, -20"), quindi può "indicizzare" in loro dal punto di destinazione. Controlla in quale cubo si trova il bersaglio e cerca solo tra i punti di quel cubo. Se ci sono meno di 10 punti in quel cubo, controlla i cubi "vicini" e così via.

Inoltre, questo non è un algoritmo molto valido: se il tuo obiettivo è più vicino al muro di un cubo di 10 punti, dovrai cercare anche nel cubo vicino.

Vorrei andare con l'approccio kd-tree e trovare il più vicino, quindi rimuovere (o contrassegnare) quel nodo più vicino e cercare nuovamente il nuovo nodo più vicino. Risciacqua e ripeti.




fondamentalmente una combinazione delle prime due risposte sopra di me. poiché i punti sono in un file non è necessario tenerli in memoria. Invece di un array o un heap minimo, utilizzerei un heap massimo, dal momento che si desidera controllare solo le distanze inferiori al decimo punto più vicino. Per un array, è necessario confrontare ogni distanza appena calcolata con tutte e 10 le distanze che hai mantenuto. Per un heap minimo, devi eseguire 3 confronti con ogni nuova distanza calcolata. Con un heap massimo, si esegue solo un confronto quando la distanza appena calcolata è maggiore del nodo radice.




Related