Контейнер данных для получения диапазона больших данных

Question

У меня есть 3D-объект, который имеет более 100000 точек, эти точки имеют значения id и x, y, z. Мне нужно найти идентификаторы точек определенного диапазона х, где значения y и z являются статическими.

например -

---- --- --- --- 
| Id | x | y | z | 
|----|---|---|---| 
| | | | | 

Если мне нужно найти идентификаторы точек между (х, у, г)

• p1 - 0,1, 0,23, 0,78
• p2 - 123,0, 0,23 , 0,78

Какой контейнер данных следует использовать для достижения этой эффективности?

Любая помощь была бы принята с благодарностью.

Answer 1

С 2 координаты всегда статична, вы можете сделать с помощью простого отсортированного массива для каждой координаты, или сбалансированный BST (или skip list/B+ tree/...), если вы также должны поддерживать эффективное добавление/удаление. (Думая об этом, список пропусков, вероятно, будет проще реализовать, просто найдите первую точку в диапазоне и повторите, пока вы не выйдете из диапазона).

Это займет O(logN) для запроса (если вам нужны реальные моменты его O(logN+k), где k являются точками), и O(NlogN) инициализации.

Таким образом, алгоритм будет:

1. Определить, не входящих в статической точки
2. Эффективный поиск для «Низшая» точки в диапазоне
3. Эффективный поиск «Самый большой» точки в диапазоне
4. Верните все точки между ними.

Сложность 2 +-O(logN) и 4 является O(k), где k этим число точек, возвращенных (он не может быть предотвращена, если вам необходим фактической точка, а не конкретная агрегацией них).