Разница между scipy.spatial.KDTree и scipy.spatial.cKDTree

Question

В чем разница между этими двумя алгоритмами?

Answer 1

cKDTree - это подмножество KDTree, реализованное на C++, обернутое в Cython, поэтому быстрее.

Каждый из них

двоичный файл, каждый из узлов которого представляет собой выровненный по оси гипергранук. Каждый узел задает ось и разделяет набор точек на основе того, больше или меньше их координата вдоль этой оси, чем определенное значение.

но KDTree

также поддерживает запросы всех соседей, как с массивами точек, так и с другими kd-деревьями. Они действительно используют достаточно эффективный алгоритм, но kd-дерево не обязательно является лучшей структурой данных для такого рода расчетов.

Answer 2

В случае использования (поиск ближайшего соседа 5D в KDTree с приблизительно 100K точками) cKDTree примерно в 12 раз быстрее, чем KDTree.

Answer 3

Обновление 2022: cKDTree устарело

В текущей (v1.8) документации SciPy указано, что теперь устарел и был заменен функционально идентичным scipy.spatial.KDTree.

scipy.spatial.cKDTreeВот примечание:

cKDTree функционально идентичен KDTree. До SciPy v1.6.0 cKDTree имел лучшую производительность и немного другую функциональность, но теперь эти два имени существуют только по причинам обратной совместимости. Если совместимость с SciPy < 1.6 не вызывает беспокойства, отдайте предпочтение KDTree.

Answer 4

В настоящее время у обоих почти одинаковые API, и cKDTree быстрее чем KDTree. Итак, в ближайшее время разработчики SciPy планируют удалитьKDTree, а также cKDTree будет переименован в KDTree обратно совместимым способом.

Ссылка: Подробная дорожная карта SciPy - Справочное руководство SciPy v1.6.0.dev http://scipy.github.io/devdocs/roadmap-detailed.html