[devel] вопрос про числа

Kharitonov A. Dmitry kharpost at rambler.ru
Mon Nov 9 12:31:16 UTC 2009


Vladislav Zavjalov wrote:
> On Sun, Nov 08, 2009 at 01:34:21AM +0300, Alexey Tourbin wrote:
>   
>> On Sun, Nov 08, 2009 at 12:35:51AM +0300, Vladislav Zavjalov wrote:
>>     
>>>> То есть, задача: есть n m-битных чисел, нужно проверить, что данное число
>>>> находится среди них. Хранить хочется меньше, чем n*m бит.
>>>>
>>>> Я бы попробовал посмотреть паковку на такую тему:
>>>>         
>>> Эх, только вот эксперимент показывает, что такая паковка эффективна
>>> только при достаточно больших n. При n=1000 и m=32 коэффициент паковки у меня
>>> получился 1.38... Так что я неправильно подумал...
>>>       
>> Что-то у Вас слишком хороший коэффициент получился.  У меня получается
>> энтропия 23.477 бита супротив 32 то максимально возможный коэффициент
>> сжатия по идее должен быть 1.36.
>>
>> $ perl -le 'sub log2{log($_[0])/log(2)}; sub H{my$p=shift;-$p*log2($p)-(1-$p)*log2(1-$p)}; $n=1000;$m=32; $bits_per_hash=(1<<$m)/$n; print H(1/$bits_per_hash)*$bits_per_hash'
>> 23.4769105882751
>> $
>>
>> Я правда не уверен что это правильная энтропия получается (через
>> эквивалентность по битмапу).
>>     
>
> Я плохо выразился, при небольших n у меня оказалось все совсем плохо, происходит не сжатие, а расширение :)
>   
Вообще-то у вас получается не паковка, а сортировка.



More information about the Devel mailing list