Probabilistic search - psearch.tar.gz

sundaresh sundaresh_member at pathlink.com
Wed Apr 5 01:08:26 PDT 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 at digitaldaemon.com>, kwilson at 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
>
>
>
>
>





More information about the Digitalmars-d mailing list