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

[Vladimir Timofeev]

3 августа 2012 г., 9:56 пользователь Михаил Монашёв
<postmaster на softsearch.ru> написал:
> Здравствуйте.
>
> Есть  несколько  миллионов  чисел  в  диапазоне от 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)

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

-- 
Vladimir Timofeev <vovkasm на gmail.com>