Уменьшение размера таблицы поиска

Question

У меня есть приложение, в котором я должен хранить пару миллионов целых чисел, я должен хранить их в таблице поиска, очевидно, я не могу хранить такой объем данных в памяти, и в своих требованиях я очень ограничен. Я должен хранить данные во встроенной системе, поэтому я очень ограничен в пространстве, поэтому я хотел бы спросить вас о рекомендуемых методах, которые я могу использовать для сокращения таблицы поиска. Я не могу использовать функцию приближения, такую ​​как нейронные сети, значения должны быть в таблице. Диапазон целых чисел в настоящее время неизвестен. Когда я говорю целые числа, я имею в виду 32-битное значение.

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

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

Я нашел один, называемый кодированием плитки http://www.cs.ualberta.ca/~sutton/book/8/node6.html, Этот основан на нескольких таблицах поиска, кто-нибудь знает какой-либо другой метод?.

Спасибо.

Answer 1

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

Было бы полезно узнать, какой у вас ключ к поиску цифр.

Answer 2

Если ваш набор целых чисел однороден, то вы можете попробовать хеш-таблицу, потому что есть хитрость, которую вы можете использовать для сокращения размера хранимых целых чисел, в вашем случае, пополам. Предположим, что целое число n, потому что его множество однородно, может быть хешем. Предположим, у вас есть 0x10000 (16k) сегментов. Индекс каждого сегмента, iBucket = n & FFFF. Каждый элемент в корзине должен хранить только 16 битов, так как первые 16 битов являются индексом корзины. Другая вещь, которую вы должны сделать, чтобы данные были небольшими, это поместить количество элементов в корзину и использовать массив для хранения элементов в корзине. Использование связанного списка будет слишком большим и медленным. Когда вы выполняете итерацию массива в поисках совпадения, помните, что вам нужно только сравнить 16 сохраненных битов.

Таким образом, предполагая, что сегмент - это указатель на массив и число. В 32-битной системе это максимум 64 бита. Если бы число целых было достаточно маленьким, мы могли бы сделать некоторые причудливые вещи и использовать 32 бита для корзины. 16 КБ * 8 байт = 524 КБ, 2 миллиона шорт = 4 МБ. Таким образом, вы получаете метод для поиска целых и сжатия около 40%.

Answer 3

Если вы просто ищете наличие рассматриваемого числа, то фильтр Блума , возможно, это то, что вы ищете. Честно говоря, хотя ваш вопрос довольно расплывчатый и запутанный. Это поможет объяснить, что такое значения Q, и что вы будете делать с ними, когда найдете их в таблице.

Answer 4

Чтение http://www.cs.ualberta.ca/~sutton/RL-FAQ.html

«Функция приближения» относится к использование параметризованной функциональной формы представлять функцию значения (и / или политики), в отличие от простой стол. "

Возможно, это относится. Также обновите ваш вопрос дополнительными фактами - не просто отвечайте в комментариях.

---

Edit.

Массив битов может легко хранить бит для каждого из ваших миллионов чисел. Допустим, у вас есть цифры в диапазоне от 1 до 8 миллионов. В одном мегабайте памяти вы можете иметь 1 бит для каждого номера в вашем наборе и 0 для каждого номера, не входящего в ваш набор.

Если у вас есть числа в диапазоне от 1 до 32 миллионов, вам потребуется 4 МБ памяти для большой таблицы из всех 32M различных чисел.

См. Мой ответ на Современный высокопроизводительный фильтр Блума в Python? для реализации на Python битового массива неограниченного размера.

Answer 5

Мне нужно больше подробностей по проблеме. Если вы не можете сохранить действительное значение целых чисел, а только приблизительное значение, это означает, что вы собираетесь уменьшить (выбросить) некоторые данные (детализацию), правильно? Я думаю, что вы ищете хеш, который может быть художественной формой сам по себе. Например, скажем, у вас есть 32-битные значения, один хеш будет состоять в том, чтобы взять 4 байта и xor их вместе, это приведет к единственному 8-битному значению, уменьшая вашу память в 4 раза, но также уменьшая реальное значение исходных данных , Как правило, вы можете / могли бы пойти дальше и, возможно, использовать только несколько из этих 8 битов, скажем, младшие 4 и еще больше уменьшить значение.

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