Управление большим пространственным набором данных с атрибутами в переполнении стека
У меня есть набор данных с около 700 000 записей, и каждая запись представляет собой набор трехмерных координат с такими атрибутами, как имя, метка времени, идентификатор и т. Д.
Сейчас я просто читаю координаты и отображаю их как точки в OpenGL. Однако я хочу связать каждую точку с соответствующими ей атрибутами и хочу иметь возможность сортировать и выбирать их во время выполнения на основе их атрибутов. Как бы я мог добиться этого эффективным способом?
Я знаю, что могу поставить, я могу поместить данные в структуру и использовать сортировку stl для сортировки, но это хороший выбор дизайна или есть более эффективный / элегантный способ решения проблемы?
Решение
Я склоняюсь к тому, чтобы взглянуть на эти варианты дизайна, сначала используя один из стандартных контейнеров библиотеки (кстати, если вам нужно «просто» выполнить поиск, вам не обязательно сортировать, но вам нужен контейнер, который позволяет поиск) , затем проверьте, является ли это «достаточно эффективным» решением проблемы.
Обычно вы можете придумать индивидуальное решение, которое будет более эффективным и, возможно, более элегантным, но при этом вы можете столкнуться с двумя проблемами:
1) В конечном итоге вам придется реализовать некоторый тип контейнера, который будет стоить вам времени как на реализацию, так и на отладку по сравнению с хорошо понятым и протестированным контейнером, который уже существует. В большинстве случаев вам лучше пытаться решить проблему, а не увеличивать ее, добавляя больше кода.
2) Если кому-то еще придется поддерживать ваш код в какой-то момент, скорее всего, они знакомы со стандартными компонентами библиотеки как с точки зрения проектирования, так и с точки зрения реализации, но они не будут знакомы с вашим пользовательским контейнером, что увеличит кривую обучения.
Другие решения
Если вы рассматриваете каждый атрибут вашего точечного класса как компонент вектора, тогда ваш процесс выбора — это региональный запрос. Ваш пример строкового атрибута, равного чему-либо, означает, что регион на самом деле является строкой в вашем пространстве данных. Однако не будет никакой сортировки, выполненной для других атрибутов в пределах этого выбора, вы должны будете реализовать это самостоятельно, но это должно быть относительно простым для октодеревьев, которые разделяют данные в упорядоченных областях.
Как указано в другом ответе, сначала попробуйте существующие стандартные решения. Если вы можете найти готовую реализацию одной из этих структур данных:
- R-дерево
- КД дерево
- БСП
- Octree, или, более вероятно, n мерная версия принципа quadtree или octree (здесь я буду использовать термин octree для обозначения общей структуры данных)
затем пойти на это. Это структуры данных, которые я рекомендую для управления пространственными данными.
Вы также можете использовать встроенную RDBMS, способную работать с пространственными данными (они обычно реализуют R-дерево для пространственной индексации), но это может быть неинтересно, если ваш набор данных не является динамическим.
Если ваш набор данных попадает в диапазон 10000 записей, то, по сегодняшним меркам, он не такой большой, поэтому должно быть достаточно использования более простых структур. В этом периметре я бы пошел первым для простого std::vectorи использовать std::sort а также std::find фильтровать данные в меньшем наборе и сортировать их потом.
Я, вероятно, попробую упорядоченный набор или карту для наиболее запрашиваемого атрибута во второй попытке, а затем проведу несколько тестов, чтобы выбрать более эффективное решение.
Для более эффективного алгоритма одномерной индексации (по сути, это наборы и карты), вы можете попробовать B-деревья: есть реализация C ++, доступная в Google.
Моя третья попытка была бы направлена на решение OpenCL (хотя, если вы выполняете тяжелый рендеринг OpenGL, вы можете вместо этого предпочесть выполнять работу с процессором, но это зависит от ваших потребностей в частоте кадров).
Если ваш набор данных намного больше, чем кажется, рассмотрите одно из более сложных решений, которые я перечислил изначально.
В любом случае, без более подробной информации о вашем наборе данных и о том, как вы планируете его использовать, будет сложно найти хорошее решение, поэтому единственный реальный совет, который мы можем дать, это: попробуйте все, что вы можете и сравните.
Если вы имеете дело с облаками точек, взгляните на PCL, это может сэкономить вам много времени и усилий без необходимости разбираться в тонкостях пространственной индексации самостоятельно. Это также включает в себя визуализацию.