0

I wrote this program that will read from a file some numbers, insert into an array, perform linear search, sort them, and perform binary search (after sorted).

I put the clock functions to measure how long it takes to perform each task mentioned above.

The files are big and have about 5 million numbers. Inserting takes time and is shown by the clock. (Reading from the file is not done in the best way), so does linear search and sorting. However, binary search takes 0 seconds to be performs. Obviously this isn’t right.

I am curios why it is displaying zero for both the time in milliseconds and the number of clock ticks?

I am running in Windows 8.1, ASUS, Intel i-5, 8GB of RAM, 2.4 GHz processor.

This is the output:

$ make
g++  -c -Wall -g  search.cpp
g++  -o search search.o

$ ./search <input-5m.in
Time to insert: 26171
Time to Linear Search: 16
Yes!
Time to Sort: 1390
Time to Binary Search in milliseconds: 0
Time to Binary Search in clock ticks: 0
Time to Binary Search printed with "printf()": 0.000000
Yes!

This is the code.

using namespace std;
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdio>
#include <iomanip>      // std::setprecision


clock_t clock(void);
...
...
...

int main(int argc, char** argv)
{
...
...
...

   clock_t startLinear, finishLinear;
   double elapsedTimeLinear =0;

    startLinear = clock();
    bool foundLinear = linearSearch(elements, n , x);
    finishLinear = clock();

    elapsedTimeLinear = (double)(finishLinear - startLinear)/CLOCKS_PER_SEC*1000;
    cout << "Time to Linear Search: " << elapsedTimeLinear << endl;
    foundLinear ? std::cout<<"Yes!"<<std::endl : std::cout<<"No!"<<std::endl;

    clock_t startSort, finishSort;
    double elapsedTimeSort =0;

    startSort = clock();
    sort(elements, elements+n);
    finishSort = clock();

    elapsedTimeSort = (double)(finishSort - startSort)/CLOCKS_PER_SEC*1000;
    cout << "Time to Sort: " << elapsedTimeSort << endl;

    clock_t startBinary, finishBinary;
    double elapsedTimeBinary =0, elapsedTimeBinaryTicks=0;

    startBinary = clock();
    //bool foundBinary = binarySearch(elements, n , x);
    bool foundBinary = binary_search(elements, elements+n, x);
    finishBinary = clock();

    elapsedTimeBinary = (double)(finishBinary - startBinary)/CLOCKS_PER_SEC*1000;
    elapsedTimeBinaryTicks = (double)(finishBinary - startBinary);
    cout << "Time to Binary Search in milliseconds: " << elapsedTimeBinary << endl;
    cout << "Time to Binary Search in clock ticks: " << elapsedTimeBinaryTicks << endl;
    printf("Time to Binary Search printed with \"printf()\": %f\n", elapsedTimeBinary);
    foundBinary ? std::cout<<"Yes!"<<std::endl : std::cout<<"No!"<<std::endl;
user2512806
  • 421
  • 1
  • 9
  • 26
  • Maybe this timer resolution is not high enough to show the difference. – JustSomeGuy Mar 10 '15 at 06:05
  • Any idea how to make it so it actually shows a difference? – user2512806 Mar 10 '15 at 06:07
  • 1
    I can't find documentation for it (I looked), but many clocks only have a precision of about 16 milliseconds. Anything less registers as 0. You might want to look into high performance timers. – Steven Hansen Mar 10 '15 at 06:08
  • @user2512806 I'm not sure. It's pretty OS-specific. But there is a `std::chrono::high_resolution_clock` in a C++11 standard library, so, if your compiler supports it, you can look at it. – JustSomeGuy Mar 10 '15 at 06:10
  • That could be the reason. The lowest I got is 15 milliseconds. Any suggestions what are some higher performance timers? – user2512806 Mar 10 '15 at 06:12

1 Answers1

4

A million items means at most 20 compares. With normally efficient code (I haven't looked at yours) that's well below 1 msec. Perform the thing you want to measure a large number of times in a loop in order to get above the clock resolution.

Cheers and hth. - Alf
  • 142,714
  • 15
  • 209
  • 331