Комплексный вектор и эталонный список связанных списков для рандомизированных вставок / удалений - PullRequest
Новая
       8

Комплексный вектор и эталонный список связанных списков для рандомизированных вставок / удалений

5 голосов
/ 19 марта 2012

Итак, я знаю этот вопрос и другие вопросы о SO, которые касаются проблемы, но большинство из них имеют дело со сложностями структур данных (просто для копирования здесь, связанные это теоретически имеет O (

Я понимаю, что сложности, похоже, указывают на то, что список будет лучше, но меня больше волнует производительность в реальном мире.

Примечание: Этот вопрос был вдохновлен слайдами 45 и 46 презентации Бьярна Страуструпа на Going Native 2012 , где он рассказывает о том, как кэширование процессора и локальность ссылок действительно помогают с векторами, но не совсем (или не достаточно) со списками.

Вопрос: Есть ли хороший способ проверить это с использованием процессорного времени, а не настенного времени, и получить достойный способ «случайной» вставки и удаления элементов, которые можно сделать заранее, чтобы это не влиять на сроки?

В качестве бонуса было бы неплохо иметь возможность применить это к двум произвольным структурам данных (скажем, векторных и хэш-карт или что-то в этом роде), чтобы найти «реальную производительность» на некотором оборудовании.

Ответы [ 2 ]

5 голосов
/ 19 марта 2012

Полагаю, если бы я собирался протестировать что-то подобное, я бы, вероятно, начал с кода чего-то такого: 

#include <list>
#include <vector>
#include <algorithm>
#include <deque>
#include <time.h>
#include <iostream>
#include <iterator>

static const int size = 30000;

template <class T>
double insert(T &container) {
    srand(1234);
    clock_t start = clock();
    for (int i=0; i<size; ++i) {
        int value = rand();
        T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
        container.insert(pos, value);
    }
// uncomment the following to verify correct insertion (in a small container).
//  std::copy(container.begin(), container.end(), std::ostream_iterator<int>(std::cout, "\t"));
    return double(clock()-start)/CLOCKS_PER_SEC;
}


template <class T>
double del(T &container) {
    srand(1234);
    clock_t start = clock();
    for (int i=0; i<size/2; ++i) {
        int value = rand();
        T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
        container.erase(pos);
    }
    return double(clock()-start)/CLOCKS_PER_SEC;
}       

int main() { 
    std::list<int> l;
    std::vector<int> v;
    std::deque<int> d;

    std::cout << "Insertion time for list: " << insert(l) << "\n";
    std::cout << "Insertion time for vector: " << insert(v) << "\n";
    std::cout << "Insertion time for deque: " << insert(d) << "\n\n";

    std::cout << "Deletion time for list: " << del(l) << '\n';
    std::cout << "Deletion time for vector: " << del(v) << '\n';
    std::cout << "Deletion time for deque: " << del(d) << '\n';

    return 0;
}

Поскольку он использует clock, это должно дать время процессора, а не время стены (хотя некоторые компиляторы, такие как MS VC ++, ошибаются). Он не пытается измерить время для вставки, исключая время, чтобы найти точку вставки, поскольку 1) это заняло бы немного больше работы и 2) я до сих пор не могу понять, чего он достигнет. Это, конечно, не 100% строго, но учитывая несоответствие, которое я вижу из этого, я был бы немного удивлен, увидев существенное отличие от более тщательного тестирования. Например, с MS VC ++ я получаю: 

Insertion time for list: 6.598
Insertion time for vector: 1.377
Insertion time for deque: 1.484

Deletion time for list: 6.348
Deletion time for vector: 0.114
Deletion time for deque: 0.82

С gcc я получаю: 

Insertion time for list: 5.272
Insertion time for vector: 0.125
Insertion time for deque: 0.125

Deletion time for list: 4.259
Deletion time for vector: 0.109
Deletion time for deque: 0.109

Вычисление времени поиска было бы несколько нетривиальным, потому что вам приходилось бы рассчитывать каждую итерацию отдельно. Вам нужно что-то более точное, чем clock (обычно это так), чтобы получить значимые результаты из этого (подробнее о порядке или чтении регистра тактового цикла). Не стесняйтесь вносить изменения, если считаете нужным - как я упоминал выше, у меня нет мотивации, потому что я не понимаю, как это разумно делать.

1 голос
/ 19 марта 2012

Это программа, которую я написал после просмотра этого выступления. Я пытался запустить каждый тест синхронизации в отдельном процессе, чтобы убедиться, что распределители не делают ничего хитрого, чтобы изменить производительность. Я внес поправки в тест, разрешающие синхронизацию генерации случайных чисел. Если вы обеспокоены тем, что это существенно влияет на результаты, вы можете рассчитать время и вычесть время, потраченное там, из остальной части времени. Но я получаю нулевое время, потраченное там на что-либо, кроме очень большого N. Я использовал getrusage (), который, я уверен, не переносим на Windows, но его было бы легко заменить чем-то с помощью clock () или чем угодно. * 

#include <assert.h>
#include <algorithm>
#include <iostream>
#include <list>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <sys/resource.h>


void f(size_t const N)
{
    std::vector<int> c;
    //c.reserve(N);
    for (size_t i = 0; i < N; ++i) {
        int r = rand();
        auto p = std::find_if(c.begin(), c.end(), [=](int a) { return a >= r; });
        c.insert(p, r);
    }
}

void g(size_t const N)
{
    std::list<int> c;
    for (size_t i = 0; i < N; ++i) {
        int r = rand();
        auto p = std::find_if(c.begin(), c.end(), [=](int a) { return a >= r; });
        c.insert(p, r);
    }
}

int h(size_t const N)
{
    int r;
    for (size_t i = 0; i < N; ++i) {
        r = rand();
    }
    return r;
}

double usage()
{
    struct rusage u;
    if (getrusage(RUSAGE_SELF, &u) == -1) std::abort();
    return
        double(u.ru_utime.tv_sec) + (u.ru_utime.tv_usec / 1e6) +
        double(u.ru_stime.tv_sec) + (u.ru_stime.tv_usec / 1e6);
}


int
main(int argc, char* argv[])
{
    assert(argc >= 3);
    std::string const sel = argv[1];
    size_t const N = atoi(argv[2]);

    double t0, t1;
    srand(127);

    if (sel == "vector") {
        t0 = usage();
        f(N);
        t1 = usage();
    } else if (sel == "list") {
        t0 = usage();
        g(N);
        t1 = usage();
    } else if (sel == "rand") {
        t0 = usage();
        h(N);
        t1 = usage();
    } else {
        std::abort();
    }

    std::cout
        << (t1 - t0)
        << std::endl;

    return 0;
}

Чтобы получить набор результатов, я использовал следующий скрипт оболочки. 

seq=`perl -e 'for ($i = 10; $i < 100000; $i *= 1.1) { print int($i), " "; }'`
for i in $seq; do
    vt=`./a.out vector $i`
    lt=`./a.out list $i`
    echo $i $vt $lt
done
...