Requisito previo : unordered_set, unordered_map
C++ proporciona std::unordered_set y std::unordered_map para que se utilicen como conjunto hash y mapa hash respectivamente. Realizan inserción/borrado/acceso en tiempo medio constante.
- Sin embargo, la complejidad del peor de los casos es O(n 2 ).
- La razón es que unordered_map almacena el par clave-valor tomando el módulo del valor de entrada por un número primo y luego lo almacena en una tabla hash.
- Cuando los datos de entrada son grandes y los valores de entrada son múltiplos de este número primo, se producen muchas colisiones y pueden causar la complejidad de O(n 2 ).
- Dependiendo del compilador, el número primo puede ser 107897 o 126271.
Ejemplo 1: Si insertamos múltiplos de los dos números primos anteriores y calculamos el tiempo de ejecución. Uno de los números primos tarda mucho más tiempo que el otro.
C++
// C++ program to determine worst case
// time complexity of an unordered_map
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
int N = 55000;
int prime1 = 107897;
int prime2 = 126271;
void insert(int prime)
{
// Starting the clock
auto start
= high_resolution_clock::now();
unordered_map<int, int> umap;
// Inserting multiples of prime
// number as key in the map
for (int i = 1; i <= N; i++)
umap[i * prime] = i;
// Stopping the clock
auto stop
= high_resolution_clock::now();
// Typecasting the time to
// milliseconds
auto duration
= duration_cast<milliseconds>(
stop - start);
// Time in seconds
cout << "for " << prime << " : "
<< duration.count() / 1000.0
<< " seconds "
<< endl;
}
// Driver code
int main()
{
// Function call for prime 1
insert(prime1);
// Function call for prime 2
insert(prime2);
}
for 107897 : 2.261 seconds for 126271 : 0.024 seconds
Claramente, para uno de los números primos, la complejidad temporal es O(n 2 ).
La función hash incorporada estándar en la que funciona unordered_map es similar a esto:
C++
struct hash {
size_t operator()(uint64_t x)
const { return x; }
};
La función anterior puede producir numerosas colisiones. Las claves insertadas en HashMap no se distribuyen de manera uniforme, y después de insertar numerosos múltiplos primos, la inserción adicional hace que la función hash reasigne todas las claves anteriores a nuevas ranuras, lo que lo hace lento. Entonces, la idea es que tenemos que aleatorizar la función hash.
La idea es usar un método para que las claves en nuestro hashmap se distribuyan uniformemente. Esto evitará que se produzcan colisiones. Para ello utilizamos los números de Fibonacci. La proporción áurea relacionada con la secuencia de Fibonacci ( Phi = 1.618 ) tiene la propiedad de que puede subdividir cualquier rango de manera uniforme sin regresar a la posición inicial.
Podemos crear nuestra propia función hash simple. A continuación se muestra la función hash:
C++
struct modified_hash {
static uint64_t splitmix64(uint64_t x)
{
// 0x9e3779b97f4a7c15,
// 0xbf58476d1ce4e5b9,
// 0x94d049bb133111eb are numbers
// that are obtained by dividing
// high powers of two with Phi
// (1.6180..) In this way the
// value of x is modified
// to evenly distribute
// keys in hash table
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
int operator()(uint64_t x) const
{
static const uint64_t random
= steady_clock::now()
.time_since_epoch()
.count();
// The above line generates a
// random number using
// high precision clock
return splitmix64(
// It returns final hash value
x + random);
}
};
Básicamente, la función hash anterior genera valores hash aleatorios para almacenar claves. Para saber más sobre esto, consulte este artículo Hashing de Fibonacci.
Ejemplo 2: Usando la función hash anterior, el programa se ejecuta muy rápido.
C++
// C++ program to determine worst case
// time complexity of an unordered_map
// using modified hash function
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
struct modified_hash {
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30))
* 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27))
* 0x94d049bb133111eb;
return x ^ (x >> 31);
}
int operator()(uint64_t x) const
{
static const uint64_t random
= steady_clock::now()
.time_since_epoch()
.count();
return splitmix64(x + random);
}
};
int N = 55000;
int prime1 = 107897;
int prime2 = 126271;
// Function to insert in the hashMap
void insert(int prime)
{
auto start = high_resolution_clock::now();
// Third argument in initialisation
// of unordered_map ensures that
// the map uses the hash function
unordered_map<int, int, modified_hash>
umap;
// Inserting multiples of prime
// number as key in the map
for (int i = 1; i <= N; i++)
umap[i * prime] = i;
auto stop
= high_resolution_clock::now();
auto duration
= duration_cast<milliseconds>(
stop - start);
cout << "for " << prime << " : "
<< duration.count() / 1000.0
<< " seconds "
<< endl;
}
// Driver Code
int main()
{
// Function call for prime 1
insert(prime1);
// Function call for prime 2
insert(prime2);
}
for 107897 : 0.025 seconds for 126271 : 0.024 seconds
De forma predeterminada, la capacidad de unordered_map es 16 y se crea una tabla hash para esto. Pero cada vez que se alcanza el umbral, la capacidad de unordered_map se duplica y todos los valores se repiten de acuerdo con la nueva tabla hash.
Por lo tanto, podemos reservar la capacidad de antemano de acuerdo con nuestro tamaño de entrada utilizando el método .reserve().
umap.reserve(1024);
1024 se puede reemplazar por cualquier valor int según el tamaño de entrada. Esto evita el refrito y la asignación dinámica, lo que hace que el programa sea más eficiente.
max_load_factor de unordered_map determina la probabilidad de colisión. El valor predeterminado se establece en 1.
Al establecerlo en un valor más bajo, como 0,25, puede disminuir en gran medida la probabilidad de colisiones.
umap.max_load_factor(0.25);
Ejemplo: el uso de los dos métodos anteriores puede hacer que umap sea más rápido:
C++
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
int N = 55000;
int prime1 = 107897;
int prime2 = 126271;
void insert(int prime)
{
// Starting the clock
auto start
= high_resolution_clock::now();
unordered_map<int, int> umap;
umap.reserve(1024); // RESERVING SPACE BEFOREHAND
umap.max_load_factor(0.25); // DECREASING MAX_LOAD_FACTOR
// Inserting multiples of prime
// number as key in the map
for (int i = 1; i <= N; i++)
umap[i * prime] = i;
// Stopping the clock
auto stop
= high_resolution_clock::now();
// Typecasting the time to
// milliseconds
auto duration
= duration_cast<milliseconds>(
stop - start);
// Time in seconds
cout << "for " << prime << " : "
<< duration.count() / 1000.0
<< " seconds "
<< endl;
}
// Driver code
int main()
{
// Function call for prime 1
insert(prime1);
// Function call for prime 2
insert(prime2);
}
Producción :
for 107897 : 0.029 seconds for 126271 : 0.026 seconds
Publicación traducida automáticamente
Artículo escrito por gurankit_pal_singh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA