Lista comparativa global contra lista vinculada para inserciones/eliminaciones aleatorias

Question

Por lo tanto, conozco la pregunta this, y otras sobre SO que se ocupan del problema, pero la mayoría se refieren a las complejidades de las estructuras de datos (solo para copiar aquí, esto tiene teóricamente O (

entiendo las complejidades parecen indicar que la lista sería mejor, pero estoy más preocupado por el rendimiento real

Nota:. esta pregunta se inspiró en slides 45 and 46 of Bjarne Stroustrup's presentation at Going Native 2012 donde habla sobre cómo el almacenamiento en caché de los procesadores y la ubicación de referencia realmente ayudan con los vectores, pero no t en absoluto (o suficiente) con listas.

Pregunta: ¿Hay una buena manera de probar este tiempo de CPU utilizando en lugar de pared del tiempo, y conseguir de una manera decente de "azar" insertar y eliminar elementos que se pueda hacer de antemano por lo que no influye en los tiempos ?

Como beneficio adicional, sería bueno poder aplicar esto a dos estructuras de datos arbitrarias (por ejemplo, mapas vectoriales y de hash o algo así) para encontrar el "rendimiento del mundo real" en algún hardware.

Answer 1

supongo que si yo fuera a probar algo como esto, probablemente me pongo con el código de algo en este orden:

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

Dado que se usa clock, esto debería dar tiempo de procesador no pared del tiempo (aunque algunos compiladores como MS VC++ lo malinterpretan). No trata de medir el tiempo de inserción, excluyendo el tiempo, para encontrar el punto de inserción, ya que 1) eso requeriría un poco más de trabajo y 2) todavía no puedo entender lo que lograría. Ciertamente es no 100% riguroso, pero dada la disparidad que veo en él, me sorprendería un poco ver una diferencia significativa de las pruebas más cuidadosas. Por ejemplo, la MS VC++, me sale:

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 

con gcc me sale:

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 

Factoring el tiempo de búsqueda sería algo no trivial, ya que tendría que el tiempo cada iteración separado . Necesitaría algo más preciso que clock (generalmente lo es) para producir resultados significativos a partir de eso (más sobre el pedido o leyendo un registro de ciclo de reloj). Siéntete libre de modificarlo si lo crees conveniente, como mencioné antes, me falta motivación porque no veo cómo hacer algo sensato.

Answer 2

Este es el programa que escribí después de ver esa charla. Traté de ejecutar cada prueba de tiempo en un proceso separado para asegurarme de que los asignadores no estaban haciendo nada furtivo para alterar el rendimiento. He enmendado el tiempo de permitir la prueba de la generación de números aleatorios. Si le preocupa que esté afectando los resultados de manera significativa, puede cronometrar y restar el tiempo que pasó allí del resto de los tiempos. Pero tengo cero tiempo dedicado allí para cualquier cosa que no sea muy grande. Usé getrusage(), que estoy bastante seguro de que no es portátil para Windows, pero sería fácil sustituirlo por algo usando clock() o lo que quieras.

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

Para obtener un conjunto de resultados utilicé el siguiente script de shell.

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