Как компрессировать упорядоченный массив уникальных натуральных чисел огр. диапазона?

Веб приложение сравнивает попарно наборы целых положительных чисел.

Каждый набор не содержит внутри себя повторов, любое из чисел не больше 210 млн. (28 бит).

В наборе их может быть от 1 до 5 млн.


Сравнивая наборы A и B надо получить наборы «уникальные для A», «уникальные для B» и «общее ядро». В частности, просто отвечать на вопросы «Есть ли в наборе S число N?»


Реализация, увы, на php и пока на shared hosting. Наскоро реализовал, нагрузив хостинговый MySQL: под каждый сет временная таблица с единственной колонкой-индексом. В большинстве случае таблицы превышают размер, который помещается в engine=Memory, и на дисковых таблицах это совсем небыстро, но работает.


Как эффективно держать такой набор, чтобы сравнение двух сетов выполнялось быстро, занимя минимальный footprint по памяти?


Пришло в голову записать каждый набор битовой маской длиной в 2^28 бит (32Mb). Из 210 млн бит всего 5 млн единиц, остальные 0: их можно записывать числом нулей подряд, например. Очень похоже на велосипед. Подскажите всем, кроме меня, известный алгоритм, эффективный для компрессии бинарных данных в частном случае «много нулей подряд»?


Про Huffman coding читал, похоже, он будет неэффективен для поиска каждого из 5 млн. чисел второго сета внутри первого.
  • Вопрос задан
  • 3579 просмотров
Решения вопроса 2
@MikhailEdoshin
Вообще это run-length encoding. Находить пересечение и разность можно без распаковки, просматривая параллельно оба набора, а вот проверку произвольного числа можно будет сделать тоже только просмотром, не очень эффективно.
Ответ написан
Комментировать
weirdan
@weirdan
Для ускорения сравнения в случае с предположительно малым общим ядром можно из каждого набора сделать Bloom Filter (для которого можно балансировать точность/потребление памяти). Тогда придется проверять вхождение только для тех элементов, для которых проверка по фильтру вернет «in set».
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@MikhailEdoshin
Учитывая, что чисел мало, проще хранить их в отсортированном массиве — 5 млн 32-битовых чисел займут 19 МБ, пересечение и разность находятся так же параллельным просмотром за O(N + M), проверка вхождения элемента двоичным поиском — O(log N).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы