Задача сравнить два набора уникальных целых положительных чисел, и найти присутствующие сразу в обоих. Все точно лежат в диапазоне от 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) БД не для решения таких задач 2) используем либо упорядоченные списки, либо хештаблицы 3) я бы использовал упорядоченный список или массив, и потом сравнивал методом попарного слияния: - оба указателя на первые элементы берем элемент с первого списка, сравниваем с элементом второго списка если значения равны, то элемен заносим в список результата и увеличиваем оба указателя и к пп 1 если 1 < 2, увеличиваем значение указателя первого списка иначе второго итого, используемые алгоритмы: 2 * qsort и попарного слияния если списки ну очень большие...(20 млн вполне терпимо для памяти, но 200 может быть уже перебором), то их можно разбить на части и сравнивать сперва часть 1, потом часть 2. Алгоритм приблизительно следующий: есть списки 1: А+Б+С+Д... и 2:А+Б+С+Д... - сравниваем список 1А и 2А если список 1А закончился, то сравниваем конец списка 2А и список 1Б иначе конец списка 2Б со списоком 1А как только какой список заканчивается текущим становится следующий из данной последовательности (1 или 2 ) и так далее
Комментариев нет:
Отправить комментарий