Precategoría de depósitos en C++ unordered_map

Estoy usando el mapa desordenado de gnu ++ 0x para almacenar una gran cantidad de datos. Quiero preasignar espacio para la gran cantidad de elementos, ya que puedo enlazar el espacio total utilizado.Precategoría de depósitos en C++ unordered_map

Lo que me gustaría ser capaz de hacer es llamar:

std::unordered_map m; 
m.resize(pow(2,x));

donde se sabe que x.

unordered_map no es compatible con esto. Prefiero usar unordered_map si es posible, ya que eventualmente formará parte del estándar.

Algunas otras limitaciones:

Necesita O fiable (1) el acceso y la mutación del mapa. Las funciones de comparación y hash deseadas ya no son estándar y son algo costosas. La mutación O (log n) (como con std :: map) es demasiado costosa.

-> El hash caro y la comparación también hacen que el crecimiento basado en la amortización sea demasiado caro. Cada inserción adicional requiere O (n) operaciones de esas funciones, lo que da como resultado un término cuadrático adicional en el tiempo de ejecución del algoritmo, ya que los requisitos de almacenamiento exponencial necesitan O (n) crecimientos.

Fuente

2011-05-05 JAD

m.rehash(pow(2,x));

if pow(2, x) es la cantidad de cubos que desea preasignar. También puede:

m.reserve(pow(2,x));

pero ahora pow(2, x) es el número de elementos que usted está planeando sobre la inserción. Ambas funciones no hacen más que preasignar cubos. No insertan ningún elemento. Y ambos están destinados a ser utilizados exactamente para su caso de uso.

Nota: No se garantiza que obtenga exactamente pow(2, x) cubos. Algunas implementaciones usarán solo una cantidad de cubos que es una potencia de 2. Otras implementaciones usarán solo un número primo de cubos. Aún otros usarán solo un subconjunto de primos para la cantidad de cubos. Pero en cualquier caso, la implementación debe aceptar su sugerencia en la cantidad de cubos que desee, y luego redondear internamente hasta su siguiente número aceptable de cubetas.

Aquí es el texto exacto que la última (N4660) utiliza para especificar el argumento para rehash:

a.rehash(n): Condiciones posteriores:a.bucket_count() >= a.size()/a.max_load_factor() and a.bucket_count() >= n.

Esta condición posteriora asegura que bucket()_count() >= n, y que load_factor() permanece igual o igual a max_load_factor().

Posteriormente reserve(n) se define en términos de rehash(n):

a.reserve(n): Igual que a.rehash(ceil(n/a.max_load_factor())).

Fuente

2011-05-05 23:56:25

Está usando la sugerencia, como si estuviera en: iterator std :: set :: insert (sugerencia del iterador, const value_type & value); http://en.cppreference.com/w/cpp/container/set/insert, parece una redacción incorrecta. –

Sugeriría escribir su propio asignador para el std::unordered_map que asigna la memoria exactamente en la forma que desee.

Fuente

2011-05-05 23:38:40 orlp

No creo que sea importante que un mapa desordenado tenga memoria preasignada. Se espera que el STL sea O (n) tiempo de inserción amortizado. Ahórrese la molestia de escribir su propio asignador hasta que sepa que este es el cuello de botella de su código, en mi opinión.

Fuente

2011-05-05 23:49:25

El STL garantiza O (n) tiempo de inserción amortizado, pero una forma común de implementar esto es aumentar el número de cubos por un factor constante, y luego volver a generar cada elemento existente. Esto sucede O (log n) veces si está almacenando n elementos en el mapa. Cuando n es 2^grande, esto agrega un factor extra de gran tamaño al número de inserciones realizadas. Estoy tratando de quitarme este factor. – JAD

"esto agrega un factor extra de gran tamaño" No, agrega un factor adicional de 2. ¿Entiende cómo funcionan las operaciones amortizadas? La única razón real por la que esta respuesta es incorrecta es porque no "garantiza" O (n) tiempo de inserción amortizado, solo proporciona el tiempo de inserción amortizado O (n) esperado, con una probabilidad exponencialmente alta sobre los elementos insertados aleatoriamente. Si conoce los tamaños exactos a los que se ajustarán las cubetas y la función de hash que se usará, aún es posible engañar a la tabla hash y forzar las colisiones N para cada inserción. – codetaku

-2

creo refrito y reserva ambos funcionan sólo si se sabe de antemano la cantidad de memoria asignada valor tomarán. Si el valor mapeado es complicado o cambia dinámicamente de tamaño (por ejemplo, un vector), necesitará su propia implementación. Por ejemplo, si el tamaño de su memoria lo permite, puede reservar el contenedor más grande que pueda existir.

Fuente

2016-01-14 21:12:24 hrrl

Algunos puntos que haces no tienen sentido, o no te hiciste entender. Por ejemplo, "si el valor mapeado cambia dinámicamente es el tamaño (por ejemplo, vector)". No importa cuántos elementos tenga en un vector (o cualquier contenedor o clase para el caso), 'sizeof (std :: vector )' permanece igual (para la misma 'T' obviamente). El 'mapa' reservará la cantidad exacta de espacio para un' std :: vector' de 1 elemento o un 'std :: vector' de 1 mil elementos. "es posible que reserve el contenedor más grande que pueda existir" es otro punto que no veo como un buen consejo en el contexto de esta pregunta. – bolov

El constructor toma un parámetro "bucket_count size_type", según http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

por lo que la forma más sencilla de hacer lo que dice el código de ejemplo es:

std::unordered_map m{ pow(2,x) };

Esto será más eficiente, ya que es indefinido cuántos los cubos se reservarán para la construcción; de lo contrario, es posible que tenga que asignarlos y luego desasignarlos cuando llame a reservar después.

Fuente

2016-10-07 18:21:10 Ben

Precategoría de depósitos en C++ unordered_map

Respuesta

Cuestiones relacionadas