From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <kharpost@rambler.ru>
X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on sa.int.altlinux.org
X-Spam-Level: 
X-Spam-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00,SPF_PASS
	autolearn=ham version=3.2.5
Message-ID: <4AF80B94.1050309@rambler.ru>
Date: Mon, 09 Nov 2009 15:31:16 +0300
From: "Kharitonov A. Dmitry" <kharpost@rambler.ru>
User-Agent: Thunderbird 2.0.0.21 (X11/20090323)
MIME-Version: 1.0
To: ALT Linux Team development discussions <devel@lists.altlinux.org>
References: <20091107193402.GD10659@altlinux.org>	<20091107203900.GA3428@imap.altlinux.org>	<20091107213551.GA22236@imap.altlinux.org>	<20091107223421.GE10659@altlinux.org>
	<20091108040207.GA21896@imap.altlinux.org>
In-Reply-To: <20091108040207.GA21896@imap.altlinux.org>
Content-Type: text/plain; charset=KOI8-R; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: [devel] =?koi8-r?b?18/Q0s/TINDSzyDeydPMwQ==?=
X-BeenThere: devel@lists.altlinux.org
X-Mailman-Version: 2.1.12
Precedence: list
Reply-To: ALT Linux Team development discussions <devel@lists.altlinux.org>
List-Id: ALT Linux Team development discussions <devel.lists.altlinux.org>
List-Unsubscribe: <https://lists.altlinux.org/mailman/options/devel>,
	<mailto:devel-request@lists.altlinux.org?subject=unsubscribe>
List-Archive: <http://lists.altlinux.org/pipermail/devel>
List-Post: <mailto:devel@lists.altlinux.org>
List-Help: <mailto:devel-request@lists.altlinux.org?subject=help>
List-Subscribe: <https://lists.altlinux.org/mailman/listinfo/devel>,
	<mailto:devel-request@lists.altlinux.org?subject=subscribe>
X-List-Received-Date: Mon, 09 Nov 2009 12:27:14 -0000
Archived-At: <http://lore.altlinux.org/devel/4AF80B94.1050309@rambler.ru/>
List-Archive: <http://lore.altlinux.org/devel/>
List-Post: <mailto:devel@altlinux.org>

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 у меня оказалось все совсем плохо, происходит не сжатие, а расширение :)
>   
Вообще-то у вас получается не паковка, а сортировка.