c++ - online - complejidad de algoritmos pdf

Algoritmo O(N) más lento que el algoritmo O(N logN)

Question

En un conjunto de números, cada número aparece incluso una cantidad de veces, y solo un número aparece como número impar de veces. Necesitamos encontrar ese número (la pregunta fue discutida previamente en Desbordamiento de pila ).

Aquí hay una solución que resuelve la pregunta con 3 métodos diferentes: dos métodos son O (N) (hash_set y hash_map), mientras que uno es O (NlogN) (clasificación). Sin embargo, la creación de perfiles para entradas arbitrariamente grandes muestra que la clasificación es más rápida y se vuelve más y más rápida (en comparación) a medida que aumenta la entrada.

¿Qué hay de malo con la implementación o el análisis de complejidad? ¿Por qué el método O (NlogN) es más rápido?

#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;

class ScopedTimer {
public:
    ScopedTimer(const string& name)
    : name_(name), start_time_(high_resolution_clock::now()) {}

    ~ScopedTimer() {
        cout << name_ << " took "
        << std::chrono::duration_cast<milliseconds>(
                                                    high_resolution_clock::now() - start_time_).count()
        << " milliseconds" << endl;
    }

private:
    const string name_;
    const high_resolution_clock::time_point start_time_;
};

int find_using_hash(const vector<int>& input_data) {
    unordered_set<int> numbers(input_data.size());
    for(const auto& value : input_data) {
        auto res = numbers.insert(value);
        if(!res.second) {
            numbers.erase(res.first);
        }
    }
    return numbers.size() == 1 ? *numbers.begin() : -1;
}

int find_using_hashmap(const vector<int>& input_data) {
    unordered_map<int,int> counter_map;
    for(const auto& value : input_data) {
        ++counter_map[value];
    }
    for(const auto& map_entry : counter_map) {
        if(map_entry.second % 2 == 1) {
            return map_entry.first;
        }
    }
    return -1;
}

int find_using_sort_and_count(const vector<int>& input_data) {
    vector<int> local_copy(input_data);
    std::sort(local_copy.begin(), local_copy.end());
    int prev_value = local_copy.front();
    int counter = 0;
    for(const auto& value : local_copy) {
        if(prev_value == value) {
            ++counter;
            continue;
        }

        if(counter % 2 == 1) {
            return prev_value;
        }

        prev_value = value;
        counter = 1;
    }
    return counter == 1 ? prev_value : -1;
}

void execute_and_time(const string& method_name, std::function<int()> method) {
    ScopedTimer timer(method_name);
    cout << method_name << " returns " << method() << endl;
}

int main()
{
    vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});

    for(const auto& input_size : input_size_vec) {
        // Prepare input data
        std::vector<int> input_data;
        const int magic_number = 123454321;
        for(int i=0;i<input_size;++i) {
            input_data.push_back(i);
            input_data.push_back(i);
        }
        input_data.push_back(magic_number);
        std::random_shuffle(input_data.begin(), input_data.end());
        cout << "For input_size " << input_size << ":" << endl;

        execute_and_time("hash-set:",std::bind(find_using_hash, input_data));
        execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, input_data));
        execute_and_time("hash-map:",std::bind(find_using_hashmap, input_data));

        cout << "--------------------------" << endl;
    }
    return 0;
}

Resultados de perfiles:

sh$ g++ -O3 -std=c++11 -o main *.cc
sh$ ./main 
For input_size 262144:
hash-set: returns 123454321
hash-set: took 107 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 37 milliseconds
hash-map: returns 123454321
hash-map: took 109 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 173 milliseconds
hash-map: returns 123454321
hash-map: took 731 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 3250 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 745 milliseconds
hash-map: returns 123454321
hash-map: took 3631 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 14528 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 3238 milliseconds
hash-map: returns 123454321
hash-map: took 16483 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 350305 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 60396 milliseconds
hash-map: returns 123454321
hash-map: took 427841 milliseconds
--------------------------

Adición

La solución rápida con xor sugerida por @Matt está, por supuesto, fuera del concurso: menos de 1 segundo para el peor de los casos, por ejemplo:

int find_using_xor(const vector<int>& input_data) {
    int output = 0;
    for(const int& value : input_data) {
        output = output^value;
    }
    return output;
}
For input_size 268435456:
xor: returns 123454321
xor: took 264 milliseconds

pero la pregunta sigue en pie: ¿por qué el hash es tan ineficiente en comparación con la clasificación en la práctica a pesar de la ventaja de la complejidad algorítmica teórica?

Answer 1

Comencemos mirando los números para la solución de clasificación. En la tabla a continuación, la primera columna es la relación de tamaño. Se calcula calculando NlogN para una prueba determinada y dividiendo por NlogN para la primera prueba. La segunda columna es la relación de tiempo entre una prueba dada y la primera prueba.

 NlogN size ratio      time ratio
   4*20/18 =  4.4     173 / 37 =  4.7
  16*22/18 = 19.6     745 / 37 = 20.1
  64*24/18 = 85.3    3238 / 37 = 87.5
1024*28/18 = 1590   60396 / 37 = 1630

Puede ver que hay una muy buena concordancia entre las dos proporciones, lo que indica que la rutina de clasificación es de hecho O (NlogN) .

Entonces, ¿por qué las rutinas hash no funcionan como se esperaba? Simple, la noción de que extraer un elemento de una tabla hash es O (1) es pura fantasía. El tiempo real de extracción depende de la calidad de la función hashing y del número de bins en la tabla hash. El tiempo real de extracción va de O (1) a O (N) , donde el peor de los casos ocurre cuando todas las entradas en la tabla hash terminan en el mismo contenedor. Por lo tanto, si utiliza una tabla hash, debe esperar que su rendimiento esté entre O (N) y O (N ^ 2), lo que parece ajustarse a sus datos, como se muestra a continuación.

 O(N)  O(NlogN)  O(N^2)  time
   4     4.4       16       6
  16      20      256      30
  64      85     4096     136
1024    1590     10^6    3274

Tenga en cuenta que la relación de tiempo está en el extremo inferior del rango, lo que indica que la función de almohadilla funciona bastante bien.

Answer 2

Ejecuté el programa a través de valgrind con diferentes tamaños de entrada, y obtuve estos resultados para recuentos de ciclos:

with 1<<16 values:
  find_using_hash: 27 560 872
  find_using_sort: 17 089 994
  sort/hash: 62.0%

with 1<<17 values:
  find_using_hash: 55 105 370
  find_using_sort: 35 325 606
  sort/hash: 64.1%

with 1<<18 values:
  find_using_hash: 110 235 327
  find_using_sort:  75 695 062
  sort/hash: 68.6%

with 1<<19 values:
  find_using_hash: 220 248 209
  find_using_sort: 157 934 801
  sort/hash: 71.7%

with 1<<20 values:
  find_using_hash: 440 551 113
  find_using_sort: 326 027 778
  sort/hash: 74.0%

with 1<<21 values:
  find_using_hash: 881 086 601
  find_using_sort: 680 868 836
  sort/hash: 77.2%

with 1<<22 values:
  find_using_hash: 1 762 482 400
  find_using_sort: 1 420 801 591
  sort/hash: 80.6%

with 1<<23 values:
  find_using_hash: 3 525 860 455
  find_using_sort: 2 956 962 786
  sort/hash: 83.8%

Esto indica que el tiempo de ordenación está superando lentamente el tiempo hash, al menos teóricamente. Con mi compilador / biblioteca particular (gcc 4.8.2 / libsddc ++) y la optimización (-O2), los métodos de clasificación y hash serían de la misma velocidad con alrededor de 2 ^ 28 valores, lo que está al límite de lo que estás intentando. Sospecho que otros factores del sistema entran en juego cuando se utiliza esa cantidad de memoria, lo que dificulta la evaluación en el tiempo real de pared.

Answer 3

El hecho de que O(N) fuera aparentemente más lento que O(N logN) me estaba volviendo loco, así que decidí profundizar en el problema.

Hice este análisis en Windows con Visual Studio, pero apuesto a que los resultados serían muy similares en Linux con g ++.

En primer lugar, utilicé Very Sleepy para encontrar las piezas de código que más se ejecutan durante el ciclo for en find_using_hash() . Esto es lo que vi:

Como puede ver, las entradas superiores están todas relacionadas con las listas (se llama a RtlAllocateHeap desde el código de la lista). Aparentemente, el problema es que para cada inserción en el conjunto unordered_set y dado que los segmentos se implementan como listas, se realiza una asignación para un nodo y esto dispara la duración del algoritmo, en oposición al tipo que no hace asignaciones.

Para estar seguro de que este era el problema, escribí una implementación MUY simple de una tabla hash sin asignaciones, y los resultados fueron mucho más razonables:

Así que ahí está, el factor log N multiplicando N que en su ejemplo más grande (es decir, 1<<28 ) es 28, es aún más pequeño que la cantidad "constante" de trabajo requerida para una asignación.

Answer 4

Este análisis es sustancialmente el mismo que el realizado por el user3386199 en su answer . Es el análisis que habría realizado independientemente de su respuesta, pero él llegó primero.

Ejecuté el programa en mi máquina (HP Z420 con un derivado de Ubuntu 14.04 LTE) y agregué una salida para 1<<26 , así que tengo un conjunto diferente de números, pero las proporciones son notablemente similares a las proporciones de los datos en el publicación original. Los tiempos crudos que obtuve fueron (archivo on-vs-logn.raw.data ):

For input_size 262144:
hash-set: returns 123454321
hash-set: took 45 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
hash-map: returns 123454321
hash-map: took 61 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 372 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 154 milliseconds
hash-map: returns 123454321
hash-map: took 390 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 1921 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 680 milliseconds
hash-map: returns 123454321
hash-map: took 1834 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 8356 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2970 milliseconds
hash-map: returns 123454321
hash-map: took 9045 milliseconds
--------------------------
For input_size 67108864:
hash-set: returns 123454321
hash-set: took 37582 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 12842 milliseconds
hash-map: returns 123454321
hash-map: took 46480 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 172329 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 53856 milliseconds
hash-map: returns 123454321
hash-map: took 211191 milliseconds
--------------------------

real    11m32.852s
user    11m24.687s
sys     0m8.035s

awk.analysis.sh un script, awk.analysis.sh , para analizar los datos:

#!/bin/sh

awk ''
BEGIN { printf("%9s  %8s  %8s  %8s  %8s  %8s  %8s  %9s  %9s  %9s  %9s/n",
               "Size", "Sort Cnt", "R:Sort-C", "Hash Set", "R:Hash-S", "Hash Map",
               "R:Hash-M", "O(N)", "O(NlogN)", "O(N^3/2)", "O(N^2)")
}
/input_size/           { if (old_size   == 0) old_size   = $3; size       = $3 }
/hash-set: took/       { if (o_hash_set == 0) o_hash_set = $3; t_hash_set = $3 }
/sort-and-count: took/ { if (o_sort_cnt == 0) o_sort_cnt = $3; t_sort_cnt = $3 }
/hash-map: took/       { if (o_hash_map == 0) o_hash_map = $3; t_hash_map = $3 }
/^----/ {
    o_n = size / old_size
    o_nlogn = (size * log(size)) / (old_size * log(old_size))
    o_n2    = (size * size) / (old_size * old_size)
    o_n32   = (size * sqrt(size)) / (old_size * sqrt(old_size))
    r_sort_cnt = t_sort_cnt / o_sort_cnt
    r_hash_map = t_hash_map / o_hash_map
    r_hash_set = t_hash_set / o_hash_set
    printf("%9d  %8d  %8.2f  %8d  %8.2f  %8d  %8.2f  %9.0f  %9.2f  %9.2f  %9.0f/n",
           size, t_sort_cnt, r_sort_cnt, t_hash_set, r_hash_set,
           t_hash_map, r_hash_map, o_n, o_nlogn, o_n32, o_n2)
}'' < on-vs-logn.raw.data

La salida del programa es bastante amplia, pero da:

     Size  Sort Cnt  R:Sort-C  Hash Set  R:Hash-S  Hash Map  R:Hash-M       O(N)   O(NlogN)   O(N^3/2)     O(N^2)
   262144        34      1.00        45      1.00        61      1.00          1       1.00       1.00          1
  1048576       154      4.53       372      8.27       390      6.39          4       4.44       8.00         16
  4194304       680     20.00      1921     42.69      1834     30.07         16      19.56      64.00        256
 16777216      2970     87.35      8356    185.69      9045    148.28         64      85.33     512.00       4096
 67108864     12842    377.71     37582    835.16     46480    761.97        256     369.78    4096.00      65536
268435456     53856   1584.00    172329   3829.53    211191   3462.15       1024    1592.89   32768.00    1048576

Está razonablemente claro que en esta plataforma, los algoritmos hash set y hash map no son O (N), ni tan buenos como O (N.logN), pero son mejores que O (N ^3/2 ) y mucho menos O (N ² ). Por otro lado, el algoritmo de clasificación está muy cerca de O (N.logN) de hecho.

Solo puede atribuirlo a una deficiencia teórica en el conjunto de hash y el código de mapa hash, o un tamaño inadecuado de las tablas hash para que utilicen un tamaño de tabla hash no óptimo. Valdría la pena investigar qué mecanismos existen para preasignar el conjunto de hash y el mapa de hash para ver si el uso afecta el rendimiento. (Consulte también información adicional a continuación).

Y, solo para el registro, aquí está el resultado del script de análisis sobre los datos originales:

     Size  Sort Cnt  R:Sort-C  Hash Set  R:Hash-S  Hash Map  R:Hash-M       O(N)   O(NlogN)   O(N^3/2)     O(N^2)
   262144        37      1.00       107      1.00       109      1.00          1       1.00       1.00          1
  1048576       173      4.68       641      5.99       731      6.71          4       4.44       8.00         16
  4194304       745     20.14      3250     30.37      3631     33.31         16      19.56      64.00        256
 16777216      3238     87.51     14528    135.78     16483    151.22         64      85.33     512.00       4096
268435456     60396   1632.32    350305   3273.88    427841   3925.15       1024    1592.89   32768.00    1048576

Pruebas adicionales muestran que se modifican las funciones hash como se muestra:

int find_using_hash(const vector<int>& input_data) {
    unordered_set<int> numbers;
    numbers.reserve(input_data.size());

y:

int find_using_hashmap(const vector<int>& input_data) {
    unordered_map<int,int> counter_map;
    counter_map.reserve(input_data.size());

produce un análisis como este:

     Size  Sort Cnt  R:Sort-C  Hash Set  R:Hash-S  Hash Map  R:Hash-M       O(N)   O(NlogN)   O(N^3/2)     O(N^2)
   262144        34      1.00        42      1.00        80      1.00          1       1.00       1.00          1
  1048576       155      4.56       398      9.48       321      4.01          4       4.44       8.00         16
  4194304       685     20.15      1936     46.10      1177     14.71         16      19.56      64.00        256
 16777216      2996     88.12      8539    203.31      5985     74.81         64      85.33     512.00       4096
 67108864     12564    369.53     37612    895.52     28808    360.10        256     369.78    4096.00      65536
268435456     53291   1567.38    172808   4114.48    124593   1557.41       1024    1592.89   32768.00    1048576

Claramente, reservar el espacio para el mapa hash es beneficioso.

El código del conjunto hash es bastante diferente; agrega un elemento aproximadamente la mitad del tiempo (total), y ''agrega'' y luego elimina un elemento la otra mitad del tiempo. Esto es más trabajo que el código de mapa hash tiene que hacer, por lo que es más lento. Esto también significa que el espacio reservado es más grande de lo realmente necesario y puede explicar el rendimiento degradado con el espacio reservado.

Answer 5

Realmente depende de la implementación de hash_map / hash_set. Al reemplazar el comando unordered_{map,set} libstdc ++ con dense_hash_{map,set} Google, es significativamente más rápido que el sort . El inconveniente de dense_hash_xxx es que requieren que haya dos valores para la clave que nunca se utilizarán. Ver su documento para más detalles.

Otra cosa que hay que recordar es que hash_{map,set} generalmente realiza una gran cantidad de asignaciones / desasignaciones dinámicas de memoria, por lo que es mejor usar una alternativa mejor al malloc/free predeterminado de libc, por ejemplo, el tcmalloc de Google o el jemalloc de Facebook.

hidden $ g++ -O3 -std=c++11 xx.cpp /usr/lib/libtcmalloc_minimal.so.4
hidden $ ./a.out 
For input_size 262144:
unordered-set: returns 123454321
unordered-set: took 35 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 18 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
unordered-map: returns 123454321
unordered-map: took 36 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 13 milliseconds
--------------------------
For input_size 1048576:
unordered-set: returns 123454321
unordered-set: took 251 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 77 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 153 milliseconds
unordered-map: returns 123454321
unordered-map: took 220 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 60 milliseconds
--------------------------
For input_size 4194304:
unordered-set: returns 123454321
unordered-set: took 1453 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 357 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 596 milliseconds
unordered-map: returns 123454321
unordered-map: took 1461 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 296 milliseconds
--------------------------
For input_size 16777216:
unordered-set: returns 123454321
unordered-set: took 6664 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 1751 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2513 milliseconds
unordered-map: returns 123454321
unordered-map: took 7299 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 1364 milliseconds
--------------------------
tcmalloc: large alloc 1073741824 bytes == 0x5f392000 @ 
tcmalloc: large alloc 2147483648 bytes == 0x9f392000 @ 
tcmalloc: large alloc 4294967296 bytes == 0x11f392000 @ 
For input_size 268435456:
tcmalloc: large alloc 4586348544 bytes == 0x21fb92000 @ 
unordered-set: returns 123454321
unordered-set: took 136271 milliseconds
tcmalloc: large alloc 8589934592 bytes == 0x331974000 @ 
tcmalloc: large alloc 2147483648 bytes == 0x21fb92000 @ 
dense-hash-set: returns 123454321
dense-hash-set: took 34641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 47606 milliseconds
tcmalloc: large alloc 2443452416 bytes == 0x21fb92000 @ 
unordered-map: returns 123454321
unordered-map: took 176066 milliseconds
tcmalloc: large alloc 4294967296 bytes == 0x331974000 @ 
dense-hash-map: returns 123454321
dense-hash-map: took 26460 milliseconds
--------------------------

Código:

#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

#include <google/dense_hash_map>
#include <google/dense_hash_set>

using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
using google::dense_hash_map;
using google::dense_hash_set;

class ScopedTimer {
public:
    ScopedTimer(const string& name)
    : name_(name), start_time_(high_resolution_clock::now()) {}

    ~ScopedTimer() {
        cout << name_ << " took "
        << std::chrono::duration_cast<milliseconds>(
                                                    high_resolution_clock::now() - start_time_).count()
        << " milliseconds" << endl;
    }

private:
    const string name_;
    const high_resolution_clock::time_point start_time_;
};

int find_using_unordered_set(const vector<int>& input_data) {
    unordered_set<int> numbers(input_data.size());
    for(const auto& value : input_data) {
        auto res = numbers.insert(value);
        if(!res.second) {
            numbers.erase(res.first);
        }
    }
    return numbers.size() == 1 ? *numbers.begin() : -1;
}

int find_using_unordered_map(const vector<int>& input_data) {
    unordered_map<int,int> counter_map;
    for(const auto& value : input_data) {
        ++counter_map[value];
    }
    for(const auto& map_entry : counter_map) {
        if(map_entry.second % 2 == 1) {
            return map_entry.first;
        }
    }
    return -1;
}

int find_using_dense_hash_set(const vector<int>& input_data) {
    dense_hash_set<int> numbers(input_data.size());
    numbers.set_deleted_key(-1);
    numbers.set_empty_key(-2);
    for(const auto& value : input_data) {
        auto res = numbers.insert(value);
        if(!res.second) {
            numbers.erase(res.first);
        }
    }
    return numbers.size() == 1 ? *numbers.begin() : -1;
}

int find_using_dense_hash_map(const vector<int>& input_data) {
    dense_hash_map<int,int> counter_map;
    counter_map.set_deleted_key(-1);
    counter_map.set_empty_key(-2);
    for(const auto& value : input_data) {
        ++counter_map[value];
    }
    for(const auto& map_entry : counter_map) {
        if(map_entry.second % 2 == 1) {
            return map_entry.first;
        }
    }
    return -1;
}

int find_using_sort_and_count(const vector<int>& input_data) {
    vector<int> local_copy(input_data);
    std::sort(local_copy.begin(), local_copy.end());
    int prev_value = local_copy.front();
    int counter = 0;
    for(const auto& value : local_copy) {
        if(prev_value == value) {
            ++counter;
            continue;
        }

        if(counter % 2 == 1) {
            return prev_value;
        }

        prev_value = value;
        counter = 1;
    }
    return counter == 1 ? prev_value : -1;
}

void execute_and_time(const string& method_name, std::function<int()> method) {
    ScopedTimer timer(method_name);
    cout << method_name << " returns " << method() << endl;
}

int main()
{
    vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});

    for(const auto& input_size : input_size_vec) {
        // Prepare input data
        std::vector<int> input_data;
        const int magic_number = 123454321;
        for(int i=0;i<input_size;++i) {
            input_data.push_back(i);
            input_data.push_back(i);
        }
        input_data.push_back(magic_number);
        std::random_shuffle(input_data.begin(), input_data.end());
        cout << "For input_size " << input_size << ":" << endl;

        execute_and_time("unordered-set:",std::bind(find_using_unordered_set, std::cref(input_data)));
        execute_and_time("dense-hash-set:",std::bind(find_using_dense_hash_set, std::cref(input_data)));
        execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, std::cref(input_data)));
        execute_and_time("unordered-map:",std::bind(find_using_unordered_map, std::cref(input_data)));
        execute_and_time("dense-hash-map:",std::bind(find_using_dense_hash_map, std::cref(input_data)));

        cout << "--------------------------" << endl;
    }
    return 0;
}

Answer 6

Ya hay muchas respuestas excelentes, pero este es el tipo especial de pregunta que naturalmente genera muchas respuestas válidas.

Y estoy escribiendo para proporcionar una respuesta desde una perspectiva matemática (lo cual es difícil de hacer sin LaTeX), porque es importante corregir la idea falsa no abordada de que resolver el problema dado con hashes representa un problema que es "teóricamente" O(n) , pero de alguna manera "prácticamente" peor que O(n) . ¡Tal cosa sería una imposibilidad matemática!

Para aquellos que deseen profundizar en el tema, recomiendo este libro que guardé y compré como un estudiante de secundaria muy pobre, y que avivó mi interés en las matemáticas aplicadas durante muchos años por venir, esencialmente cambiando el resultado de mi vida. : http://www.amazon.com/Analysis-Algorithms-Monographs-Computer-Science/dp/0387976876

Para entender por qué el problema no es "teóricamente" O(n) , es necesario tener en cuenta que la suposición subyacente también es falsa: no es cierto que los hash sean "teóricamente" una estructura de datos O(1) .

Lo opuesto es verdad. Los hashes, en su forma pura, son solo "prácticamente" una estructura de datos O(1) , pero teóricamente todavía son una estructura de datos O(n) . (Nota: en forma híbrida, pueden lograr un rendimiento teórico de O(log n) .)

Por lo tanto, la solución sigue siendo, en el mejor de los casos, un problema O(n log n) , ya que n aproxima al infinito.

¡Puede comenzar a responder, pero todos saben que los hashes son O (1)!

Entonces, permítanme explicar cómo esa afirmación es verdadera, pero en el sentido práctico, no teórico .

Para cualquier aplicación (independientemente de n , siempre que n se conozca con anticipación -lo que llaman "fijo" en lugar de "arbitrario" en pruebas matemáticas), puede diseñar su tabla hash para que coincida con la aplicación y obtener O(1) rendimiento dentro de las limitaciones de ese entorno. Cada estructura hashing pura está diseñada para funcionar bien dentro de un rango a priori de tamaños de conjunto de datos y con la supuesta independencia de claves con respecto a la función hash.

Pero cuando dejas que n acerque al infinito, como lo exige la definición de notación Big- O , los cubos comienzan a llenarse (lo cual debe suceder según el principio de casillero) y cualquier estructura purificada pura se descompone en un algoritmo O(n) ( la notación Big- O aquí ignora el factor constante que depende de cuántos cubos hay).

Whoa! Hay mucho en esa oración.

Y entonces, en este punto, en lugar de ecuaciones, una analogía apropiada sería más útil:

Una comprensión matemática muy precisa de las tablas hash se obtiene imaginando un archivador que contiene 26 cajones, uno para cada letra del alfabeto. Cada archivo se almacena dentro del cajón que corresponde a la primera letra en el nombre del archivo.

• La "función hash" es una operación O(1) , mirando la primera letra.

• El almacenamiento es una operación O(1) : coloca el archivo dentro del cajón para esa letra.

• Y mientras no haya más de un archivo dentro de cada cajón , la recuperación es una operación O(1) : abrir el cajón para esa letra.

Dentro de estas restricciones de diseño, esta estructura hash es O(1) .

Ahora suponga que excede las restricciones de diseño para esta estructura de hashing "archivador" y ha almacenado varios cientos de archivos. El almacenamiento ahora requiere tantas operaciones como sea necesario para encontrar un espacio vacío en cada cajón, y la recuperación requiere tantas operaciones como la cantidad de elementos dentro de cada cajón.

En comparación con tirar todos los archivos en una sola gran pila, el rendimiento promedio en general es aproximadamente mejor por un factor de 1/26 de ese tiempo. Pero recuerde, matemáticamente, uno no puede decir O(n/26) , porque la notación O(n) por definición no toma en consideración los factores constantes que afectan el rendimiento, sino solo la complejidad algorítmica como una función de n . Entonces, cuando se exceden las restricciones de diseño, la estructura de datos es O(n) .