[Moscow.pm] Большой битовый массив

[Михаил Монашёв]

Здравствуйте, Vladimir.

>> Есть  несколько  миллионов  чисел  в  диапазоне от 0 до 2 в 32 степени
>> минус  1  .  Нужно  быстро  проверять, есть такое число или нету. Если
>> засунуть  их в битовый массив, то они все влезут в 16 мегабайт. Вопрос
>> в  том,  каким  модулем  пользоваться для записи/чтения в этот битовый
>> массив,  чтобы  было  быстро  и при этом не раздувалось в памяти более
>> 20-30  мегабайт? Или может проще самому через substr + побитовые ИЛИ/И
>> реализовать чзапись/чтение?

> Мне кажется, вам может подойти Judy ;-)
> https://gist.github.com/3252244

> Тут тест... памяти такой массив занимает 13Мб на 4 с небольшим млн
> элементов битовых, скорость доступа достаточно высока.
> Я сравнивал не с вектором (который по памяти проигрывает, а с хешом
> перловым), вот вывод у меня дома:
> $ perl test.pl
> fill array...
> done...
> Judy stats:
>         Count all: 4297124
>         Count (<=10000): 10
>         MemUsage: 13115440
> benchmark tests...
> Benchmark: running Hash, Judy for at least 2 CPU seconds...
>       Hash:  2 wallclock secs ( 2.10 usr +  0.00 sys =  2.10 CPU) @
> 1963552.36/s (n=4126528)
>       Judy:  2 wallclock secs ( 2.00 usr +  0.00 sys =  2.00 CPU) @
> 2505395.00/s (n=5010790)

> Вообще в продакшн, я этим модулем не пользовался, как-то не
> требовалось до сих пор, так что мемлики, треды и т.п. желательно
> потестить.

Спасибо большое. Попробуем. Как раз то, что нужно.

-- 
С уважением,
 Михаил                          mailto:postmaster на softsearch.ru