Ho una domanda sull'efficienza di un algoritmo:
Hai una lista di x, y punti
Ora voglio ottenere tutti i punti che sono fino a 5 unità di distanza da un riferimento x, punto y
Come si calcola nel modo più efficiente?
Vado sopra ogni punto e calcola la distanza, e se quella distanza è inferiore a 5, aggiungo alla risposta
Se sai come viene chiamato questo algoritmo, sarei felice se pubblichi anche questo.
Mentre non puoi evitare di dover controllare ogni punto, ci sono tecniche che puoi usare per controllare velocemente o controllare solo una volta.
Ad esempio, la maggior parte dei punti si può dire se sono troppo lontani senza calcolare la distanza esatta. Ad esempio, se ho un punto il cui componente x è 100 lontano dal punto di riferimento, non è necessario calcolare la distanza. Sai già che il punto è troppo lontano. Allo stesso modo se i delta xey sono inferiori a 5 * 2 * sqrt (2) di distanza dal punto di riferimento, sai che sono abbastanza vicini. Vedi lo schema seguente per un esempio visivo:
Se P è il tuo punto di origine e il cerchio rappresenta il punto più distante che un punto può essere dal punto P (nel tuo caso il raggio di 5 unità), allora A e C rappresentano i punti in cui i punti sono decisamente fuori o definitivamente dentro. Pertanto, è possibile ottimizzare il proprio algoritmo controllando i delta x e y. Solo i punti che si trovano nell'area grigia B devono calcolare la loro distanza perché non si può sapere senza eseguire un calcolo più sofisticato.
Inoltre, non sarebbe male per ordinare i tuoi punti per distanza a P. Se devi eseguire questo calcolo spesso, puoi ottimizzare il calcolo ordinando una volta, quindi trovare il punto più lontano entro 5 unità da P. A meno che le posizioni dei punti cambino , sai che tutti i punti dopo quel punto devono essere più vicini.
Spero che ti aiuti!
Questo è un problema comune e c'è esattamente una ottimizzazione nota per il caso one-shot: controlla se la distanza al quadrato è inferiore a 25. Questo ti risparmia una costosa chiamata% per% di punto co_de . La quadratura e l'aggiunta di coordinate sono quasi gratuite, rispetto al tempo necessario per recuperare i dati dalla memoria.
Se eseguirai ripetutamente questi test, dovresti essere in grado di migliorare in media le prestazioni O(N) tenendo i punti in un quadtree .
Fondamentalmente, un quadrilatero divide lo spazio 2D ricorsivamente in un "albero" di quadrati annidati (quadruple). Ogni quadrato può avere 4 quadrati nidificati, ma in genere si divide solo un quad se c'è qualcosa all'interno.
Dato una rappresentazione quadtree per la lista punti, puoi trovare tutti i punti entro 5 unità da un punto dato come segue:
L'accelerazione effettiva dipenderà dal raggruppamento dei punti e dalla granularità dei quadricipiti; vale a dire quando si interrompe la suddivisione.
Leggi altre domande sui tag algorithms efficiency