5

Задача сравнить два набора уникальных целых положительных чисел, и найти присутствующие сразу в обоих. Все точно лежат в диапазоне от 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. Проще сформулирую вопрос. Ищется компрессия для данных, когда известны их параметры и ограничения: только натуральные числа от .. до .., не подряд, не сортированные, без повторов, порядок неважен. И даже без необходимости распаковки: нужно лишь уметь ответить на вопрос «есть ли такое-то число в наборе, или нет?».

10
  • А как вы свяжете битовые поля и бинарные деревья?
    – IronVbif
    25 фев 2013 в 5:21
  • В этом и вопрос ) Как я смутно представляю себе, дерево будет состоять только из 0 и 1, причем "полностью прорисовываются" только ветви, ведущие к установленным битам,а нулевые отбрасываются. Возможно, что-то близкое к Хаффману, но без статистического анализа получившегося набора.
    – Sergiks
    25 фев 2013 в 6:18
  • 1
    почитайте как работают индексы в СУБД для чисельных типов данных. скорее за все вам нужен аналог индекса на основе бинарного дерева, но можно и скомбинировать несколько разных
    – jmu
    25 фев 2013 в 8:48
  • 1
    @sergiks, откуда у Вас взялось 8 GB? Битовая строка для всех 32-бит целых это 512 MB. Тоже немало. Вы пишете, что максимальный размер набора 5млн. Тогда хэш-таблица с 50% заполнения займет 10млн ячеек, т.е. 40 MB (без компрессии). Подумайте.
    – avp
    25 фев 2013 в 13:01
  • 1
    @sergiks, а ведь если битовый вектор на 2^28 бит (Вы пишете 268,435,456 бит) содержит только 5,000,000 единичек, то он должен неплохо сжиматься. В среднем получается единичка на 53 нулевых бита. Возможно сжатие самым тривиальным способом - счетчиком повторов (наверное не бит, а нулевых байт). Т.е. каждый набор храните как сжатую строку из 2^28 бит, а в процессе чтения разворачиваете в памяти и одновременно (!!!) выполняете операцию AND. Причем IMHO можно написать так, что эта распаковка и AND потребует минимума (буквально несколько слов) памяти (кроме буфера, естественно).
    – avp
    26 фев 2013 в 9:20

2 ответа 2

5

1) БД не для решения таких задач

2) используем либо упорядоченные списки, либо хештаблицы

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

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

итого, используемые алгоритмы: 2 * qsort и попарного слияния

если списки ну очень большие...(20 млн вполне терпимо для памяти, но 200 может быть уже перебором), то их можно разбить на части и сравнивать сперва часть 1, потом часть 2.

Алгоритм приблизительно следующий: есть списки 1: А+Б+С+Д... и 2:А+Б+С+Д... - сравниваем список 1А и 2А

  • если список 1А закончился, то сравниваем конец списка 2А и список 1Б
  • иначе конец списка 2Б со списоком 1А
  • как только какой список заканчивается текущим становится следующий из данной последовательности (1 или 2 )
  • и так далее
6
  • Спасибо за алгоритм попарного сравнивания. Думаю, то, что надо - в паре с компрессией из коммента @avp. Память совсем мала - проект пока живёт на shared хостинге, отсюда и вынужденный аутсорс на сервер БД, где памяти больше, чем у скриптов.
    – Sergiks
    26 фев 2013 в 10:12
  • пиши на С++ или JAVA, может быть на python так же возможно, но точно не знаю, как там организованы массивы. на РНР точно такое писать нельзя - по памятти не влезет.
    – akalend
    26 фев 2013 в 10:16
  • @akalend попробую написать модуль к nginx, чего уж там.. : )
    – Sergiks
    26 фев 2013 в 13:00
  • и зачем тебе лишний гемморой? пиши scgi модуль на libscgi в конфиге nginx пропишешь location /numpers { scgi_pass localhost:8080; }
    – akalend
    26 фев 2013 в 13:53
  • Вообще от БД не избавиться, т.к. в ней надо хранить все эти сеты долговременно. В компрессированном бинарном виде, теперь, наверное. Попробую всё же на PHP реализовать, или на perl, т.к. Си не владею, и Java только в контексте Processing.org использовал пока.
    – Sergiks
    26 фев 2013 в 14:54
3

Я бы начал с простых решений и замеров времени выполнения для разных наборов данных. Вы можете всегда хранить данные в заранее подготовленном виде (Например уже в бинарном дереве или в отсортированном массиве)? Тогда находить элементы можно примерно так:

    // для отсортированным массивов. Сложность О(a.length + b.length)
    public static List<Int32> GetSameNumber(Int32[] a, Int32[] b) {
        var i = 0;
        var j = 0;
        var ans = new List<Int32>();
        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<Int32> GetSameNumber(SortedSet<Int32> a, SortedSet<Int32> b) {
        var ans = new List<Int32>();
        foreach (var i in a) {
            if (b.Contains(i))
                ans.Add(i);
        }
        return ans;
        //var ansset = new SortedSet<Int32>(a);
        //ansset.IntersectWith(b);
        //return ansset.ToList(); // или просто return ansset
    }

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

Большое дерево с битами на 8Гб наверно даст пенальти по кешу и пейджингу.

4
  • Только хотел запостить тот же код. @sergiks: Бинарные деревья необязательны и таблицы, ваши данные прекрасно помещаются в память. Отсортируйте их и пробегитесь один раз по обоим массивам, как в первом примере ответа.
    – VladD
    25 фев 2013 в 13:31
  • @IronVbif: всё же сложность первого варианта O(n log n), где n = max(len(a), len(b)), потому что ещё нужна сортировка.
    – VladD
    25 фев 2013 в 13:34
  • @VladD: Ну там сверху предлагается всегда хранить элементы в отсортированном виде, если это возможно. А снизу написано про nlogn в случае сортировки
    – IronVbif
    26 фев 2013 в 7:40
  • @VladD: данные будут отсортированы заранее.
    – Sergiks
    27 фев 2013 в 0:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.