Probabilistic search - psearch.tar.gz ~~ possible proof of wrongness

[Hasan Aljudy]

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.
> 
> 

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.exe

 >dps > 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.

 >gnuplot
 >>set 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;
}


-------------- next part --------------
A non-text attachment was scrubbed...
Name: results.zip
Type: application/x-zip-compressed
Size: 9984 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20060405/9250a7da/attachment.bin>