Wie kann ich die nächste Nachbarsuche mit Python beschleunigen?

Question

Ich habe einen Code, der das nächste Voxel (das nicht zugewiesen ist) zu einem Voxel (das zugewiesen ist) berechnet. Das heißt, ich habe eine Reihe von Voxeln, nur wenige Voxel haben bereits skalare (1,2,3,4 .... etc) Werte und wenige Voxel sind leer (sagen wir mal einen Wert von '0'). Dieser Code findet das nächste zugewiesene Voxel für ein nicht zugewiesenes Voxel und weist diesem Voxel den gleichen Skalar zu. Ein Voxel mit einem Skalar '0' erhält also einen Wert (1 oder 2 oder 3, ...) basierend auf dem nächsten Voxel. Dieser Code unten funktioniert, aber es dauert zu viel Zeit. Gibt es eine Alternative dazu? oder wenn Sie Feedback darüber haben, wie Sie es weiter verbessern können?

"" "# self.voxels ist ein 3D-numpy Array """

def fill_empty_voxel1(self,argx, argy, argz): 
""" where # argx, argy, argz are the voxel location where the voxel is zero""" 
    argx1, argy1, argz1 = np.where(self.voxels!=0) # find the non zero voxels 
    a = np.column_stack((argx1, argy1, argz1)) 
    b = np.column_stack((argx, argy, argz)) 
    tree = cKDTree(a, leafsize=a.shape[0]+1) 
    distances, ndx = tree.query(b, k=1, distance_upper_bound= self.mean) # self.mean is a mean radius search value 
    argx2, argy2, argz2 = a[ndx][:][:,0],a[ndx][:][:,1],a[ndx][:][:,2] 
    self.voxels[argx,argy,argz] = self.voxels[argx2,argy2,argz2] # update the voxel array 

Beispiel

"" "Hier ist ein kleines Beispiel mit kleiner Datenmenge: """

import numpy as np 
from scipy.spatial import cKDTree 
import timeit 

voxels = np.zeros((10,10,5), dtype=np.uint8) 
voxels[1:2,:,:] = 5. 
voxels[5:6,:,:] = 2. 
voxels[:,3:4,:] = 1. 
voxels[:,8:9,:] = 4. 
argx, argy, argz = np.where(voxels==0) 

tic=timeit.default_timer() 
argx1, argy1, argz1 = np.where(voxels!=0) # non zero voxels 
a = np.column_stack((argx1, argy1, argz1)) 
b = np.column_stack((argx, argy, argz)) 
tree = cKDTree(a, leafsize=a.shape[0]+1) 
distances, ndx = tree.query(b, k=1, distance_upper_bound= 5.) 
argx2, argy2, argz2 = a[ndx][:][:,0],a[ndx][:][:,1],a[ndx][:][:,2] 
voxels[argx,argy,argz] = voxels[argx2,argy2,argz2] 
toc=timeit.default_timer() 
timetaken = toc - tiC#elapsed time in seconds 
print '\nTime to fill empty voxels', timetaken 

zur Visualisierung:

from mayavi import mlab 
data = voxels.astype('float') 
scalar_field = mlab.pipeline.scalar_field(data) 
iso_surf = mlab.pipeline.iso_surface(scalar_field) 
surf = mlab.pipeline.surface(scalar_field) 
vol = mlab.pipeline.volume(scalar_field,vmin=0,vmax=data.max()) 
mlab.outline()  
mlab.show()  

Nein w, wenn ich die Dimension des Voxel-Arrays als etwas wie (500,500,500) habe, dann ist die Zeit, die benötigt wird, um die nächste Suche zu berechnen, nicht mehr effizient. Wie kann ich das überwinden? Könnte parallele Berechnung die Zeit reduzieren (ich habe keine Ahnung, ob ich den Code parallelisieren kann, wenn Sie das tun, lassen Sie es mich bitte wissen)?

Ein mögliches fix:

Ich konnte die Rechenzeit erheblich verbessern, indem die n_jobs Zugabe = -1 Parameter in der cKDTree Abfrage.

distances, ndx = tree.query(b, k=1, distance_upper_bound= 5., n_jobs=-1) 

I war in der Lage, die Abstände in weniger als eine Stunde für eine Anordnung von (400.100.100) auf einem 13-Core-CPU zu berechnen. Ich habe es mit 1 Prozessor versucht und es dauert ungefähr 18 Stunden, um das gleiche Array zu vervollständigen. Danke an @gsamaras für die Antwort!

Answer 1

Es wäre interessant sklearn.neighbors.NearestNeighbors zu versuchen, die n_jobs Parameter bietet:

Die Anzahl der parallelen Jobs für Nachbarn Suche auszuführen.

Dieses Paket enthält auch den Kugel-Tree-Algorithmus, die Sie gegenüber dem kd-Baum eines Test können aber meine Vermutung ist, dass der kd-Baum besser sein wird (aber das wieder auf Ihren Daten abhängt, so Forschung Das!).

---

Sie möchten vielleicht auch Dimensionsreduktion, verwenden, die einfach ist. Die Idee ist, dass Sie Ihre Dimensionen reduzieren, daher enthalten Ihre Daten weniger Informationen, so dass das Nearest Neighbour Problem viel schneller bewältigt werden kann. Natürlich gibt es hier einen Kompromiss, Genauigkeit!

Sie könnten/werden mit der Reduzierung der Dimensionalität weniger genau, aber es könnte sich lohnen. Dies gilt jedoch normalerweise in einem hochdimensionalen Raum und Sie sind nur in 3D. Also ich weiß nicht, ob für Ihren speziellen Fall es sinnvoll wäre, sklearn.decomposition.PCA zu verwenden.

---

Eine Bemerkung:

Wenn Sie wirklich obwohl hohe Leistung wollen, werden Sie es nicht mit python bekommen, Sie zu c++ wechseln könnte, und CGAL beispielsweise verwenden.

Answer 2

Sie wechseln nächsten Nachbarn (KNN) Algorithmen zur Annäherung, die in der Regel den Vorteil von anspruchsvollen Hashing oder Näherungs Graph Techniken Index schnell Ihre Daten nehmen und schnellere Abfragen durchführen. Ein Beispiel ist Spotifys Annoy. Stören Sie die README enthält this plot die Präzision Leistungs tradeoff Vergleich verschiedener ANN-Algorithmen in den letzten Jahren veröffentlicht wurde, zeigt. Der Top-Performance-Algorithmus hnsw hat eine Python-Implementierung unter Non-Metric Space Library (NMSLIB).