Как скомпрессировать набор натуральных чисел? Порядок неважен, повторов нет.

#множества #сжатие #алгоритм #сравнение #компрессия

Задача сравнить два набора уникальных целых положительных чисел, и найти присутствующие
сразу в обоих. Все точно лежат в диапазоне от 1 до 200 млн. Обычно в каждом из двух
наборов от 0 до 5 млн чисел.
До сих пор делаю "в лоб": оба сета заношу во временные таблицы MySQL. Две одноколоночные
таблицы, где числа – первичные ключи. Сравнение проходит быстро, если сеты маленькие
и помещаются в engine=MEMORY. Медленно, когда таблицы большие и приходится создавать
их на диске. Когда надо таких сравнений выполнять помногу и часто — тормоза.
Что, если воспроизвести индексированные колонки MySQL в собственном коде? Один из
сетов держать в памяти, а каждый элемент второго проверять на наличие в первом.
Не хранить каждое из чисел набора (32бит, 2.5млн в среднем = 80Мб), а работать с
битовой маской всех возможных значений. 200 млн это, с запасом, 2^28 = 268,435,456
бит = 32Мб. Установлен – число есть в наборе, 0 – нет. Сравнивать установленные биты. 
В полном виде хранить для каждого сета весь набор битов неэффективно. Наверняка,
можно такие данные здорово компрессировать. Большинство битов будут 0, значит, их последовательности
можно кодировать их кол-вом подряд например. 
Вопрос к такому компрессированному массиву будет один: есть ли очередное искомое
число в наборе, или нет?
Упростим для примера. Пусть всего может быть 32 значения: 0..31. Наш массив будет
состоять из 32 нулей/единиц. В наборе присутствуют всего два значения: 17 и 22. 16
нулей, единица, 4 нуля, 1. И запишем их как 16,4: 10000100. Всего 8 бит вместо 2*6.
компрессия сэкономила 25%. Но это моё совсем косолапое представление о возможном способе
компрессии, без разделителей, единиц подряд и т.п.
Надо узнать про число 19, есть ли в наборе? Проходим по нашим 8 битам: 16 ещё пока
меньше 19, ещё 4 — уже перебор, ответ "нет в наборе".
Как по-вашему, есть ли вообще смысл в таком велосипеде, может ли он ускорить сравнение
двух сетов, по сравнению с MySQL?
Upd. Проще сформулирую вопрос. Ищется компрессия для данных, когда известны их параметры
и ограничения: только натуральные числа от .. до .., не подряд, не сортированные, без
повторов, порядок неважен. И даже без необходимости распаковки: нужно лишь уметь ответить
на вопрос «есть ли такое-то число в наборе, или нет?».    

Ответы

Ответ 1

1) БД не для решения таких задач
2) используем либо упорядоченные списки, либо хештаблицы 
3) я бы использовал упорядоченный список или массив, и потом сравнивал методом попарного
слияния:
 - оба указателя на первые элементы

берем элемент с первого списка,
сравниваем с элементом второго списка
если значения равны, то элемен заносим в список результата и увеличиваем оба указателя
и к пп 1
если 1 < 2, увеличиваем значение указателя первого списка
иначе второго

итого, используемые алгоритмы: 2 * qsort и попарного слияния
если списки ну очень большие...(20 млн вполне терпимо для памяти, но 200 может быть
уже перебором), то их можно разбить на части и сравнивать сперва часть 1, потом часть 2.
Алгоритм приблизительно следующий: есть списки 1: А+Б+С+Д... и 2:А+Б+С+Д...
 - сравниваем список 1А и 2А

если список 1А закончился, то сравниваем конец списка 2А и список 1Б
иначе конец списка 2Б со списоком 1А
как только какой список заканчивается текущим становится следующий из данной последовательности
(1 или 2 )
и так далее


Ответ 2

Я бы начал с простых решений и замеров времени выполнения для разных наборов данных.
Вы можете всегда хранить данные в заранее подготовленном виде (Например уже в бинарном
дереве или в отсортированном массиве)? Тогда находить элементы можно примерно так:
    // для отсортированным массивов. Сложность О(a.length + b.length)
    public static List GetSameNumber(Int32[] a, Int32[] b) {
        var i = 0;
        var j = 0;
        var ans = new List();
        while (i < a.Length && j < b.Length) {
            if (a[i] == b[j]) {
                ans.Add(a[i]);
                i++;
                j++;
            } else if (a[i] > b[j])
                j++;
            else i++;

        }

        return ans;
    } 
    // для бинарных деревьев. Сложность О(a.length) или О(a.length + b.length)в зависимости
от реализации
    public static List GetSameNumber(SortedSet a, SortedSet b) {
        var ans = new List();
        foreach (var i in a) {
            if (b.Contains(i))
                ans.Add(i);
        }
        return ans;
        //var ansset = new SortedSet(a);
        //ansset.IntersectWith(b);
        //return ansset.ToList(); // или просто return ansset
    }

Если данные нельзя хранить в нужном виде, то переводить в него каждый раз при вызове.
Тут появляется О(nlogn) для создания бинарного дерева или сортировки массива.
Большое дерево с битами на 8Гб наверно даст пенальти по кешу и пейджингу.