This (attached) search function of an unordered array of elements appears to have a logarithmic search time, like binary search of an ordered array.

sundaresh wrote:
> This (attached) search function of an unordered array of elements appears
> to have a logarithmic search time, like binary search of an ordered array.
> 
> 

I believe the time complexity of this algorithm is no better than a simple linear search. Would you care to prove your claim on the O(log n) complexity?

BTW, this newsgroup is for the D programming language.

I was told to post here by walter. I did think of posting it in the C newgroup
but felt otherwise, since D is apparently upward compatible with C, or the
specs in the site told me, so I presumed that every C program was a D program.
As far as proof goes, I have included a test program. The results clearly
indicate that for an array of size 512, of random numbers, with 2048 trials
of different distibutions, and for each trial upto 2048 random selections
of elements in the array to lookup, the number of comparisons is a constant
at 9 or lg(512). Please run the test program. If it is a bug and you can point
it out, I would be indebted. But that was why I posted it here.
If it is'nt a bug, I was hoping it would be my contribution.

I was hoping for an enlightened response.

You can lie all you want, but that does'nt change the truth.
The sun does rise in the east. There are only 4 seasons in a year, and
the value of pie is a fixed.

I would encourage users to please try it out and respond. The proof of the pudding is in the eating.

Not many experts here walter.I am dissapointed.

sundaresh skrev:
> I was told to post here by walter. I did think of posting it in the C newgroup
> but felt otherwise, since D is apparently upward compatible with C, or the
> specs in the site told me, so I presumed that every C program was a D program.
> As far as proof goes, I have included a test program. The results clearly
> indicate that for an array of size 512, of random numbers, with 2048 trials
> of different distibutions, and for each trial upto 2048 random selections
> of elements in the array to lookup, the number of comparisons is a constant
> at 9 or lg(512). Please run the test program. If it is a bug and you can point
> it out, I would be indebted. But that was why I posted it here. If it is'nt a bug, I was hoping it would be my contribution.
> 
> I was hoping for an enlightened response.
> 
> You can lie all you want, but that does'nt change the truth.
> The sun does rise in the east. There are only 4 seasons in a year, and
> the value of pie is a fixed.
> 
> I would encourage users to please try it out and respond. The proof of the
> pudding is in the eating.
> 
> Not many experts here walter.I am dissapointed.

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. I guess the error in your code is the computation of the number of comparisons:

comparisons = ++depth;

Cheers,

/Oskar

In article <e0u6na$1mdo$1@digitaldaemon.com>, sundaresh says...
>
>Not many experts here walter.I am dissapointed.
>

Well, as you say, "the proof [...] is in the eating".  You, my good man, have merely had a taste of our wonderful community so far! :)

In all seriousness, I think Wang's request for proof/data was the prime example of an enlightened response.  I'd be suprised if others lurking here weren't thinking the same thing and just didn't bother to post redundantly.

My $0.02:
As this group is still participating in the formulative steps of the D langauge,
we get a lot of "pie in the sky" ideas around here.  If I may be so bold as to
speak for the group: we've all learned to approach things here with a dose of
skepticism (as professionals do) before embracing them completely.  The
unfortunate side effect of this behavior is that perfectly good new ideas still
have to fight for some degree of recognition thanks to this de-facto acceptance
process.

And of course Walter's opinion trumps everyone's when it comes to what actually gets into D. ;)

Also, I've noticed that people here actually read posts rather than skip over the longer ones and hunt for attachments.  So posting just a .gz along with a one-liner citing how awesome your algorithm probably didn't help.  It really wouldn't hurt your case at all if you compose a small abstract about the algorithm (how it works, what its based on) and supplement that with some timing and performance data.  At least that way, nobody has to even touch a compiler unless they feel the need to validate your claims. :)


- EricAnderton at yahoo

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.


Sean

"Sean Kelly" <sean@f4.ca> wrote in message news:e0u9gl$1ppd$1@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

Andrew Fedoniouk wrote:
> 
> Take your time, no rush, it is impossible anyway.
> To find something in unordered set requires N comparison operations at least. Always.

Oops... you're right, of course.  That's what I get for reading these forums before having my coffee ;-)


Sean

Andrew Fedoniouk wrote:

> 
> "Sean Kelly" <sean@f4.ca> wrote in message news:e0u9gl$1ppd$1@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

John Demme wrote:

> Andrew Fedoniouk wrote:
> 
>> 
>> "Sean Kelly" <sean@f4.ca> wrote in message news:e0u9gl$1ppd$1@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