Probabilistic search - psearch.tar.gz

[John Demme]

Andrew Fedoniouk wrote:

> 
> "Sean Kelly" <sean at f4.ca> wrote in message
> news:e0u9gl$1ppd$1 at digitaldaemon.com...
>> Oskar Linde wrote:
>>>
>>> I'm not sure if this is intended as a joke or not, but I am sorry to
>>> tell that your code is not logarithmic. It is easy to prove that there
>>> are no better algorithm than O(n) for searching an unordered array on a
>>> deterministic single thread.
>>
>> Perhaps, but some algorithms have a better average case than others
>> assuming certain (typical) conditions.  If there were simply no point,
>> why all the bother back in the 60s?
>>
>> By the way, as I just woke up, I haven't had a chance to look at the
>> algorithm yet.
>>
> 
> Take your time, no rush, it is impossible anyway.
> To find something in unordered set requires N comparison operations at
> least. Always.
> 
> As a morning tea reading I suggest to read US Patent 5,533,051 on
> compression of random data.
> It claims that it will compress two arbitrary bits into one bit.
> 
> http://gailly.net/05533051.html
> 
> 
> Andrew Fedoniouk.
> http://terrainformatica.com

Come now... I'm sure he's talking about the average case, not the worst
case.

~John Demme