C++时间()函数

Question

我调用time()函数，在向量上运行排序算法，然后再次调用time()函数。当我这样做时，从time()返回的值对于两个调用都是完全相同的，因此我无法计算完成排序所需的时间。当向量有任意数量的元素时，就会发生这种情况；它不会改变。我在底部的sort()函数中调用time(NULL)。任何帮助都是非常感谢的。谢谢!

main.cpp

#include <cstdlib>
#include <iostream>
#include <vector>
#include <stdio.h>
#include <ctime>

using namespace std;

int listSize, listType;
static const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";

template <typename E>
void printVector(vector<E>& list)
{
    typename vector<E>::iterator it;
    for (it = list.begin(); it != list.end(); it++)
        cout << *it << " ";
}

template <typename E>
vector<E> generateList(int listType, int listSize)
{   
    vector<E> list;
    if (listType == 1)
    {
        for (int i = 0; i < listSize; i++)
        {
            int random = rand() % 10001;
            list.push_back(random);
        }
    } 
    else if (listType == 2)
    {
        for (int i = 0; i < listSize; i++)
        {
            double random = (10000 * (double)rand() / (double)RAND_MAX);
            list.push_back(random);
        }
    }
    else if (listType == 3)
    {
        for (int i = 0; i < listSize; i++)
        {
            char random = alphabet[rand() % (sizeof(alphabet) - 1)];
            list.push_back(random);
        }
    }
    else
    {
        cout << "Invalid type\n";
        exit(0);
    }

    return list;
}

template <typename E>
void insertionSort(vector<E>& list)
{
    E i, j, tmp;

    for (i = 1; i < list.size(); i++)
    {
        j = i;
        tmp = list[i];
        while (j > 0 && tmp < list[j-1])
        {
            list[j] = list[j-1];
            j--;
        }
        list[j] = tmp;
    }
}

template <typename E>
vector<E> merge(vector<E>& list, vector<E>& left, vector<E>& right)
{
    vector<E> result;
    unsigned left_it = 0, right_it = 0;

    while(left_it < left.size() && right_it < right.size())
    {
        if(left[left_it] < right[right_it])
        {
            result.push_back(left[left_it]);
            left_it++;
        }
        else
        {
            result.push_back(right[right_it]);
            right_it++;
        }
    }

    while(left_it < left.size())
    {
        result.push_back(left[left_it]);
        left_it++;
    }

    while(right_it < right.size())
    {
        result.push_back(right[right_it]);
        right_it++;
    }
    list = result;              
    return list;
}

template <typename E>
vector<E> mergeSort(vector<E>& list)
{
    if(list.size() == 1)
    {
        return list;
    }

    typename vector<E>::iterator middle = list.begin() + (list.size() / 2);

    vector<E> left(list.begin(), middle);
    vector<E> right(middle, list.end());

    left = mergeSort(left);
    right = mergeSort(right);

    return merge<E>(list, left, right);
}

template <typename E>
void shiftRight(vector<E>& list, int low, int high)
{
    int root = low;
    while ((root*2)+1 <= high)
    {
        int leftChild = (root * 2) + 1;
        int rightChild = leftChild + 1;
        int swapIndex = root;
        if (list[swapIndex] < list[leftChild])
        {
            swapIndex = leftChild;
        }
        if ((rightChild <= high) && (list[swapIndex] < list[rightChild]))
        {
            swapIndex = rightChild;
        }
        if (swapIndex != root)
        {
            double tmp = list[root];
            list[root] = list[swapIndex];
            list[swapIndex] = tmp;
            root = swapIndex;
        }
        else
        {
            break;
        }
    }
    return;
}

template <typename E>
void heapify(vector<E>& list, int low, int high)
{
    int midIndex = (high - low - 1)/2;
    while (midIndex >= 0)
    {
        shiftRight(list, midIndex, high);
        midIndex--;
    }
    return;
}

template <typename E>
void heapSort(vector<E>& list, int size)
{
    heapify(list, 0, size - 1);
    int high = size - 1;
    while (high > 0)
    {
        double tmp = list[high];
        list[high] = list[0];
        list[0] = tmp;
        high--;
        shiftRight(list, 0, high);
    }
    return;
}

template <typename E>
int pivot(vector<E>& list, int first, int last) 
{
    int p = first;
    E pivotElement = list[first];

    for(int i = first+1 ; i <= last ; i++)
    {
        if(list[i] <= pivotElement)
        {
            p++;
            E temp = list[i];
            list[i] = list[p];
            list[p] = temp;
        }
    }

    E temp = list[p];
    list[p] = list[first];
    list[first] = temp;

    return p;
}

template <typename E>
void quickSort(vector<E>& list, int first, int last) 
{
    E pivotElement;

    if(first < last)
    {
        pivotElement = pivot(list, first, last);
        quickSort(list, first, pivotElement-1);
        quickSort(list, pivotElement+1, last);
    }
}
template <typename E>
bool sort(vector<E>& list)
{
    int again = 0;
    int sort = 0;
    long int start, finish, duration;

    cout << "Which sorting algorithm would you like to use?" << endl;
    cout << " 1 for Insertion Sort\n 2 for Merge Sort\n 3 for Heapsort\n 4 for Quicksort" << endl;
    cin >> sort;
    cout << endl;

    printVector(list);    
    cout << "\n" << endl;

    start = time(NULL);
    if (sort == 1)
        insertionSort(list);
    else if (sort == 2)
        mergeSort(list);
    else if (sort == 3)
        heapSort(list, list.size());
    else if (sort == 4)
        quickSort(list, 0, list.size() - 1);
    else {
        cout << "Invalid command\n";
        exit(0);
    }    
    finish = time(NULL);

    duration = finish - start;

    cout << start << endl;
    cout << "Sorting the list took " << duration << " seconds." << endl;  
    cout << finish << endl;

    printVector(list);

    while (again == 0) {
        cout << "\n\nWould you like to go again? (1 for yes, 2 for no)\n";
        cin >> again;
        if (again == 1)
            return true;
        else if (again == 2)
            return false;
    }
}

int main(int argc, char** argv) 
{
    bool again = true;
    while (again) {
        cout << "How many items do you want to sort? (0 to quit)" << endl;
        cin >> listSize;
        if (listSize == 0)
            exit(0);
        else if (listSize < 0) {
            cout << "Invalid input.\n";
            exit(0);
        }
        /* Change first parameter of generateList() to 1-3
         * 1 for ints, 2 for doubles, 3 for chars
         * 
         * Also change vector types in the three places below to
         * the corresponding parameter type.
         */
        vector<char> list = generateList<char>(3, listSize);
        again = sort<char>(list);
    }
}

Answer 1

time()只有第二分辨率。您的类型可能完成得足够快，以至于您看不到它的滴答声。如果你想给它计时，你需要用一个更精确的时钟。

如果您可以访问C++11，最简单的方法是：

auto begin = std::chrono::high_resolution_clock::now();
// do sort() stuff here
auto end = std::chrono::high_resolution_clock::now();

auto elapsed_usec = std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();;

预-C++11，您可以使用这个：

struct timeval begin, end;
gettimeofday(&begin, NULL);
// do sort() stuff here
gettimeofday(&end, NULL);

long elapsed_usec = (end.tv_sec - begin.tv_sec) * 1e6 + 
                    (end.tv_usec - begin.tv_usec);

Answer 2

第一个问题是通过对finish和start时间的不同来计算时间：

• time_t通常以秒为单位表示。
• 可移植程序不应直接使用http://www.cplusplus.com/reference/ctime/time/返回的值，而应始终依赖于对标准库中其他元素的调用来将它们转换为可移植类型(例如本地时间、gmtime或difftime)。
• 使用difftime()，您将得到一个以秒为单位表示的双值，但使用您所使用的特定库实现(可能低于第二个)可用的精度。

更好的方法是使用C++11 ：

chrono::high_resolution_clock::time_point t = high_resolution_clock::now();
...
chrono::high_resolution_clock::time_point t2 = high_resolution_clock::now();
long elapsed_milisecs = duration_cast<milliseconds>(t2 - t).count();

然而，还有第二个问题:尽管这是可移植的和精确的，但是您的操作系统的时钟分辨率是受限制的。

例如，在windows上，这个时钟分辨率是15 ms的。小于15 ms的任何内容都可能显示为0。

改进时间度量的最简单方法，尤其是在基准测试的情况下，可能是增加度量的迭代次数。与其只执行一次度量的代码，不如度量数千次连续迭代的时间，并计算每次迭代的平均时间。

一种较不容易移植的方法是使用本机OS高分辨率计时器，以规避库实现限制：

• 对于windows，您可以使用QueryPerformanceCounter，如这个博客中所解释的那样。
• 对于linux，您可以使用clock_gettime()，如这个问题中所解释的那样。