## digitalmars.D - Probabilistic search - psearch.tar.gz

- sundaresh <sundaresh_member pathlink.com> Apr 04 2006
- Wang Zhen <nehzgnaw gmail.com> Apr 04 2006
- sundaresh <sundaresh_member pathlink.com> Apr 04 2006
- Oskar Linde <oskar.lindeREM OVEgmail.com> Apr 04 2006
- Sean Kelly <sean f4.ca> Apr 04 2006
- "Andrew Fedoniouk" <news terrainformatica.com> Apr 04 2006
- Sean Kelly <sean f4.ca> Apr 04 2006
- John Demme <me teqdruid.com> Apr 04 2006
- John Demme <me teqdruid.com> Apr 04 2006
- Sean Kelly <sean f4.ca> Apr 04 2006
- "Rioshin an'Harthen" <rharth75 hotmail.com> Apr 04 2006
- "Andrew Fedoniouk" <news terrainformatica.com> Apr 04 2006
- BCS <BCS_member pathlink.com> Apr 04 2006
- Sean Kelly <sean f4.ca> Apr 04 2006
- sundaresh <sundaresh_member pathlink.com> Apr 04 2006
- BCS <BCS_member pathlink.com> Apr 04 2006
- Georg Wrede <georg.wrede nospam.org> Apr 04 2006
- kwilson nowhere.com Apr 04 2006
- sundaresh <sundaresh_member pathlink.com> Apr 05 2006
- kris <foo bar.com> Apr 05 2006
- "Rioshin an'Harthen" <rharth75 hotmail.com> Apr 05 2006
- sundaresh <sundaresh_member pathlink.com> Apr 05 2006
- Nic Tiger <g_tiger progtech.ru> Apr 05 2006
- Nic Tiger <g_tiger progtech.ru> Apr 05 2006
- sundaresh <sundaresh_member pathlink.com> Apr 05 2006
- pragma <pragma_member pathlink.com> Apr 04 2006
- Hasan Aljudy <hasan.aljudy gmail.com> Apr 04 2006
- Hasan Aljudy <hasan.aljudy gmail.com> Apr 05 2006
- Sean Kelly <sean f4.ca> Apr 05 2006
- Hasan Aljudy <hasan.aljudy gmail.com> Apr 05 2006

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

Apr 04 2006

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.

Apr 04 2006

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.

Apr 04 2006

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

Apr 04 2006

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

Apr 04 2006

"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

Apr 04 2006

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

Apr 04 2006

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

Apr 04 2006

John Demme wrote:Andrew Fedoniouk wrote:"Sean Kelly" <sean f4.ca> wrote in message news:e0u9gl$1ppd$1 digitaldaemon.com...Oskar Linde wrote:

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

Apr 04 2006

John Demme wrote:Andrew Fedoniouk wrote:"Sean Kelly" <sean f4.ca> wrote in message news:e0u9gl$1ppd$1 digitaldaemon.com...Oskar Linde wrote:

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.

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

Apr 04 2006

"Sean Kelly" <sean f4.ca> wrote in message news:e0ud2e$1tvn$1 digitaldaemon.com...John Demme wrote:Andrew Fedoniouk wrote:"Sean Kelly" <sean f4.ca> wrote in message news:e0u9gl$1ppd$1 digitaldaemon.com...Oskar Linde wrote:

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.

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.

You have to examine every element of the search string? How come I haven't heard that? :) Try (approximately - my C(++) experience shows too much): char *needleInHaystack(char *haystack, char needle) { if( !haystack ) return null; for( char *loc = haystack; *loc != '\0'; loc++ ) if( *loc == needle ) return loc; return null; } This definitely does not examine every element of the string, except in the worst-case scenario - just enough to find the first occurence, no matter what the string is or what character the needle is.

Apr 04 2006

"Rioshin an'Harthen" <rharth75 hotmail.com> wrote in message news:e0ugi0$229d$1 digitaldaemon.com..."Sean Kelly" <sean f4.ca> wrote in message news:e0ud2e$1tvn$1 digitaldaemon.com...John Demme wrote:Andrew Fedoniouk wrote:"Sean Kelly" <sean f4.ca> wrote in message news:e0u9gl$1ppd$1 digitaldaemon.com...Oskar Linde wrote:

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.

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.

You have to examine every element of the search string? How come I haven't heard that? :) Try (approximately - my C(++) experience shows too much): char *needleInHaystack(char *haystack, char needle) { if( !haystack ) return null; for( char *loc = haystack; *loc != '\0'; loc++ ) if( *loc == needle ) return loc; return null; } This definitely does not examine every element of the string, except in the worst-case scenario - just enough to find the first occurence, no matter what the string is or what character the needle is.

Lets assume that here unordered set (string) has flat distribution of element(chars) occurences. You can cry, pray, read C++ books, whatever you like, but it will take you N/2 comparisons average and in the worst case N comparisons to find first occurence of something there. The only thing which affect N/2 average is the quality of your random generator (flatness of distribution). And this quality is usual reason of "wonders" in such discoveries. Andrew Fedoniouk. http://terrainformatica.com

Apr 04 2006

Andrew Fedoniouk wrote:Lets assume that here unordered set (string) has flat distribution of element(chars) occurences. You can cry, pray, read C++ books, whatever you like, but it will take you N/2 comparisons average and in the worst case N comparisons to find first occurence of something there. The only thing which affect N/2 average is the quality of your random generator (flatness of distribution). And this quality is usual reason of "wonders" in such discoveries. Andrew Fedoniouk. http://terrainformatica.com

That is true if you are using N for the size of your alphabet consider: B is a string of random bits with even distribution of 1 or 0. Find the first 1 bit. mean search length is something like 1-2

Apr 04 2006

Rioshin an'Harthen wrote:You have to examine every element of the search string? How come I haven't heard that? :)

Potentially, yes. Unless the algorithm has notably unique best-case behavior (such as quicksort), there's really no point in considering anything else. Sean

Apr 04 2006

FYI, there is absolutely nothing wrong with that statement. It is certainly not a bug, if there is one, and I am not ruling out that possibility.comparisons is never decremented or decreased, so how can it be reduced to the value of 9, if it increases above 9, as you claim/assume that it supposedly does. The value of comparisons is set prior to any/all recursive calls to psearch. If on the other hand, you claim that it is possibly the characteristic of the random number generator, since it makes the decision of which half to search for first, but then again, that decision is binary and I think that any random number generator should generate as many even numbers as odd numbers, at least for a reasonably sized sample. I am not one to contest theory, and if this algorithm is correct, then there probably is a very valid and sound theoretical explanation as to why it works, but I am not one to reject evidence either, in the face of it, especially of such an astounding nature. It is well acknowledged that empirical testing of methods lead to a convincing degree of assurance in them and is a reasonable way to assess their reliability. My apologies if I have irked you. To have an open mind, while looking at it is all I asked for. The reason I posted it here was because I was not sure myself. In article <e0u7jg$1n3i$1 digitaldaemon.com>, Oskar Linde says...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

Apr 04 2006

sundaresh wrote:FYI, there is absolutely nothing wrong with that statement. It is certainly not a bug, if there is one, and I am not ruling out that possibility.comparisons is never decremented or decreased, so how can it be reduced to the value of 9, if it increases above 9, as you claim/assume that it supposedly does. The value of comparisons is set prior to any/all recursive calls to psearch. If on the other hand, you claim that it is possibly the characteristic of the random number generator, since it makes the decision of which half to search for first, but then again, that decision is binary and I think that any random number generator should generate as many even numbers as odd numbers, at least for a reasonably sized sample. I am not one to contest theory, and if this algorithm is correct, then there probably is a very valid and sound theoretical explanation as to why it works, but I am not one to reject evidence either, in the face of it, especially of such an astounding nature. It is well acknowledged that empirical testing of methods lead to a convincing degree of assurance in them and is a reasonable way to assess their reliability. My apologies if I have irked you. To have an open mind, while looking at it is all I asked for. The reason I posted it here was because I was not sure myself.

How about try a different dataset? Grab chunks out of "Alice in wonderland" or something like that. I have heard of cases where it was possible to get more performance than you should be able to by leveraging predictable non randomness in a data set. An example: in English the letter "Q" is almost always followed by "U" their for if you are searching for "U" and you find a "Q" check the next char.

Apr 04 2006

Point 1: we do have to allow for the different expression of content and intent that arises from writers, who are from a fundamentally different cultural background. (Possibly this is made even harder if such a person uses some automatic translation between languages.) So, I vote for understanding, meditation and deep thought, before dismissing the ideas presented. Point 2: there are several "test cases" for algorithms. One is "worst case", another is "truly random data", another is "best case", yet another is "average case", and finally we have "plausible data". (There are others, I know.) Since _no_ interesting data is truely random (because by definition, such data does not contain Information!), we can dismiss the "truly random data" case. Now, depending on the application domain, it may or may not be significant what the "worst case" performance is. Similarly, "best case" usually doesn't count, but it's weight has to be evaluated on a case by case basis. At this point we are between the "average case" and "plausible data". Here we actually can find surprising results, if we look hard enough. For all practical purposes, the algorithm which performs best _given_ "actual like" data, would be the one to choose. (Assuming we are even able to present such "actual like" data in the first place.) --- In summary, instead of quibbling over theoretical merits of this particular method, we might do better by trying to evaluate which kind of data this algorithm may perform best with, and thereafter compare it to those generally suggested for that kind of data. sundaresh wrote:FYI, there is absolutely nothing wrong with that statement. It is certainly not a bug, if there is one, and I am not ruling out that possibility.comparisons is never decremented or decreased, so how can it be reduced to the value of 9, if it increases above 9, as you claim/assume that it supposedly does. The value of comparisons is set prior to any/all recursive calls to psearch. If on the other hand, you claim that it is possibly the characteristic of the random number generator, since it makes the decision of which half to search for first, but then again, that decision is binary and I think that any random number generator should generate as many even numbers as odd numbers, at least for a reasonably sized sample. I am not one to contest theory, and if this algorithm is correct, then there probably is a very valid and sound theoretical explanation as to why it works, but I am not one to reject evidence either, in the face of it, especially of such an astounding nature. It is well acknowledged that empirical testing of methods lead to a convincing degree of assurance in them and is a reasonable way to assess their reliability. My apologies if I have irked you. To have an open mind, while looking at it is all I asked for. The reason I posted it here was because I was not sure myself. In article <e0u7jg$1n3i$1 digitaldaemon.com>, Oskar Linde says...sundaresh skrev:

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

Apr 04 2006

Hi there Sandresh, The "bug" within your program is simply that your base case (or terminating case) for the recursion is (size == 1) and you increment/decrement a variable (ie. depth) outside of this base case "if" statement. This leads to a recursively maximized value of 9 (or log base 2 of 512), as pointed out. Then, since no variable is updated in the base case "if" statement, you don't actually add to the comparison total accordingly. Thus you mistakenly get a maximal depth of 9 for each search. This is not actually the depth to find the element you are searching for, but rather the depth to the "size == 1" base case. Now you will say that "this is not true" since the base case is reached many times during the search process before the search is terminated....not just once after depth equals nine. The static "depth" variable is not being updated properly, though. Once you try the changes suggested below you will see that the "Average depth" of the 2048 searches per distribution will be approximately 256. Single "depths" or comparisons will range from 1 to 512 as would be expected. The average per distribution is approximately N/2 as several others in this thread have pointed out, as the correct average case search for an element in a randomized array of size N. If you want to argue that the "depth" of the actual comparisons never exceeds 9, then that is obviously true because log base 2 of 512 is 9.....but that doesn't mean that the number of comparisons is 9. Sorry ;) Hope the code change and viewing the results will clear things up if anyone can't follow my explanation above (my fault for not explaining things well enough, I'm afraid). Try these simple changes: in psearch.c on line 9: add ------> ++comparisons; on line 18: comment out --------> //comparisons = ++depth; on line 31: comment out --------> //--depth; Thanks, K.Wilson

Apr 04 2006

I believe that I have replied to this already. My first suspisions was with comparisons, but there is nothing wrong with it. Comparisons is updated prior to call to the base case psearch, so why should it be updated again during the base case, since in the base case, no recursive call to psearch is being made. Doing so might actually result in 256 or so as you claim, but that would be introducing a bug and not eliminating it. Sorry, these arguments have only served to convince me even further of the correctness and workability of this algorithm. In article <e0uug0$2mq8$1 digitaldaemon.com>, kwilson nowhere.com says...Hi there Sandresh, The "bug" within your program is simply that your base case (or terminating case) for the recursion is (size == 1) and you increment/decrement a variable (ie. depth) outside of this base case "if" statement. This leads to a recursively maximized value of 9 (or log base 2 of 512), as pointed out. Then, since no variable is updated in the base case "if" statement, you don't actually add to the comparison total accordingly. Thus you mistakenly get a maximal depth of 9 for each search. This is not actually the depth to find the element you are searching for, but rather the depth to the "size == 1" base case. Now you will say that "this is not true" since the base case is reached many times during the search process before the search is terminated....not just once after depth equals nine. The static "depth" variable is not being updated properly, though. Once you try the changes suggested below you will see that the "Average depth" of the 2048 searches per distribution will be approximately 256. Single "depths" or comparisons will range from 1 to 512 as would be expected. The average per distribution is approximately N/2 as several others in this thread have pointed out, as the correct average case search for an element in a randomized array of size N. If you want to argue that the "depth" of the actual comparisons never exceeds 9, then that is obviously true because log base 2 of 512 is 9.....but that doesn't mean that the number of comparisons is 9. Sorry ;) Hope the code change and viewing the results will clear things up if anyone can't follow my explanation above (my fault for not explaining things well enough, I'm afraid). Try these simple changes: in psearch.c on line 9: add ------> ++comparisons; on line 18: comment out --------> //comparisons = ++depth; on line 31: comment out --------> //--depth; Thanks, K.Wilson

Apr 05 2006

sundaresh wrote:I believe that I have replied to this already. My first suspisions was with comparisons, but there is nothing wrong with it. Comparisons is updated prior to call to the base case psearch, so why should it be updated again during the base case, since in the base case, no recursive call to psearch is being made. Doing so might actually result in 256 or so as you claim, but that would be introducing a bug and not eliminating it. Sorry, these arguments have only served to convince me even further of the correctness and workability of this algorithm.

Jolly good! Capital stuff, what! Now then, my good man ~ you've qualified for tonight's free gift: a front-row ticket to the greatest show on the planet! ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The Cast (in order of appearance.) M= Man looking for an argument R= Receptionist Q= Abuser A= Arguer (John Cleese) C= Complainer (Eric Idle) H= Head Hitter M: Ah. I'd like to have an argument, please. R: Certainly sir. Have you been here before? M: No, I haven't, this is my first time. R: I see. Well, do you want to have just one argument, or were you thinking of taking a course? M: Well, what is the cost? R: Well, It's one pound for a five minute argument, but only eight pounds for a course of ten. M: Well, I think it would be best if I perhaps started off with just the one and then see how it goes. R: Fine. Well, I'll see who's free at the moment. Pause R: Mr. DeBakey's free, but he's a little bit conciliatory. Ahh yes, Try Mr. Barnard; room 12. M: Thank you. (Walks down the hall. Opens door.) Q: WHAT DO YOU WANT? M: Well, I was told outside that... Q: Don't give me that, you snotty-faced heap of parrot droppings! M: What? Q: Shut your festering gob, you tit! Your type really makes me puke, you vacuous, coffee-nosed, maloderous, pervert!!! M: Look, I CAME HERE FOR AN ARGUMENT, I'm not going to just stand...!! Q: OH, oh I'm sorry, but this is abuse. M: Oh, I see, well, that explains it. Q: Ah yes, you want room 12A, Just along the corridor. M: Oh, Thank you very much. Sorry. Q: Not at all. M: Thank You. (Under his breath) Stupid git!! (Walk down the corridor) M: (Knock) A: Come in. M: Ah, Is this the right room for an argument? A: I told you once. M: No you haven't. A: Yes I have. M: When? A: Just now. M: No you didn't. A: Yes I did. M: You didn't A: I did! M: You didn't! A: I'm telling you I did! M: You did not!! A: Oh, I'm sorry, just one moment. Is this a five minute argument or the full half hour? M: Oh, just the five minutes. A: Ah, thank you. Anyway, I did. M: You most certainly did not. A: Look, let's get this thing clear; I quite definitely told you. M: No you did not. A: Yes I did. M: No you didn't. A: Yes I did. M: No you didn't. A: Yes I did. M: No you didn't. A: Yes I did. M: You didn't. A: Did. M: Oh look, this isn't an argument. A: Yes it is. M: No it isn't. It's just contradiction. A: No it isn't. M: It is! A: It is not. M: Look, you just contradicted me. A: I did not. M: Oh you did!! A: No, no, no. M: You did just then. A: Nonsense! M: Oh, this is futile! A: No it isn't. M: I came here for a good argument. A: No you didn't; no, you came here for an argument. M: An argument isn't just contradiction. A: It can be. M: No it can't. An argument is a connected series of statements intended to establish a proposition. A: No it isn't. M: Yes it is! It's not just contradiction. A: Look, if I argue with you, I must take up a contrary position. M: Yes, but that's not just saying 'No it isn't.' A: Yes it is! M: No it isn't! A: Yes it is! M: Argument is an intellectual process. Contradiction is just the automatic gainsaying of any statement the other person makes. (short pause) A: No it isn't. M: It is. A: Not at all. M: Now look. A: (Rings bell) Good Morning. M: What? A: That's it. Good morning. M: I was just getting interested. A: Sorry, the five minutes is up. M: That was never five minutes! A: I'm afraid it was. M: It wasn't. Pause A: I'm sorry, but I'm not allowed to argue anymore. M: What?! A: If you want me to go on arguing, you'll have to pay for another five minutes. M: Yes, but that was never five minutes, just now. Oh come on! A: (Hums) M: Look, this is ridiculous. A: I'm sorry, but I'm not allowed to argue unless you've paid! M: Oh, all right. (pays money) A: Thank you. short pause M: Well? A: Well what? M: That wasn't really five minutes, just now. A: I told you, I'm not allowed to argue unless you've paid. M: I just paid! A: No you didn't. M: I DID! A: No you didn't. M: Look, I don't want to argue about that. A: Well, you didn't pay. M: Aha. If I didn't pay, why are you arguing? I Got you! A: No you haven't. M: Yes I have. If you're arguing, I must have paid. A: Not necessarily. I could be arguing in my spare time. M: Oh I've had enough of this. A: No you haven't. M: Oh Shut up. (Walks down the stairs. Opens door.) M: I want to complain. C: You want to complain! Look at these shoes. I've only had them three weeks and the heels are worn right through. M: No, I want to complain about... C: If you complain nothing happens, you might as well not bother. M: Oh! C: Oh my back hurts, it's not a very fine day and I'm sick and tired of this office. (Slams door. walks down corridor, opens next door.) M: Hello, I want to... Ooooh! H: No, no, no. Hold your head like this, then go Waaah. Try it again. M: uuuwwhh!! H: Better, Better, but Waah, Waah! Put your hand there. M: No. H: Now.. M: Waaaaah!!! H: Good, Good! That's it. M: Stop hitting me!! H: What? M: Stop hitting me!! H: Stop hitting you? M: Yes! H: Why did you come in here then? M: I wanted to complain. H: Oh no, that's next door. It's being-hit-on-the-head lessons in here. M: What a stupid concept. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Sundaresh-dude; If you want to argue the merits of your outstanding algorithm, you need to choose the right room to begin. This is the room for discussion upon the D language itself ~ not language-agnostic algorithms. Might I suggest you try the /slashdot/ room instead? Just down the hallway, and to the right a bit. Yes, that's right. You may get a good argument there

Apr 05 2006

"sundaresh" <sundaresh_member pathlink.com> wrote in message news:e0vqej$12o5$1 digitaldaemon.com...I believe that I have replied to this already. My first suspisions was with comparisons, but there is nothing wrong with it. Comparisons is updated prior to call to the base case psearch, so why should it be updated again during the base case, since in the base case, no recursive call to psearch is being made.

That's just it. You don't count how many comparisons it takes to find a match, just how deep it has to go. And with an original size of 512, that always leads to log2(512). Since you only count the depth of the search, not the amount of comparisons, you'll find it's almost always 9 - it may be shorter, depending on which item was randomly picked to be searched for.Doing so might actually result in 256 or so as you claim, but that would be introducing a bug and not eliminating it.

Frankly, you are so wrong in this. Now you only count the depth, not how many items it searches. And it's the items that matter, not the depth. It's the amount of comparisons that tells what time the algorithm has - and in the case of this, it's most definitely O(N).Sorry, these arguments have only served to convince me even further of the correctness and workability of this algorithm.

*sigh* A fool, then. Many have shown you where you've gone wrong, but you seem to be "I'm right and I know it, you'd just introduce a bug in it"... If you refuse to listen, go ahead. Mathematically, it is possible to prove that no search of unordered data can be done in time less than O(N) - you always have to in the worst case test *all* occurences. I'm attaching an altered version of psearch with this message, so you can test it yourself. It's a zip archive with MS-DOS line endings (since that's the system I happen to be on). I strongly recommend after unzipping and compiling that you invoke it by directing standard output to a file - it's going to display so much data on the amount of comparisons it took to find something, as well as how it found it. Then you'll see it's not O(log N) but O(N).

Apr 05 2006

Sorry about that, you were right, for all but the base case, the value of comparisons is incremented in the else part. So here is the corrected version. But the search time is still O(lg(n)), since avg comparisons is just one more at 10,and I think the worst case comparisons is 11, so this still seems to be comparable to binary search.Here is the corrected version. #include<stdlib.h> int comparisons; void *psearch(void *base, int size, int width, void *element, int (*compare)(void *, void *)) { static int depth = 0; if(size <= 1) { ++comparisons; return ! size || compare(base, element) ? NULL : base; } else { int half, right; void *found; half = size / 2; right = abs(rand()) % 2; comparisons = ++depth; if(right) { found = psearch(base + half * width, size - half, width, element, compare); if(! found) { found = psearch(base, half, width, element, compare); } } else { found = psearch(base, half, width, element, compare); if(! found) { found = psearch(base + half * width, size - half, width, element, compare); } } --depth; return found; } } In article <e0uug0$2mq8$1 digitaldaemon.com>, kwilson nowhere.com says...Hi there Sandresh, The "bug" within your program is simply that your base case (or terminating case) for the recursion is (size == 1) and you increment/decrement a variable (ie. depth) outside of this base case "if" statement. This leads to a recursively maximized value of 9 (or log base 2 of 512), as pointed out. Then, since no variable is updated in the base case "if" statement, you don't actually add to the comparison total accordingly. Thus you mistakenly get a maximal depth of 9 for each search. This is not actually the depth to find the element you are searching for, but rather the depth to the "size == 1" base case. Now you will say that "this is not true" since the base case is reached many times during the search process before the search is terminated....not just once after depth equals nine. The static "depth" variable is not being updated properly, though. Once you try the changes suggested below you will see that the "Average depth" of the 2048 searches per distribution will be approximately 256. Single "depths" or comparisons will range from 1 to 512 as would be expected. The average per distribution is approximately N/2 as several others in this thread have pointed out, as the correct average case search for an element in a randomized array of size N. If you want to argue that the "depth" of the actual comparisons never exceeds 9, then that is obviously true because log base 2 of 512 is 9.....but that doesn't mean that the number of comparisons is 9. Sorry ;) Hope the code change and viewing the results will clear things up if anyone can't follow my explanation above (my fault for not explaining things well enough, I'm afraid). Try these simple changes: in psearch.c on line 9: add ------> ++comparisons; on line 18: comment out --------> //comparisons = ++depth; on line 31: comment out --------> //--depth; Thanks, K.Wilson

Apr 05 2006

sundaresh wrote:#include<stdlib.h> int comparisons; void *psearch(void *base, int size, int width, void *element, int (*compare)(void *, void *)) { static int depth = 0; if(size <= 1) {

Replace this line++comparisons;

if ( size ) ++comparisons;return ! size || compare(base, element) ? NULL : base; } else { int half, right; void *found; half = size / 2; right = abs(rand()) % 2;

and remove this linecomparisons = ++depth;

if(right) { found = psearch(base + half * width, size - half, width, element, compare); if(! found) { found = psearch(base, half, width, element, compare); } } else { found = psearch(base, half, width, element, compare); if(! found) { found = psearch(base + half * width, size - half, width, element, compare); } } --depth; return found; } }

then you will have *REAL* count of compare() function call even better we to supply test compare function that would increment comparisons before returning comparison result. If you don't apply mentioned changes, your code will count something completely different from "comparison number" Nic Tiger

Apr 05 2006

this is your latest code, with proper comparisons counting and some simple test; just compile it and run. last printed line will state: average_cmp=247 which is essentially ~(N/2) for 512 item test as a note, you should write compare(*(void**)base, element), otherwise it is difficult to use any of existing comparison functions (strcmp or smth.) Nic Tiger. -------- test suite for psearch -------- #include <stdlib.h> #include <string.h> #include <stdio.h> int comparisons = 0; int compare (void *p1, void *p2) { comparisons ++; return strcmp ( *(const char**)p1, (const char*)p2 ); } void *psearch(void *base, int size, int width, void *element, int (*compare)(void *, void *)) { static int depth = 0; if(size <= 1) { return ! size || compare(base, element) ? NULL : base; } else { int half, right; void *found; half = size / 2; right = abs(rand()) % 2; //comparisons = ++depth; if(right) { found = psearch((char*)base + half * width, size - half, width, element, compare); if(! found) { found = psearch((char*)base, half, width, element, compare); } } else { found = psearch((char*)base, half, width, element, compare); if(! found) { found = psearch((char*)base + half * width, size - half, width, element, compare); } } --depth; return found; } } main () { char *list[512]; int i; for ( i = 0; i < 512; i ++ ) { char buf[32]; sprintf ( buf, "str%d", i ); list[i] = strdup(buf); } int total_cmp = 0; for ( i = 0; i < 512; i ++ ) { comparisons = 0; void *res = psearch ( list, 512, 4, list[i], compare ); if ( res ) printf ( "%d comparisons to find %s (found as %d index of list)\n", comparisons, list[i], (char**)res - list ); else printf ( "%s not found, %d comparisons\n", list[i], comparisons ); total_cmp += comparisons; } printf ( "average_cmp=%d", total_cmp/512 ); }

Apr 05 2006

My apologies, making these changes does result in a linear worst case behaviour, so it is no better than sequential search. In article <e0uug0$2mq8$1 digitaldaemon.com>, kwilson nowhere.com says...

Apr 05 2006

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

Apr 04 2006

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.

It doesn't compile, on VC++ 2005 I get: psearch.c(19) : error C2036: 'void *' : unknown size psearch.c(27) : error C2036: 'void *' : unknown size I fixed it by casting base to int (int)base anyway, I'd like (please) to see a human readable pseudo code that doesn't include mangling with pointers, just array indecies.

Apr 04 2006

Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit sundaresh wrote:

ok, I just wrote a D version of the algorithm, and used the CPU counter to benchmark pefromance. before I post the code, here's how you can use it, assuming you compile it into dps.exedps > log.txt

(give it a few seconds to run all the test cases, shouldn't take too long). you can examine the log file, and you will see clearly that the increase in time is linear related to the increase in array size. or, you can use gnuplot to see it more clearly.gnuplotset terminal png set output "graph.png" plot "log.txt" with lines

I've attached my results. and here's the D code, according to what I understood of the algorithm. if something is wrong in my understanding, please point me to it. --------- import std.stdio; import std.random; template psearch(T) { bool psearch( T[] arr, T element ) { if( arr.length == 1 ) { if( arr[0] == element ) return true; else return false; } int choice = rand() % 2; T[] first, second; int middle = arr.length / 2; if( choice == 1 ) { first = arr[0..middle]; second = arr[middle..$]; } else { first = arr[middle..$]; second = arr[0..middle]; } if( !psearch( first, element ) ) { return psearch( second, element ); } return false; } } alias psearch!(int) probSearch; void main() { CPUTimer timer = new CPUTimer(); for( int i = 1000; i < 100000; i+=500 ) { int[] arr = randomArray( i ); //random int array of size i timer.timein(); //start cpu timer probSearch( arr, 27 ); //look for 27 timer.timeout(); //stop cpu timer //print: length time writefln( "%d %d", i, timer.getSmallTime() ); } } class CPUTimer { long time; void timein() { time = rdtsc(); } void timeout() { time = rdtsc() - time; } //a small version of the time .. int getSmallTime() { return (time/1000L); } } //x86 only long rdtsc() { asm { naked; rdtsc; ret; } } int[] randomArray( int size ) { int[] arr = new int[size]; for( int i = 0; i < size; i++ ) { arr[i] = rand() % (size/2); //random data, mod by size/2 to give 27 a reasonably chance of appearing??!! } return arr; }

Apr 05 2006

Hasan Aljudy wrote:and here's the D code, according to what I understood of the algorithm. if something is wrong in my understanding, please point me to it. --------- import std.stdio; import std.random; template psearch(T) { bool psearch( T[] arr, T element ) { if( arr.length == 1 ) { if( arr[0] == element ) return true; else return false; } int choice = rand() % 2; T[] first, second; int middle = arr.length / 2; if( choice == 1 ) { first = arr[0..middle]; second = arr[middle..$]; } else { first = arr[middle..$]; second = arr[0..middle]; } if( !psearch( first, element ) ) { return psearch( second, element ); } return false; } }

Thanks for posting this. I hadn't taken the time to look at the algorithm yet, and this got me interested :-) The algorithm is obviously O(N) for single-element searches, and equivalent in theoretical complexity to the naive approach for substring searches. In practical terms it's even worse because of the N recursive function calls, but it could always be rewritten as a loop with some bookkeeping. It's obvious that the algorithm favors certain pattern positions in the search string, ie. (1/4)N, (3/4)N, and so on, while traditional searches typically perform best if the pattern is near the beginning of the string. Though this raises an interesting point--the probabilistic search above is not a "find first" or "find last" algorithm. Probably not a big deal for unordered sets, but it might be otherwise. Sean

Apr 05 2006

Sean Kelly wrote:Hasan Aljudy wrote:and here's the D code, according to what I understood of the algorithm. if something is wrong in my understanding, please point me to it. --------- import std.stdio; import std.random; template psearch(T) { bool psearch( T[] arr, T element ) { if( arr.length == 1 ) { if( arr[0] == element ) return true; else return false; } int choice = rand() % 2; T[] first, second; int middle = arr.length / 2; if( choice == 1 ) { first = arr[0..middle]; second = arr[middle..$]; } else { first = arr[middle..$]; second = arr[0..middle]; } if( !psearch( first, element ) ) { return psearch( second, element ); } return false; } }

Thanks for posting this. I hadn't taken the time to look at the algorithm yet, and this got me interested :-) The algorithm is obviously O(N) for single-element searches, and equivalent in theoretical complexity to the naive approach for substring searches. In practical terms it's even worse because of the N recursive function calls, but it could always be rewritten as a loop with some bookkeeping. It's obvious that the algorithm favors certain pattern positions in the search string, ie. (1/4)N, (3/4)N, and so on, while traditional searches typically perform best if the pattern is near the beginning of the string. Though this raises an interesting point--the probabilistic search above is not a "find first" or "find last" algorithm. Probably not a big deal for unordered sets, but it might be otherwise. Sean

I think I have a mistake in the last bit of it .. I wrote: if( !psearch( first, element ) ) { return psearch( second, element ); } return false; when it should be: if( psearch( first, element ) ) { return true; } else { return psearch( second, element ); }

Apr 05 2006