1

I am having problems with my timing functions here. I have a program that is timing how long a binary search is taking to find a given number in a list of sorted elements in an array.

So i am getting strange results and I'm not sure why.

For example this last run i did, the program said that it took 0 microseconds to find the value not in the array of size 100,000 elements, but just before it the program searched an array of 95,000 elements which also found the value was not in the array yet it took 4080005 microseconds.

Here is my function code. Thanks for any help!

int binarySearch(int array[], int numElems, int value)
{
    auto start =chrono::steady_clock::now();

    cout << "Searching..."<< endl;
    //variables
    int first = 0,
        last = numElems - 1,
        middle,
        position = -1;

    bool found = false;


    //Checks values for match
    while (!found && first <= last)
    {
        //divides elements
        middle = (first + last) / 2;
        if (array[middle] == value)
        {
            found = true;
            position = middle;
        }
        else if (array[middle] > value)
            last = middle - 1;
        else
            first = middle + 1;
    }

    auto end = chrono::steady_clock::now();
    auto elasped = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
    cout << "Time Taken: " << elasped.count() << " microseconds." << endl;

    return position;
}
Zelf
  • 21
  • 1
  • 5
  • 2
    4080005 can't be right. Ain't no way a binary search over 100K elements takes four seconds. Most likely, your timing is dominated by the cost of printing "Searching..." to `cout` (though 4 sec seems too much for that, either). – Igor Tandetnik Feb 17 '15 at 03:47
  • Alright put the start time under the searching and see if it changes anything but yeah that's what im thinking that something is just exploding for some reason i dont understand :( – Zelf Feb 17 '15 at 03:49
  • The values are still coming back looking pretty random I have a bunch of arrays that are being searched ranging from 5,000 elements to 100,000. but almost all of them are coming back with a 0 microsecond time to search the elements I'm really not sure what to do at this point. – Zelf Feb 17 '15 at 03:56
  • 0 milliseconds doesn't sound realistic? I mean it could return in nanoseconds. – Pranit Kothari Feb 17 '15 at 03:58
  • Even with a millisecond duration cast it gives 0. As well as nano – Zelf Feb 17 '15 at 04:01
  • Cast what? Did you mean to say, even for long durations it gives 0 seconds? – Pranit Kothari Feb 17 '15 at 04:02
  • If you need to break out a drastic-workaround for lack of VS-support in this this area, see http://stackoverflow.com/a/5524138/576911 – Howard Hinnant Feb 17 '15 at 04:07
  • Yeah, sorry every time duration is giving me 0, I will try what Howard linked here and see how it goes thanks! – Zelf Feb 17 '15 at 04:14
  • You might also consider http://stackoverflow.com/a/16299576/920069 as a high resolution windows specific replacement. – Retired Ninja Feb 17 '15 at 04:19

1 Answers1

2

Running your code with a worst case search I consistently get between 25 and 86 microseconds on my machine. Moving the cout outside the clocked section of code, I get a consistent 0 microseconds.

Maybe your stdout buffer was hung for 4 seconds. Sending text to the terminal is an extraordinarily slow process. The binary search is fast; O(log(n)), which for 100,000 is 6 comparisons, worst case. 0 microseconds makes a lot of sense. I bet it was your terminal buffers being wonky.

Now for kicks, I switched to the high_resolution_clock.

$ ./a.out 
Searching...
Time Taken: 619 nanoseconds.
Position: 99999

Source:

int binarySearch(int array[], int numElems, int value)
{

  cout << "Searching..."<< endl;
  auto start =chrono::high_resolution_clock::now();

  //variables
  int first = 0,
  last = numElems - 1,
  middle,
  position = -1;

  bool found = false;


  //Checks values for match
  while (!found && first <= last)
  {
    //divides elements
    middle = (first + last) / 2;
    if (array[middle] == value)
    {
        found = true;
        position = middle;
    }
    else if (array[middle] > value)
        last = middle - 1;
    else
        first = middle + 1;
  }

  auto end = chrono::high_resolution_clock::now();
  auto elasped = std::chrono::duration_cast<std::chrono::nanoseconds>(end-start);
  cout << "Time Taken: " << elasped.count() << " nanoseconds." << endl;

  return position;
}
JumpandSpintoWin
  • 157
  • 4
  • Was that 619 with or without the stdcout? – Zelf Feb 17 '15 at 04:13
  • That was with the std::cout, but moved above the start of the timer. – JumpandSpintoWin Feb 17 '15 at 04:14
  • I have just that as well but still getting 0 on everything, do you think there might be something making the search take 0 time if the value is not in the array? like by default if it's not in there the time is too short? – Zelf Feb 17 '15 at 04:25
  • If you switched to the high res timer and still get 0 nanoseconds, your system's timer is not good enough. I'm on a recent version of linux on pretty new hardware, Windows may not be exposing its high resolution timer through this interface (or it may not have one, but I doubt that). – JumpandSpintoWin Feb 17 '15 at 04:33
  • I switched to my windows desktop and am also getting 0 nano there also. > – Zelf Feb 17 '15 at 04:35
  • Okay so after looking through this step by step it is actually looking like auto start and auto end are giving the same values. any idea why this would happen? – Zelf Feb 18 '15 at 00:26