22
Jaka jest różnica między tymi dwoma algorytmami?Różnica między scipy.spatial.KDTree i scipy.spatial.cKDTree
A
Odpowiedz
22
cKDTree jest podzbiorem KDTree, prawdopodobnie zaimplementowanym w C, a więc szybszym.
Każdy z nich jest
binarny trie, której każdy z węzłów oznacza hyperrectangle osi wyrównany. Każdy węzeł określa oś i dzieli zbiór punktów na podstawie tego, czy ich współrzędne wzdłuż tej osi są większe lub mniejsze od określonej wartości.
ale KDTree
obsługuje również wszystkie zapytania-sąsiadów, zarówno z tablicami punktów i innymi KD-drzew. Te używają rozsądnie wydajnego algorytmu, ale drzewo kd niekoniecznie jest najlepszą strukturą danych dla tego rodzaju obliczeń.
7
W przypadku użycia (5D najbliższego sąsiada wyszukuje w KDTree z około 100K punktów) cKDTree jest około 12x szybciej niż KDTree.
Jestem zaskoczony, że nie jest to reklamowane w większym stopniu w dokumentach i artykułach KDTree. Dla mojego prostego (i prawdopodobnie powszechnego) przypadku znalezienia sąsiadów w 3D dla około 20 000 punktów, cKDTree było 40 razy szybsze. – python1981