Probabilistic search - psearch.tar.gz

[Andrew Fedoniouk]

"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