• PHP
• математика
• технология за търсене
• алгоритми

Уеб приложение сравнява двойките набори от положителни числа.

Всеки комплект съдържа в себе си повтаря, всяко от числата вече не 210 Mill. (28 бита).

Комплектът може да бъде от 1 до 5 Mill.

Сравнявайки набори А и В е необходимо, за да получите набор от "уникални за A", "B за уникалната" и "обща основа". По-специално, просто отговори на въпросите: "Има ли определен брой S N»?

Изпълнение, уви, в PHP и докато споделен хостинг. Набързо реализира, натоварване хостинг MySQL: за всяка определена временна таблица с една колона-индекс. В повечето случаи, надвишава размера на таблицата, която се поставя в двигателя = паметта и по-диск маси е абсолютно не бърза, но тя работи.

Как ефективно да се запази този комплект за сравнение две групи извършват бързо, заемайки минимална графична среда за памет?

Хрумна записвате всеки набор от битова маска дължина от 2 ^ 28 бита (32MB). От 210 милиона бита само 5 милиона единици, 0 почивка: те може да записва броя на последователни нули, например. Много подобна на мотора. Кажи ми всичко, с изключение на мен, добре познат алгоритъм за ефективно компресиране на двоични данни в конкретен случай "много нули в ред?"

Pro Хъфман кодиране прочете той изглежда е неефективен за търсене на всяка от 5 Mill. Втората група от номера в рамките на първия.

не 19MB. Особено в PHP памет изисква два пъти повече. Сега като "глава" и да запази - в базата данни, индексирана колона е 32-битово цяло число. Там сравнение. Уникалността на конкретния случай, в отсъствието на повторенията, за unprincipledness и известно разстояние. От тях три, данните, които искате да изтръгне atski ефективна компресия, скорост и малък необходимата памет.

За да компресирате поредица от нула бита нужда от етикет, който не надхвърля данните, както и броя, а след това - на този номер. Да предположим, че тези цифри ще са с фиксиран размер на 32 бита - тогава ще трябва същите пет милиона 32-битови цели числа да се позове на сгъстен част. Вероятно някакъв начин може да наруши и използване на променлива дължина, но тя все още се усложни кода и вече е трудно narisovyvaetsya. Сортирани масива да се съхраняват в обикновен файл и да го прочете в части (макар че, за да запълни тази масив ще бъде по-трудно). Между другото, не само на броя на 32-битова, можете да използвате горните бита за информационно обслужване - например, да се създаде единен масив, и в по-горните бита да се отбележи, на това, което отличава този номер се отнася.