[Python] Distanza tra molti punti

[HaldoSax]

Buon giorno a tutti, dovrei fare un programma che mi calcoli la distanza tra 124845 punti, in un file di testo ho le loro coordinate (x,y,z). La prima cosa che mi è venuta in mente è quella di fare due cicli for:

Codice:

for i in range(1,124846):
             for j in range(1,124846):
                 if(j>i):
                     d.append(sqrt(pow((x[j]-x[i]),2)+pow((y[j]-y[i]),2)+pow((z[j]-z[i]),2)


In tal modo all'inizio è lento ma mano a mano che il tempo passa dovrebbe diventare più veloce, in quanto il numero di punti su cui deve calcolare la distanza diminuisce, l'unico problema è che in questo modo in tre giorni ha fatto solo 2100 iterazioni sul primo ciclo.
Qualcuno potrebbe suggerirmi un metodo alternativo per poter velocizzare il conto? perché ci sto sbattendo la testa da tre giorni e non riesco a venirne a capo.
Grazie in anticipo

[mathbells]

Dovrebbe essere sufficiente far partire l'indice j dal valore i+1 invece che da 1 (e l'indice i deve arrivare a 124844 invece che a 124845, e l'indice j deve arrivare a 124845)

[HaldoSax]

Adesso provo, grazie mathbells

[mathbells]

Naturalmente a questo punto ti puoi anche risparmiare il test

Codice:

if j>i

perché è sicuramente soddisfatto

[HaldoSax]

E' vero, in effetti mettendo quel ciclo if i tempi si allungano di molto, in quanto il secondo ciclo for riparte sempre dall'inizio. Adesso l'ho mandato in esecuzione e vedrò se i tempi si accorciano. Grazie ancora mathbells.

[HaldoSax]

mathbells grazie mille con alcune piccole modifiche, tipo non salvare in un array le distanze, adesso il programma calcola il tutto in una mezz'oretta. Grazie Grazie

[mathbells]

Di nulla!

[apatriarca]

Che versione di Python stai usando? Se stai usando Python 2 allora sarebbe meglio usare xrange al posto di range. Questo non è un problema se stai invece facendo uso di Python 3 in quando in questo caso non viene creata una lista con tutti i numeri nell'intervallo.

L'altro punto importante è quello già proposto da @mathbells di ridurre il numero di cicli di circa la metà (da \(n^2\) a \(\frac{n^2 + n}{2}\)). A questo punto è però necessario chiarire se sia effettivamente necessario calcolare tutti questi valori. Se non fosse necessario calcolarli tutti per risolvere il problema finale, si potrebbe ridurre ulteriormente il numero di cicli.

Altri punti potrebbero essere i seguenti:
1. A volte è possibile usare il quadrato della distanza invece della distanza risparmiando quindi una radice quadrata.
2. La moltiplicazione è normalmente molto più veloce della potenza. E' possibile che python faccia questa ottimizzazione per te, ma avrei scritto il codice calcolando le differenze lungo gli assi in variabili temporanee dx, dy, dz e poi calcolare la distanza come sqrt(dx*dx + dy*dy + dz*dz).
3. L'uso di numpy potrebbe aiutare parecchio in situazioni come queste.

[HaldoSax]

Ciao apatriarca, alla fine ho adottato C, perché non devo memorizzare le distanze ma mi servono solo per vedere in quale intervallo cadono. Quindi eliminando la memorizzazione delle distanze, confrontando subito gli intervalli e adottando il suggerimento di mathbells sono passato da tre giorni di calcolo non compiuto a meno di mezz'ora. Comunque grazie per il suggerimento sulla moltiplicazione, non lo sapevo. Grazie per i suggerimenti.