Лучший алгоритм для поиска ключа в диапазоне от хеш-таблицы

проблема

Из ниже списка элементов мне нужно будет получить доступ к элементу, указав диапазон ключей с заданным значением, например, скажем, если значение равно 2.1.1, которое находится в градусах, минутах и секундах Мне нужно найти ключ 0.0.0-30.0.0 высокая производительность.

key: 0.0.0-30.0.0   value: x-y-z
key: 30.0.0-60.0.0  value: y-x-z
key: 60.0.0-90.0.0  value: z-y-z

Решение1: Ниже решений, которые я пытался до сих пор

воссоздайте новый файл key/value (json), как показано ниже

key: 0.0.0  value: x-y-z
key: 0.0.1  value: x-y-z
.
key: 0.0.59 value: x-y-z
.
key: 0.1.0 value x-y-z
key: 0.1.1 value x-y-z

key: 30.0.0  value: y-x-z
.
.
key: 30.0.59 value: y-x-z
.
key: 30.1.0 value: y-x-z
key: 30.1.1 value: y-x-z
key: 30.1.2 value: y-x-z
.
.
key: 30.1.59 value: y-x-z
key: 30.2.0 value: y-x-z
key: 30.2.1 value: y-x-z
key: 30-2.3 value: y-x-z
.
.
key: 60.0.0 value: z-y-x
key: 60.0.1 value: z-y-x
key: 60.0.2 value: z-y-x
.
.
key: 60.0.59 value: z-y-x
key: 60.1.0 value: z-y-x
key: 60.1.1 value: z-y-x
.
.

Проблема (ы) Проблема с вышеупомянутым решением - размер файла будет увеличен, что вызывает переполнение кучи в моем компактном приложении

Solution2

?

Ответ 1

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

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

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

"синтаксический анализ из DMS" является неопределенным, но я предполагаю, что вы имеете в виду, что у вас есть текстовое представление ключа, такого как "2.1.1", входящего в вашу программу: почти наверняка лучше разобрать это, чем выполнять поиск с использованием текста сравнения. Чтобы разобрать текст в стиле "C++", вы можете просто использовать...

std::istringstream iss(the_incoming_key);
int degree, minute, second;
char c1, c2;
if (iss >> degree >> c1 >> minute >> c2 >> seconds &&
    c1 == '.' && c2 == '.')
{
    // have parsed a valid key...
}
else
    error_throw_exit_whatever();

Если вы были готовы использовать более старую функцию C для дополнительной скорости, подумайте:

if (sscanf(the_incoming_key.c_str(), "%d.%d.%d", &degree, &minute, &second) == 3)
    // have parsed a valid key...

Разработав ключ, вы могли бы разумно:

1) имеют std::map<tuple<int8_t, int8_t, int8_t>, Value> values; и двоичный поиск с помощью std::make_tuple(degree, minute, second) или

2) имеют значения std::map<int, Value> values; и двоичный поиск со degree * 3600 + minute * 60 + second - общее количество секунд, которое может быть или не быть быстрее для вашего компьютера для сравнения.

а. Умножение немного медленное, поэтому, чтобы избежать его, может быть использовано (degree << 12) + (minute << 6) + second, поскольку шести бит более чем достаточно для хранения значений от 0 до 59.

Конечно, любое преобразование, которое вы делаете для создания ключа, должно быть использовано ранее при анализе json файла и заполнении таблицы.

Для еще большей оптимизации вы можете иметь массив из 360 карт и индексировать на конкретную карту, на которой вы хотите найти минуты и секунды. Можно ожидать, что разделение пространства поиска на 360 приведет к устранению 8 или 9 сравнений, как и при каждом поиске карты (так как каждое сравнение уменьшает количество элементов, все еще находящихся в конфликте, а 360 - между 2 ^ 8 и 2 ^ 9).

Ответ 2

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

В первом списке я проанализирую входное значение как 3 ints. Для этого нам нужна только первая часть ввода (степень). И тогда мы получим такую позицию:

 int position = input_degree / step_size;

step_size будет 30 с вашим первым списком.

Если вам нужен ключ, вы можете сгенерировать его сейчас, используя позицию:

String key_begin = position * step_size;
String search_key = key_begin + ".0.0-" + key_begin+step_size + ".0.0";

Ответ 3

Используйте структуры данных KD-дерева или R-дерева вместо хеш-карт.