创建用于基准测试的随机向量的最快方法

Question

所以，我只是尝试用 C++ 实现一些排序算法，但我发现目前对它们进行基准测试很烦人，因为不运行算法而是创建输入数据所需的时间很长。我目前测试每个输入长度（1000、2000、...） 10 次，以获得稍微平均的时间。对于这 10 次中的每一次，我都会创建一个长度正确的新随机向量：

    // Each of the 10 times.
    for(int j = 0; j < 10; j++) {

        A.clear();

        // 'i' is the current input size.
        for(int k = 0; k < i; k++) {
            A.push_back(rand() % 10000);
        }

        // Other stuff
    }

是否有更好的方法来做到这一点？我是否应该费心将 rand() 限制在 10000，或者这只是我的强迫症大脑喜欢整数？ （即，当您考虑到目前 10 次循环中的每个循环最多执行 10,000 次时，模运算实际上是否会花费大量时间。）或者，我是否应该在每次运行时创建一个新向量种类？我一直这样做是因为我觉得创建的向量可能会存在偏差，因此如果生成该向量然后使用 10 次，答案可能会非常错误......

Answer 1

有更好的方法吗？

是的，您可能需要在这里做一些事情来帮助加快速度。
如前所述，在 std::vector 中保留空间，然后将值分配给已知元素，速度更快。此外，使用非优化编译器时，预递增（ ++var 而不是 var++ ）速度更快。只是为了保持代码快速，无论谁构建它，您可能需要考虑从现在开始这样做。就内存而言，您可能会发现它微不足道，但是当我使用无符号的已知大小并且不是不合理地大时，我在 for 循环中使用无符号短整型。

然而，关于模数。如果您不需要它，您可能不想使用它。根据向量中保存的数据类型，如果结果超出该类型的最大存储容量，则结果应该换行。

我不知道它是否会消耗更多具有变量包装的处理能力，如果是的话，我仍然不确定它是否是一个比执行模数更便宜的操作。在使用 rand 之前，可能需要运行一些已知大小的速度测试。

    A.reserve(i * i);
    for(unsigned short j = 0; j < 10; ++j) {            
        for(unsigned short k = 0; k < i; ++k) 
            A[k + (i*10)] = rand();                
        // Other stuff
    }

编辑

需要注意的非常小的变化：循环仅进行 10 次，因此您最好使用 unsigned char，而不是短字符。在 Win32 上至少需要一半的内存。

    A.reserve(i * i);
    for(unsigned char j = 0; j < 10; ++j) {            
        for(unsigned char k = 0; k < i; ++k) 
            A[k + (i*10)] = rand();                
        // Other stuff
    }

Answer 2

来自 cplusplus.com 的引用 (http://www.cplusplus.com/reference/stl/ vector/），它提供了一个非常有用的提示：

“就性能而言，重新分配可能是一项成本高昂的操作，因为它们通常涉及将向量使用的整个存储空间复制到新位置。因此，每当计划大幅增加向量的大小，建议使用成员函数vector::reserve显式指示向量的容量。”

使用 vector::reserve 几乎肯定会提高您的情况的性能。

编辑：您可以尝试使用 random_shuffle (http://www. cplusplus.com/reference/algorithm/random_shuffle/）在向量创建后对其进行洗牌（显然，random_shuffle与元素数量呈线性关系）。

Answer 3

我创建了一个，你看一下：

#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <sstream>

int main(int argc, char* argv[]){
    if (argc < 2){
        printf("No arguments found\n");
        exit(1);
    }
    int maxi;
    maxi = atoi(argv[1]);
    int * a;
    a = new int [5];

    std::stringstream ss;
    ss << maxi;
    printf(ss.str());
    printf("\n");
}