Probabilistic search - psearch.tar.gz

[Sean Kelly]

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.

I don't think it matters.  No matter the algorithm, you must examine 
every element of the search string.  It's just that typical searches are 
actually worse than O(N), as they often examine each element more than once.


Sean