timing accuracy?

This is my first post and any help would be appreciated. I'm writing a program that reads a file of integers of unknown length, then allows the user to choose 1 of 5 kinds of sorts. At the end. the time it took to sort the list will be displayed. The problem has been finding something to time it in ms. What I have below is the closest I've gotten but at times still shows 0 seconds, other times .06, or .11 (all my testing so far has been with a selection sort and bubble sort of 200 integers).

Code:

---

void SelectionSort(        vector <int>& listOfData,
                double& duration)
{       
    int        temp;
    int        counter;
    int        index;
    int        minIndex;
    clock_t        start;       
    clock_t        finish;       

    start = clock();    //  grabs beginning count

    for (counter = 0; counter < listOfData.size(); counter++)
  {
        minIndex = counter;

        for (index = counter + 1; index < listOfData.size(); index++)
        {
            if (listOfData[index] < listOfData[minIndex])
                minIndex = index;
        }

        temp = listOfData[counter];
        listOfData[counter] = listOfData[minIndex];
        listOfData[minIndex] = temp;
    }       
       
    finish = clock();        // grabs ending count
    duration = double (finish - start) / CLOCKS_PER_SEC;
}

---

I hope I got the code tags right. If there's any other methods of timing anyone knows that are more consistent and accurate I would appreciate it. Thanks!

Also on a somewhat unrelated topic. With vectors, is there an upper range limit of elements that a vector can hold? Is it necessary to do checks for out of bounds? And if so, how might I do that without knowing the number of elements I'll be adding? I'll appreciate any help. Thanks!

Thanks, I'll give those a shot. Appreciate the info on vectors.

With your guess of the initial size, use the reserve(size_type n) member function (where n is the number of objects to hold). Then, continue to use push_back(). The vector will not reallocate its array until you've filled up the n spots available, and you call push_back() once more.

What I've done so far is created a zero length vector and called push_back() as I read from the file. Is it better to create a vector of say 2000 (my estimate) up front, even though there could be significantly more or less elements than that? I guess creating the spaces up front would be more efficient, but wouldn't it waste memory if they aren't all used? Thanks

Whats the default number of elements an vector holds if you don't use reserve() but immediately do push_back, before it allocates another block of memory?

It would be a waste of memory, but it all depends on which is more important: time efficiency, or memory efficiency.

If time is an issue, allocate a lot, and use however much you need. If memory is an issue, allocate on demand only.

There are also some strategies for allocating memory, such as the following: allocate memory based on an initial guess - once you run out, allocate twice as much memory, and repeat as necessary. This way, no more than half of the memory is wasted (assuming that at least one reallocation did occur).

Here is some (untested) code which illustrates what I am talking about:

Code:

---

const int elements_to_add = 700;
int elements added = 0;

void foo()
{
  vector<int> array;
  array.reserve(200);

  add_elements(array);

  while(elements_added < elements_to_add)
  {
    array.reserve(2 * array.capacity());
    add_elements(array);
  }
}

void add_elements(vector<int>& vec)
{
  while(vec.size() < vec.capacity() && elements_added < elements_to_add)
  {
    vec.push_back(3);
    ++elements_added;
  }
}

---

Elixia--
As far as I can tell it's just an empty container with zero length and memory is allocated every time push_back() is called (not very efficient as I see now).

Zach L.--
That makes a lot of sense. I'm going try something like you showed and see how it works out. It looks like resize() would be helpful.

This is my first try at dynamic allocation so I appreciate all your guys' help.

Glad to be of help.

Just some more info on resizing vectors. resize() and reserve() do very different (externally), yet very similar (internally) things (yes, I know that makes no sense... hang on a second). reserve() sets the capacity of the vector, but you don't want to access elements until its size (number of indexable elements) reaches that particular index. The size() returns the size (essentially, the number of indexable elements), while capacity() returns how many can 'fit' into the currently allocated space. Granted, you can write to that memory using the subscript operator, your vector will not know about it (at() would fail, and end() will point to the wrong location.

For example:

Code:

---

vector<int> vec;
vec.reserve(10);
cout << vec.size(); // Print "0".
cout << vec.capacity(); // Print "10"
...
vec.push_back(10); // size() == 1, capacity() == 10

---

Cheers

I'll bet you're running Windows.

With Windows, clock() does NOT get updated every millisecond. It has somethng to do with the interrupt clock rate. I don't recall what the interrupt rate is, but once every ~50ms might be right. So, clock() still returns milliseconds, but the resolution is about 50ms. :(

There is a Windows function that works. I think it's GetClockTick().

Quote:

---

Originally posted by mfknitz
What I have below is the closest I've gotten but at times still shows 0 seconds, other times .06, or .11

---

That's because you are using the default system timer that ticks approximately 18.2 times per second (about every 55 msec). In fact, it is the original 4.772720 MHz clock of the original IBM PC divided by 2^18. You should use the QueryPerformanceCounter function, instead, if you are programming under Windows.

About vector memory:
The exact allocation strategy is implementation-defined, but the most common is this:
initial size: 0
first addition: allocate 1
whenever not enough memory: allocate twice as much as there already is

I know that SGItech STL and STLport use this. I'm quite sure the the MS and GNU STL use it too.

Thanks everyone for your great replies. The GetTickCount() worked but still wasn't accurate enough for really small lists. The QueryPerformanceCounter works great though.

I've allocated more memory initially in my vector now and it's working pretty well. I think it'll take me a little bit to learn all the ins and outs of dynamic memory but this is a pretty good start. Thanks

There's also a
clock_t clock( void );
function in <time.h>

On my WinXP system, it has a resolution of 1/100th of a second, even though it returns values in milliseconds, as CLOCKS_PER_SEC on my machine is 1000.

I guess this is something you could use if your system doesn't have a High-Resolution Timer.

In a program I've written that talks to an external device on the serial port, the device requires millisecond accuracy to "wake up". I've implemented this as follows which works perfectly as the resulting serial trace on an oscilloscope was measured and found to be at exactly 1ms intervals.


timeBeginPeriod (1); // request windows to be accurate to within 1ms instead of the normal 5ms. This function will return TIMERR_NOCANDO if the system does not support 1ms accuracy (works fine under 2000 and XP, which are my main OS's).

timeGetTime(); // Returns the system time, in milliseconds. This is very efficient and low-overhead function. It returns a DWORD result, and so wraps around to 0 every 2^32 milliseconds, which is about 49.71 days.

timeEndPeriod(1); // Call this function immediately after you are finished using timer services. Parameter is the value you used in timeBeginPeriod.