lookup — C ++ Сложная таблица поиска
У меня есть около 400.000 «предметов».
Каждый «элемент» состоит из 16 двойных значений.
Во время выполнения мне нужно сравнить элементы друг с другом. Поэтому я дублирую их двойные значения. Это довольно много времени.
Я провел несколько тестов и обнаружил, что существует только 40 000 возможных возвращаемых значений, независимо от того, какие элементы я сравниваю друг с другом.
Я хотел бы сохранить эти значения в справочной таблице, чтобы я мог легко получить их без каких-либо реальных вычислений во время выполнения.
Мой вопрос заключается в том, как эффективно хранить данные в справочной таблице.
Проблема в том, что если я создаю справочную таблицу, она становится невероятно огромной, например, так:
item-id, item-id, compare return value
1 1 499483,49834
1 2 -0.0928
1 3 499483,49834
(...)
Суммарно до 120 миллионов комбинаций.
Это выглядит слишком большим для реального приложения.
Но я не уверен, как этого избежать.
Кто-нибудь может поделиться некоторыми классными идеями?
Большое спасибо!
Решение
Предполагая, что я вас правильно понимаю, у вас есть два входа с возможностями 400K, поэтому 400K * 400K = 160B записей … при условии, что они были проиндексированы последовательно, и вы сохранили свои возможности 40K таким образом, что каждый из них по 2 октета, мы смотрим на таблицу размером примерно 300 ГБ … уверен, что это выходит за рамки современных ежедневных вычислений. Таким образом, вместо этого вы могли бы исследовать, есть ли какая-либо корреляция между «элементами» 400 КБ, и если да, можете ли вы назначить какую-либо функцию для этой корреляции, которая дает вам подсказку (читай: хэш-функция), какая из 40 КБ результаты могут / могли / должны привести. Очевидно, что ваша хеш-функция и поиск должны быть короче, чем просто выполнять умножение в первую очередь. Или, может быть, вы можете сократить время сравнения с помощью некоторого интеллектуального сокращения, например, узнать результат при определенных сценариях. Или, возможно, некоторые из ваших математических выражений могут быть оптимизированы с использованием целочисленных математических или логических сравнений. Всего несколько мыслей …
Другие решения
Чтобы ускорить процесс, вам, вероятно, следует рассчитать все возможные ответы и сохранить входные данные для каждого ответа.
Затем я бы порекомендовал составить какую-то таблицу поиска, в которой в качестве ключа используется ответ (поскольку все ответы будут уникальными), а затем сохранить все возможные входные данные, которые получат этот результат.
Чтобы помочь визуализировать:
Скажем, у вас был стол «Стол». Внутри таблицы у вас есть ключи, и с этими ключами связаны значения. То, что вы делаете, вы делаете так, чтобы ключи имели тип любого формата, в котором находятся ваши ответы (ключи будут всеми вашими ответами). Теперь присвойте каждому из 400 тыс. Входов уникальный идентификатор. Затем вы сохраняете уникальные идентификаторы для умножения как одно значение, связанное с этим конкретным ключом. Когда вы снова вычисляете тот же ответ, вы просто добавляете его как еще один набор входных данных, который может вычислить этот ключ.
Пример:
Table<AnswerType, vector<Input>>
Определить ввод как:
struct Input {IDType one, IDType two}
Где один «Ввод» может иметь идентификаторы 12384, 128, что означает, что объекты, идентифицированные 12384 и 128, при умножении дадут ответ.
Итак, в вашем поиске у вас будет что-то похожее на:
AnswerType lookup(IDType first, IDType second)
{
foreach(AnswerType k in table)
{
if table[k].Contains(first, second)
return k;
}
}
// Defined elsewhere
bool Contains(IDType first, IDType second)
{
foreach(Input i in [the vector])
{
if( (i.one == first && i.two == second ) ||
(i.two == first && i.one == second )
return true;
}
}
Я знаю, что это не настоящий код C ++, он просто подразумевается как псевдокод, и это черновой вариант как есть, но это может быть место для начала.
Хотя foreach, вероятно, будет ограничен линейным поиском, вы можете заставить метод ‘Contains’ запустить бинарный поиск, отсортировав, как хранятся входные данные.
В общем, вы смотрите на приложение для однократного запуска, которое будет выполнено за O (n ^ 2), и поиск, который будет выполняться в nlog (n). Я не совсем уверен, как память будет выглядеть после всего этого, хотя. Конечно, я не очень разбираюсь в математике, поэтому вы можете ускорить линейный поиск, если сможете как-то отсортировать ключи.