Запрос диапазона точек 2D-данных

Я работаю с огромным набором 2D-данных, и мне нужен запрос диапазона для каждой точки, возвращающий соседей в диапазоне в виде набора, который я уже протестировал, используя индекс с KD Tree form sk, но проблема в том, что он возвращает индекс как список и преобразование в набор занимает слишком много времени. Существует ли структура данных, которая возвращает точки из запроса диапазона в виде набора, а не в виде списка?


indexing spatial-index spatial-query kdtree range-query
person Felix Ha    schedule 27.05.2017    source источник
comment
Вы уверены, что создание набора из списка занимает слишком много времени? Вы говорите так, будто это занимает столько же или даже больше времени, чем сам запрос диапазона, в этом случае я подозреваю, что с вашим созданием набора что-то не так. Может быть, вы могли бы показать нам некоторые цифры времени? Кроме того, каждое пространственное дерево также должно будет внутренне добавлять точки результата в набор, так что это не может быть быстрее, чем когда вы выполняете итерацию по списку для создания набора...   -  person TilmannZ    schedule 28.05.2017
comment
на ваш вопрос здесь есть ответ stackoverflow.com/questions/44224696/ :)   -  person Felix Ha    schedule 30.05.2017
comment
Ну, ссылка говорит только о том, почему преобразование в набор занимает больше времени, чем преобразование в список. Мой вопрос заключался в том, действительно ли это узкое место, обычно запрос диапазона должен занимать больше времени, чем создание набора или списка. Кроме того, как я уже упоминал, если вы хотите набор, кто-то должен нести расходы по его созданию, будь то вы или KD-дерево, делающее это внутри...   -  person TilmannZ    schedule 31.05.2017

Ответы (1)


arrow_upward
1
arrow_downward

Результат изначально не является списком.

Получите исходный код k-d-дерева и измените его так, чтобы он напрямую записывался в набор, а не в список.

Но я очень сомневаюсь, что это решит вашу настоящую проблему. Преобразование небольшого списка в набор едва ли должно быть проблемой производительности... но вы используете python. Традиционный набор Python set() будет намного медленнее, чем массив numpy. Но не вините структуру данных в том, что она не использует медленный набор.

person Has QUIT--Anony-Mousse    schedule 12.07.2017