Самый быстрый способ создания случайных векторов для бенчмаркинга

Question

Итак, я просто играю над реализацией некоторых алгоритмов сортировки в C ++, но на данный момент мне неприятно сравнивать их из-за продолжительности времени, необходимого не для запуска алгоритма, а для создания входные данные. В настоящее время я тестирую каждую длину ввода (1000, 2000, ...) 10 раз, чтобы получить несколько усредненное время. Для каждого из этих 10 раз я создаю новое случайное число vector правильной длины, выполнив:

    // 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 000 для каждого цикла из 10.) В качестве альтернативы, я должен действительно создавать новый вектор каждый раз, когда запускаю Сортировать? Я делал это потому, что чувствовал, что возможно, что созданный вектор может быть предвзятым, и поэтому, если он был сгенерирован, а затем использован 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 раз, так что вы могли бы также использовать неподписанный символ вместо короткого. На 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");
}