Pertanyaan Vektor komperhensif vs benchmark linked benchmark untuk sisipan / penghapusan secara acak


Jadi saya sadar ini pertanyaan, dan lain-lain pada SO yang berhubungan dengan masalah, tetapi sebagian besar dari mereka berurusan dengan kompleksitas struktur data (hanya untuk menyalin di sini, terkait ini secara teoritis memiliki O (

Saya memahami kerumitan tampaknya menunjukkan bahwa daftar akan lebih baik, tetapi saya lebih peduli dengan kinerja dunia nyata.

catatan: Pertanyaan ini diinspirasikan oleh slide 45 dan 46 dari presentasi Bjarne Stroustrup di Going Native 2012 di mana dia berbicara tentang bagaimana caching prosesor dan lokalitas referensi sangat membantu dengan vektor, tetapi tidak semuanya (atau cukup) dengan daftar.

Pertanyaan: Apakah ada cara yang baik untuk menguji ini menggunakan waktu CPU dibandingkan dengan waktu dinding, dan mendapatkan cara yang layak "secara acak" memasukkan dan menghapus elemen yang dapat dilakukan sebelumnya sehingga tidak mempengaruhi timing?

Sebagai bonus, akan sangat bagus untuk dapat menerapkan ini ke dua struktur data arbitrary (katakanlah vektor dan peta hash atau sesuatu seperti itu) untuk menemukan "kinerja dunia nyata" pada beberapa perangkat keras.


5
2018-03-19 02:58


asal


Jawaban:


Saya kira jika saya akan menguji sesuatu seperti ini, saya mungkin akan mulai dengan kode sesuatu pada urutan ini:

#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;
}

Karena itu digunakan clock, ini harus memberikan waktu prosesor bukan waktu dinding (meskipun beberapa compiler seperti MS VC + + mendapatkan kesalahan itu). Ini tidak mencoba untuk mengukur waktu untuk penyisipan eksklusif waktu untuk menemukan titik penyisipan, karena 1) yang akan membutuhkan sedikit lebih banyak pekerjaan dan 2) Saya masih tidak tahu apa yang akan dicapai. Itu pasti tidak 100% ketat, tetapi mengingat perbedaan yang saya lihat dari itu, saya akan sedikit terkejut melihat perbedaan yang signifikan dari pengujian yang lebih hati-hati. Misalnya, dengan MS VC ++, saya mendapatkan:

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

Dengan gcc saya dapatkan:

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

Memfaktorkan waktu pencarian akan menjadi hal yang tidak sepele karena Anda harus mengatur waktu setiap iterasi secara terpisah. Anda akan membutuhkan sesuatu yang lebih tepat daripada clock (biasanya) untuk menghasilkan hasil yang berarti dari itu (lebih pada urutan atau membaca daftar jam siklus). Jangan ragu untuk memodifikasi untuk itu jika Anda mau - seperti yang saya sebutkan di atas, saya kurang motivasi karena saya tidak bisa melihat bagaimana hal itu masuk akal untuk dilakukan.


5
2018-03-19 04:37



Ini adalah program yang saya tulis setelah menonton pembicaraan itu. Saya mencoba menjalankan setiap tes waktu dalam proses terpisah untuk memastikan bahwa pengalokasi tidak melakukan sesuatu yang licik untuk mengubah kinerja. Saya telah mengamandemen uji ini memungkinkan waktu pembuatan bilangan acak. Jika Anda khawatir itu mempengaruhi hasil secara signifikan, Anda dapat mengatur waktu dan mengurangi waktu yang dihabiskan di sana dari sisa waktu. Tapi saya mendapatkan nol waktu yang dihabiskan di sana untuk apa pun kecuali N. yang sangat besar Saya menggunakan getrusage () yang saya cukup yakin tidak portabel untuk Windows tetapi akan mudah untuk menggantikan sesuatu menggunakan jam () atau apa pun yang Anda suka.

#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;
}

Untuk mendapatkan serangkaian hasil, saya menggunakan skrip shell berikut.

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

1
2018-03-19 04:59