Структура данных для индексирования кортежа

Question

Мне нужна структура данных, в которой хранятся кортежи, и позволит мне выполнить запрос, например: заданный кортеж (x,y,z) целых чисел, найти следующий (увеличенная граница для него). Под этим я подразумеваю рассмотрение естественного порядка (a,b,c)<=(d,e,f) <=> a<=d and b<=e and c<=f. Я попробовал сортировку MSD radix, которая разбивает элементы на ведра и сортирует их (и делает это рекурсивно для всех позиций в кортежах). Есть ли у кого-нибудь другое предложение? В идеале я хотел бы, чтобы запрос abouve выполнялся внутри O (log n), где n - количество кортежей.

Answer 1

Два варианта.

Используйте двоичный поиск по отсортированному массиву. Если вы построите ключи (при условии 32bit int) 'с (a < < 64) | (b < 32) | c и удерживайте их в простом массиве, упакованном один рядом с другим, вы можете использовать бинарный поиск, чтобы найти значение вы ищете (если используете C, для этого есть даже функция библиотеки), а следующая - просто одна позиция. Худший случай Производительность - O (logN), и если вы можете сделать http://en.wikipedia.org/wiki/Interpolation_search, то вы можете даже приблизиться к O (log log N)

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

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

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

Я также вижу, что у вас был аналогичный вопрос по этим строкам, поэтому я думаю, что кишки того, что я говорю, объединяют A, b, c, чтобы создать один длинный ключ и использовать его с бинарным поиском, хэшем или даже б-дерево. Если длина ключа - ваша проблема (какой язык), можете ли вы рассматривать ее как строку?

Если этот ответ полностью отключен, сообщите мне, и я увижу, могу ли я удалить этот ответ, поэтому вопросы остаются без ответа, а не бесполезным ответом.