Funcionalidad de inserción/función hash unordered_map miserable

He estado escribiendo un algoritmo de procesamiento de imagen ahora, y en algún momento tuve que recopilar información estadística sobre los píxeles transformados para obtener más información sobre la dirección que debería seguir con el desarrollo posterior . El tipo de información que necesitaba para recoger estaba en el formato:Funcionalidad de inserción/función hash unordered_map miserable

key: RGB value 
value: int

Lo que hice, estaba abrí la imagen transformada y iterado a través de él, el ahorro de los valores que necesitaba para std::unordered_map que tiene la firma siguiente:

typedef std::unordered_map<boost::gil::rgb8_pixel_t, unsigned int> pixel_map_t;

En un bucle:

for(int y = 0; y < vi.height(); y++) { 
    SrcView::x_iterator dst_it = src.row_begin(y); 
    for(int x = 0; x < vi.width(); x++, hits++) { 
     diff_map.insert(std::make_pair(dst_it[x], /* some uint32 */)); 
    }

que escribir también una función hash personalizado (que era una función hash perfecta: 256^2 x R + 256 x G + B - por lo que el Collis iones deben ser mínimos independientemente de los cubos y el diseño de hashtable (en una extensión razonable).

¡Lo que noté, fue que la inserción fue miserablemente lenta! - después de alcanzar la iteración 11'th, la velocidad de inserción se ha degradado en aproximadamente 100x. ¡Tuve una gran cantidad de colisiones! A pesar de la muy pequeña cantidad de colores duplicados en la imagen.

Después, quise eliminar cualquier posible error dentro de mi código, y comencé a comparar el unordered_map usando las funciones hash STL con tipos de teclas primitivas como int.

El código para el punto de referencia era:

std::size_t hits = 0, colls = 0; 
for(int y = 0; y < vi.height(); y++) { 
    SrcView::x_iterator dst_it = src.row_begin(y); 

    for(int x = 0; x < vi.width(); x++, hits++) { 
     if(diff_map.find(x*y) != diff_map.cend()) 
      colls++; 
     diff_map.insert(std::make_pair(x*y, 10)); 
    } 
    std::cout << y << "/" << vi.height() << " -> buckets: " 
       << diff_map.bucket_count() << "(" 
       << std::floor(diff_map.load_factor() * 100) 
       << "% load factor) [ " << colls << " collisions/" << hits << " hits ]" << std::endl; 
}

... y aquí están los resultados para las primeras 20 iteraciones del bucle externo (función hash utilizando solamente de STL para la clave-int mecanografiado):

0/480 -> buckets: 8(12% load factor) [ 639 collisions/640 hits ] 
1/480 -> buckets: 4096(15% load factor) [ 640 collisions/1280 hits ] 
2/480 -> buckets: 4096(23% load factor) [ 960 collisions/1920 hits ] 
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions/2560 hits ] 
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions/3200 hits ] 
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions/3840 hits ] 
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions/4480 hits ] 
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions/5120 hits ] 
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions/5760 hits ] 
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions/6400 hits ] 
10/480 -> buckets: 4096(77% load factor) [ 3872 collisions/7040 hits ] 
11/480 -> buckets: 4096(85% load factor) [ 4161 collisions/7680 hits ] 
12/480 -> buckets: 4096(90% load factor) [ 4612 collisions/8320 hits ] 
13/480 -> buckets: 4096(99% load factor) [ 4901 collisions/8960 hits ] 
14/480 -> buckets: 32768(13% load factor) [ 5315 collisions/9600 hits ] 
15/480 -> buckets: 32768(13% load factor) [ 5719 collisions/10240 hits ] 
16/480 -> buckets: 32768(14% load factor) [ 6148 collisions/10880 hits ] 
17/480 -> buckets: 32768(15% load factor) [ 6420 collisions/11520 hits ] 
18/480 -> buckets: 32768(16% load factor) [ 6870 collisions/12160 hits ] 
19/480 -> buckets: 32768(17% load factor) [ 7135 collisions/12800 hits ] 
20/480 -> buckets: 32768(17% load factor) [ 7584 collisions/13440 hits ] 
21/480 -> buckets: 32768(18% load factor) [ 7993 collisions/14080 hits ]

¿No es el número de colisiones demasiado alto en este caso? Las bibliotecas STL en general son de alta calidad, pero tienen 639/640 y 640/1280 para un sonido de clave basado en int simple al menos extraño. O tal vez estoy haciendo algo mal?

y esta fue mi función hash (en teoría, no debería tener colisiones en absoluto - pero los números eran muy cerca):

template<> 
struct std::hash<boost::gil::rgb8_pixel_t> : 
    public std::unary_function<const boost::gil::rgb8_pixel_t&, size_t> 
{ 
    size_t operator()(const boost::gil::rgb8_pixel_t& key) const 
    { 
     size_t ret = (static_cast<size_t>(key[0]) << 16) | 
         (static_cast<size_t>(key[1]) << 8) | 
         (static_cast<size_t>(key[2])); 
     //return 256 * 256 * key[0] + 256 * key[1] + key[2]; 
     return ret; 
    } 
};

Ahora, esto ya no es divertido. ..

escribí esta función hash:

template<> 
struct std::hash<int> : 
    public std::unary_function<const int&, size_t> 
{ 
    size_t operator()(const int& key) const 
    { 
     return 5; 
    } 
};

En teoría, debería tener una tasa de colisiones del 100%, ¿verdad? pero los resultados son:

0/480 -> buckets: 8(12% load factor) [ 639 collisions/640 hits ] 
1/480 -> buckets: 4096(15% load factor) [ 640 collisions/1280 hits ] 
2/480 -> buckets: 4096(23% load factor) [ 960 collisions/1920 hits ] 
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions/2560 hits ] 
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions/3200 hits ] 
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions/3840 hits ] 
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions/4480 hits ] 
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions/5120 hits ] 
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions/5760 hits ] 
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions/6400 hits ]

¿Por qué?

Env: MSVS2010

Fuente

2011-05-21 Karim Agha

Su punto de referencia es defectuoso. Para y == 0 inserta 640 veces 'std :: make_pair (x * y, 10)', que es 'make_pair (0,10)'. Se esperan 639 colisiones. No busqué más, suponiendo que el archivo restante de su código es igualmente defectuoso – hirschhornsalz

El hashmap que ha proporcionado está muy lejos de una función hash perfecta, a menos que tenga una tabla hash de cubo 2^24. Para cualquier tabla que sea una potencia de dos (que parece ser el caso), lo que está haciendo es ignorar el componente rojo y parte del verde. Si tiene una imagen que contiene todos los tonos de rojo, todos los píxeles colisionarán, por ejemplo ... –

(((r + 2)^37)% 4294967291)^(((g + 2)^37)% 4294967291)^(((b + 2)^37)% 4294967291) sería lento, pero daría como resultado una mezcla excelente. :-) – Omnifarious

colls no está midiendo colisiones. Si desea medir colisiones, para cada cubo b en el rango [0, bucket_count()), obtenga bucket_size(b). Eso le dirá cuántos artículos hay en cada cubo. Si hay 2 o más elementos en el cucharón, entonces tiene bucket_size(b) - 1 colisiones para el cucharón b.

Fuente

2011-05-22 00:46:19

¡Gracias! ahora los resultados son más realistas, hasta la 52.a iteración apenas tuve colisiones, –

Si entiendo lo que estás haciendo correctamente, son posiblemente sólo conseguir estas colisiones debido a que muchos píxeles de la imagen tienen el mismo color y que están llamando repetidamente diff_map.insert para el mismo color (por lo que la calidad de su valor de hash es irrelevante).Si está haciendo esto para calcular el histograma de colores, probablemente no desee hacer "diff_map.insert (std :: make_pair (dst_it [x],/* some uint32 * /));", sino simplemente hacer algo como

auto it = diff_map.find (dst_it [x]); if (it == diff_map.end()) it = 1; else (it-> second) ++;

Fuente

2011-05-22 00:18:13

No hay muchos colores duplicados en la imagen (es un semi-degradado 3d). ¿Cómo podría diff_map.insert (x * y, 5) explicar las colisiones? –

Su espacio hash es de 24bits de tamaño. Para tener 0 colisiones, necesitarías una tabla hash del tamaño de tus datos si tu has es perfecta, más grande en un 25-50% si no es así. Supongo que ha creado su tabla hash mucho, mucho más pequeña que esto, por lo tanto, el contenedor está reasignando sus datos y causando las colisiones.

Fuente

2011-05-22 00:19:38

También escribo una función hash personalizado (que era una función hash perfecta: 256^2 x R + 256 x G + B - por lo que las colisiones debe ser mínima, independientemente de los cubos y diseño de tabla hash (a un precio razonable extender).

Esta función hash no es bueno. una buena función hash (cuando no se conoce el número de cubos) debería generar enormemente diferentes valores hash para las entradas casi idénticos. En su caso, una Una forma muy simple de lograr esto es usar tres tablas de 256 valores aleatorios de 32 bits: int32_t rand[3][256] - luego hash ala rand[0][R]^rand[1][G]^rand[2][B]. Esto dispersa sus valores al azar en los cubos sin tendencia a agruparse para s valores imilares: la propiedad de la función hashing ideal para # cubos desconocidos.

También puede dejar que las funciones hash-biblioteca proporcionada tienen una grieta en ella, posiblemente no pueden mejorar en las propiedades de la tabla al azar para la generación de hash, pero pueden deberse más rápido a menos búsquedas de memoria o más lento debido a la operaciones matemáticas más o menos complejas: punto de referencia si te importa.

Fuente

2011-05-22 04:32:39

Aunque es posible que no tenga valores iguales, los valores pueden ser lo suficientemente cercanos. Me ha costado trabajo intentar encontrar buenas funciones hash para series de tiempo o números que no estén dispersos. Cuando el mapa desordenado hace un '%' (módulo) en el valor hash con el número de segmentos, la mayoría de sus valores pueden terminar en pocos segmentos (si los valores hash no están bien dispersos) y eso conduce a búsquedas O (n) .

Cuando los valores hash no están lo suficientemente dispersos, solo usaría std :: map (árbol RB) donde obtengo O (log n).

Fuente

2011-05-22 05:23:48 hackworks

Funcionalidad de inserción/función hash unordered_map miserable

Respuesta

Cuestiones relacionadas