Мне нужно сохранить значения, подобные следующим, в структуре данных,
id x y z
0 0.1 0.1 0.1
1 0.2 0.1 0.6
2 0.01 0.3 0.1
.....
Теперь мне нужно сопоставить двойные значения x, y, z и получить соответствующее значение id(int). Мне может понадобиться хранить около 400000 значений. Какую структуру данных следует использовать для эффективного поиска? Поставляется ли C++ с какими-либо встроенными структурами, которые будут поддерживать мое требование.
Если вас не интересует поиск по NN, вы можете использовать std::unordered_set. Однако вам нужно будет определить свою собственную хеш-функцию.
Вот (вероятно, ужасный) пример:
struct entry
{
int id;
double x, y, z;
// constructor if needed, etc...
};
struct entry_hasher
{
size_t operator()(const entry &e) const
{
std::hash<double> h;
return h(e.x) ^ (h(e.y) << 1) ^ (h(e.z) << 2);
}
};
std::unordered_set<entry, entry_hasher> entries;
В противном случае стандарт не предоставляет контейнеры, способные выполнять геометрические запросы (например, NN).
Возможно, это плохие новости для вас, но я думаю, что для ваших целей лучше всего подходит дерево kd и не реализовано в стандартной библиотеке.
Эта структура данных позволяет вам искать ближайшего соседа к любой заданной точке в многомерном пространстве (в вашем случае в трехмерном пространстве). Это гарантирует устойчивость к ошибкам округления, которые наиболее вероятны при работе с ключами с плавающей запятой.
Тем не менее, эта DS очень популярна, и я уверен, что вы сможете найти ее онлайн-реализацию.
Если вам нужно только выполнить точный поиск, вам подойдет хэш-таблица (unordered_map). хороший выбор. Сделайте ключ tuple или структурой, а значение — идентификатором int.
Если вам нужно выполнить интервальный поиск (например, найти элемент, ближайший к x), и вы всегда выполняете поиск по x, y, z по порядку, вам понадобится упорядоченная структура данных. Упорядоченное дерево (карта) должно работать. Используйте три уровня вложенности map, чтобы вы могли выполнять поиск, выполняя по существу mymap[x][y][z] с любыми правилами интервалов, которые вы хотите применить.
Если вам нужен более сложный поиск, в котором вы можете начать с любых элементов, или поиск, в котором вы знаете только два последних элемента, тогда вам понадобится многомерная упорядоченная структура данных, которую можно использовать для разделения пространства мира измерений для логарифмического поиска. . Некоторые примеры: octtree или дерево kd. Насколько я могу судить, не существует стандартной библиотечной реализации дерева octtree/kd. Существует множество вариаций этого класса структуры данных, например, вы можете использовать список пропуска вместо дерева.
x и y одинаковы, а y и z одинаковы, то x и z одинаковы). И почти все входы с разницей менее трехкратной дельты одинаковы... и так далее.
- person ; 16.03.2015
double в небольшой набор вещей, с которыми вы можете выполнить точное сопоставление, — я говорю, что это вводит в заблуждение и сбивает с толку (если не совершенно неправильно), чтобы описать это как хеширование значений с плавающей запятой.
- person ; 16.03.2015
delta, тогда числам, достаточно большим, чтобы x + delta == x, вероятно, было разрешено собственное хеш-значение)
- person ; 16.03.2015
x соответствовал при поиске, например x или x + delta/2 или x - 17*delta/256 или .... Кроме того, начальные условия неплохие - они такие, какие есть. Что плохо, так это, например, пытаться применить алгоритм поиска точных совпадений, когда вашей целью является поиск приблизительных совпадений.
- person ; 16.03.2015
y, что abs(x-y) < threshold. Следовательно, выполнение поиска на основе применения хеш-функции к float данным — плохая идея, поскольку они основаны на поиске точных совпадений.
- person ; 16.03.2015
Вы можете использовать OcTree (http://en.wikipedia.org/wiki/Octree ). Это было бы быстрее и удобнее любого контейнера в std на основе бинарного дерева. Также вы не будете беспокоиться об индексных или хеш-функциях. Однако это займет больше памяти. Его можно использовать даже для поиска NN (ближайшие соседи). Другим вариантом является дерево Kd (http://en.wikipedia.org/wiki/K-d_tree). Оба не являются частью ЗППП. KdTree требует меньше памяти, чем OcTree, а иногда даже быстрее. Вы должны быть в состоянии найти хорошие реализации C++ OcTree или KdTree с помощью Google.
struct(скажем,foo), содержащий значенияx,yиz, а также необходимые предикаты. Затем используйтеstd::map<foo, int>; предполагая, что вашidможет быть представлен какint. Поиск будет O(log N). Единственное, с чем вам придется столкнуться, — это сравнение с плавающей запятой, но это зависит от того, как возникают значения-кандидаты дляx,yиz. - person Bathsheba schedule 16.03.2015doubles? Возможные ответы будут сильно отличаться, если вы используетеoperator==вместо чего-то вродеabs(x-y) < thresholdили чего-то еще. - person schedule 16.03.2015