Ich arbeite mit 3D Pointcloud von Lidar. Die Punkte werden durch ein numpy-Array angegeben, das folgendermaßen aussieht:
points = np.array([[61651921, 416326074, 39805], [61605255, 416360555, 41124], [61664810, 416313743, 39900], [61664837, 416313749, 39910], [61674456, 416316663, 39503], [61651933, 416326074, 39802], [61679969, 416318049, 39500], [61674494, 416316677, 39508], [61651908, 416326079, 39800], [61651908, 416326087, 39802], [61664845, 416313738, 39913], [61674480, 416316668, 39503], [61679996, 416318047, 39510], [61605290, 416360572, 41118], [61605270, 416360565, 41122], [61683939, 416313004, 41052], [61683936, 416313033, 41060], [61679976, 416318044, 39509], [61605279, 416360555, 41109], [61664837, 416313739, 39915], [61674487, 416316666, 39505], [61679961, 416318035, 39503], [61683943, 416313004, 41054], [61683930, 416313042, 41059]])
Ich möchte meine Daten in Würfel mit einer Größe gruppieren, 50*50*50
damit jeder Würfel einige Hash-Indizes und Numpy-Indizes meiner points
enthaltenen Würfel beibehält . Um eine Aufteilung zu erhalten, ordne ich folgende cubes = points \\ 50
Ausgänge zu:
cubes = np.array([[1233038, 8326521, 796], [1232105, 8327211, 822], [1233296, 8326274, 798], [1233296, 8326274, 798], [1233489, 8326333, 790], [1233038, 8326521, 796], [1233599, 8326360, 790], [1233489, 8326333, 790], [1233038, 8326521, 796], [1233038, 8326521, 796], [1233296, 8326274, 798], [1233489, 8326333, 790], [1233599, 8326360, 790], [1232105, 8327211, 822], [1232105, 8327211, 822], [1233678, 8326260, 821], [1233678, 8326260, 821], [1233599, 8326360, 790], [1232105, 8327211, 822], [1233296, 8326274, 798], [1233489, 8326333, 790], [1233599, 8326360, 790], [1233678, 8326260, 821], [1233678, 8326260, 821]])
Meine gewünschte Ausgabe sieht folgendermaßen aus:
{(1232105, 8327211, 822): [1, 13, 14, 18]),
(1233038, 8326521, 796): [0, 5, 8, 9],
(1233296, 8326274, 798): [2, 3, 10, 19],
(1233489, 8326333, 790): [4, 7, 11, 20],
(1233599, 8326360, 790): [6, 12, 17, 21],
(1233678, 8326260, 821): [15, 16, 22, 23]}
Meine echte Punktwolke enthält bis zu einige hundert Millionen 3D-Punkte. Was ist der schnellste Weg, um diese Art der Gruppierung durchzuführen?
Ich habe die meisten verschiedenen Lösungen ausprobiert. Hier ist ein Vergleich der Zeitaufnahme unter der Annahme, dass die Größe der Punkte etwa 20 Millionen und die Größe der einzelnen Würfel etwa 1 Million beträgt:
Pandas [Tupel (elem) -> np.array (dtype = int64)]
import pandas as pd
print(pd.DataFrame(cubes).groupby([0,1,2]).indices)
#takes 9sec
Defauldict [elem.tobytes () oder Tupel -> Liste]
#thanks @abc:
result = defaultdict(list)
for idx, elem in enumerate(cubes):
result[elem.tobytes()].append(idx) # takes 20.5sec
# result[elem[0], elem[1], elem[2]].append(idx) #takes 27sec
# result[tuple(elem)].append(idx) # takes 50sec
numpy_indexed [int -> np.array]
# thanks @Eelco Hoogendoorn for his library
values = npi.group_by(cubes).split(np.arange(len(cubes)))
result = dict(enumerate(values))
# takes 9.8sec
Pandas + Dimensionsreduktion [int -> np.array (dtype = int64)]
# thanks @Divakar for showing numexpr library:
import numexpr as ne
def dimensionality_reduction(cubes):
#cubes = cubes - np.min(cubes, axis=0) #in case some coords are negative
cubes = cubes.astype(np.int64)
s0, s1 = cubes[:,0].max()+1, cubes[:,1].max()+1
d = {'s0':s0,'s1':s1,'c0':cubes[:,0],'c1':cubes[:,1],'c2':cubes[:,2]}
c1D = ne.evaluate('c0+c1*s0+c2*s0*s1',d)
return c1D
cubes = dimensionality_reduction(cubes)
result = pd.DataFrame(cubes).groupby([0]).indices
# takes 2.5 seconds
Es ist möglich , zum Download - cubes.npz
Datei hier und einen Befehl
cubes = np.load('cubes.npz')['array']
um die Leistungszeit zu überprüfen.
numpy_indexed
nähert sich auch nur. Ich denke es ist richtig. Ich verwendepandas
derzeit für meine Klassifizierungsprozesse.Antworten:
Konstante Anzahl von Indizes pro Gruppe
Ansatz Nr. 1
Wir können auftreten
dimensionality-reduction
, umcubes
auf ein 1D-Array zu reduzieren . Dies basiert auf einer Abbildung der gegebenen Würfeldaten auf ein n-dim-Gitter, um die im Detail diskutierten linearen Indexäquivalente zu berechnenhere
. Basierend auf der Eindeutigkeit dieser linearen Indizes können wir dann eindeutige Gruppen und ihre entsprechenden Indizes trennen. Wenn wir diesen Strategien folgen, hätten wir eine Lösung wie diese -Alternative Nr. 1: Wenn die ganzzahligen Werte in
cubes
zu groß sind, möchten wir dies möglicherweise so tundimensionality-reduction
, dass die Dimensionen mit kürzerer Ausdehnung als primäre Achsen ausgewählt werden. Daher können wir für diese Fälle den Reduktionsschritt modifizieren, um Folgendes zu erhaltenc1D
:Ansatz Nr. 2
Als nächstes können wir verwenden
Cython-powered kd-tree
schnelle Suche nach dem nächsten Nachbarn verwenden, um die nächsten Nachbarindizes zu erhalten und damit unseren Fall wie folgt zu lösen:Allgemeiner Fall: Variable Anzahl von Indizes pro Gruppe
Wir werden die argsort-basierte Methode mit einigen Aufteilungen erweitern, um die gewünschte Ausgabe zu erhalten.
Verwenden von 1D-Versionen von Gruppen
cubes
als SchlüsselWir werden die zuvor aufgeführte Methode um die Gruppen von
cubes
als Schlüssel erweitern, um den Prozess der Wörterbucherstellung zu vereinfachen und sie auch so effizient zu gestalten.Als nächstes werden wir nutzen
numba
Paket verwenden, um zu iterieren und zur endgültigen Ausgabe des Hashable-Wörterbuchs zu gelangen. Dazu gibt es zwei Lösungen: Eine, bei der die Schlüssel und Werte separat verwendet werden,numba
und der Hauptaufruf werden komprimiert und in Dikt konvertiert, während die andere einennumba-supported
Diktat-Typ erstellt und somit keine zusätzliche Arbeit für die Hauptaufruffunktion erforderlich ist .Wir hätten also die erste
numba
Lösung:Und zweite
numba
Lösung als:Timings mit
cubes.npz
Daten -Alternative Nr. 1: Wir können eine weitere Beschleunigung erzielen, indem
numexpr
große Arraysc1D
wie folgt berechnet werden -Dies gilt für alle erforderlichen Stellen
c1D
.quelle
dtypes
int32
undint64
number of indices per group would be a constant number
dass ich die Kommentare gesammelt habe. Wäre das eine sichere Annahme? Testen Sie auchcubes.npz
die Ausgabe von915791
?cubes.npz
nur von und es war983234
für die anderen Ansätze, die ich vorgeschlagen habe.Approach #3
nach dem generischen Fall einer variablen Anzahl von Indizes.Sie können einfach iterieren und den Index jedes Elements zur entsprechenden Liste hinzufügen.
Die Laufzeit kann weiter verbessert werden, indem tobytes () verwendet wird, anstatt den Schlüssel in ein Tupel zu konvertieren.
quelle
res[tuple(elem)].append(idx)
dauerte 50 Sekunden gegenüber seiner Ausgabe,res[elem[0], elem[1], elem[2]].append(idx)
die 30 Sekunden dauerte.Sie könnten Cython verwenden:
Aber es wird Sie nicht schneller machen als das, was Pandas tut, obwohl es danach das schnellste ist (und vielleicht die
numpy_index
basierte Lösung) und nicht mit der Speicherstrafe verbunden ist. Eine Sammlung der bisher vorgeschlagenen Vorschläge finden Sie hier .Auf dem OP-Computer sollte die Ausführungszeit ungefähr 12 Sekunden betragen.
quelle