- PHP
- Математика
- пошукові технології
- алгоритми
Веб додаток порівнює попарно набори цілих позитивних чисел.
Кожен набір не містить в собі повторів, будь-яка з чисел не більше 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 млн. Чисел другого сету всередині першого.
немає 19Мб. Тим більше, в PHP пам'яті буде потрібно рази в два більше. Зараз так «в лоб» і зберігаю - в БД, індексована колонка 32-бітних цілих. Там же порівнюю. Унікальність окремого випадку у відсутності повторів, непринциповості порядку і відомому діапазоні. З цих трьох подробиць хочеться вичавити ацкі ефективну компресію, швидкість і малу необхідну пам'ять.
Щоб стиснути послідовність нульових бітів потрібна мітка, що далі йдуть не дані, а число, а потім - це число. Припустимо, ці числа у вас будуть фіксованого розміру в 32 біта - вам тоді будуть потрібні ті ж самі п'ять мільйонів 32-бітних чисел для позначення стислих ділянок. Можна, напевно, якось перекрутити і використовувати числа змінної довжини, але це ще ускладнить код, а він і так уже нарісовивается непростий. Відсортований же масив можна зберігати в простому файлі і зчитувати його по частинах (правда, заповнити такий масив буде важче). До речі, раз числа не 32-бітові, можна використовувати верхні біти для службової інформації - наприклад, створити один масив, а в верхніх бітах відзначати, до яких наборам це число відноситься.