Probabilistic search - psearch.tar.gz

[John Demme]

John Demme wrote:

> 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

Oops... Didn't read Sean's post.... Searching an unordered set doesn't
always take n time... If the search terminates after finding the first
entry, it only can only take n in the worse case.  Given that, the average
case can be quite good.  I suspect, however, that given truely random data,
it's tough to beat n/2.

~John Demme