Come evitare di dover calcolare radici quadrate per ogni elemento in un set di dati?

Se non hai bisogno di sapere la esatta risposta, dovresti leggere questo articolo:

link (archive.org link per impedire il link rot )

In primo luogo, è chiaro dal documento che non c'è modo di farlo per ottenere una risposta esatta più veloce dell'approccio della forza bruta:

Our aim is beating the obvious algorithm that computes the exact value of the aforementioned average (by considering all pairs of points). But, unlike in the graph theoretic setting (cf. [4]), we cannot hope for approximation algorithms that run in time that is sub-linear in the number of points (because a single “exceptional” point may dominate the value of the average of all pairwise distances). Thus, we seek approximation algorithms that run in time that is almost linear in the number of points. We consider two algorithmic approaches.

Quindi hanno una risposta facile: invece di calcolare la distanza euclidea per tutte le coppie di punti, puoi ottenere un'approssimazione sqrt(d) calcolando la media delle distanze delle coordinate (sfortunatamente, Programmers.SE non ha MathJax quindi lo screenshot dovrà fare):

tl;drlinguaggiomatematico:fondamentalmentelaformulastasolodicendodiaggiungeretuttelecoppiedidistanzetralecoordinate.Adesempio,sqrt((x2-x1)^2+(y2-y1)^2)diventasolox2-x1+y2-y1elatuarispostasaràdisattivatasolodaunfattoresqrt(d),cheinquestocasoèsqrt(2).

Quindi,ildocumentocontinuaadiscuterediunalgoritmodicampionamentocasuale,cheèpiùaccurato.

Consiglio di leggere il documento per capire perché funziona, lo spiegano meglio di me.

1. cambia i dati di presentazione

Non salvare i quadrati ma le radici quadrate quando li inserisci, poiché a*a è più economico di sqrt(aa)

2. cache fissa

Suppongo che vengano usati solo numeri interi.

Se sai, ci sono molti duplicati, forse tra 1*1 e 1000*1000 e.g. che memorizzarli in una hashmap potrebbe accelerare il calcolo.

3. LRU-cache

Se sai che ci sono molti duplicati, allora una LRU-Cache potrebbe aiutarti.

4. approssimazione

Invece di usare sqrt potresti implementarlo tu stesso, ma solo con poche iterazioni.

Dipende da quanto esatta deve essere la tua media. Se c'è una grande disparità tra le dimensioni dei cubi puoi "ignorare" i cubetti più piccoli e non calcolare il loro sqrt e ottenere comunque una buona stima media:

(1000 + 1000 + 1000 + 0.001) / 4 = 750.00025

Ignora l'ultimo valore:

(1000 + 1000 + 1000 + 0) / 4 = 750 

C'è un modo per evitare di calcolare la radice quadrata per ogni elemento?

Assolutamente. Aumenta il valore alla potenza di ½.

Grande. È più veloce?

È una strada battuta , ma sfortunatamente Devo ancora trovare una lingua, una piattaforma o una CPU in cui l'implementazione di default di questo sia più efficiente.

Esistono vari algoritmi se vuoi eseguire il rollover.

Aitch ha proposto di usare una cache se hai numeri interi, ma hai affermato di avere i float. Una cache è comunque ancora possibile se:

• i punti la cui distanza si sta calcolando si trovano su una griglia (quindi l'insieme di valori probabili è piccolo)

- o -

• il valore risultante non richiede un'elevata precisione (nel qual caso è possibile utilizzare intervalli come chiavi nella cache).

Nel secondo caso, se si mantengono coppie (a²; b²) → (a; b) con a e b close, è anche possibile ottenere un limite inferiore e superiore in media, se ciò è utile per il cliente. (Sarebbe utile menzionare per che cosa è necessaria questa media)