Pre-asignación de cubos en un C++ std::unordered map
Estoy usando el std::unordered_map de gnu++0x para almacenar una gran cantidad de datos. Quiero pre-asignar espacio para el gran número de elementos, ya que puedo vincular el espacio total utilizado.
Lo que me gustaría poder hacer es llamar:
std::unordered_map m;
m.resize(pow(2,x));
Donde se conoce x.
std::unordered_map no apoya esto. Prefiero usar std::unordered_map si es posible, ya que eventualmente será parte del estándar.
Algunas otras limitaciones:
Necesita acceso O(1) fiable y mutación del mapa. El las funciones hash y de comparación deseadas ya no son estándar y algo costosas. O (log n) mutación (como con std::map) es demasiado caro.
-> El costoso hash y la comparación también hacen que el crecimiento basado en la amortización sea demasiado caro. Cada inserto adicional requiere operaciones O(n) de esas funciones, lo que resulta en un término cuadrático adicional en el tiempo de ejecución del algoritmo, ya que los requisitos de almacenamiento exponencial necesitan crecimientos O(n).
5 answers
m.rehash(pow(2,x));
Si pow(2, x) es el número 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 está planeando insertar. Ambas funciones no hacen más que pre-asignar 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 obtendrá exactamente pow(2, x) cubos. Algunas implementaciones usarán solo un número de cubos que es una potencia de 2. Otro las implementaciones solo usarán un número primo de cubos. Otros usarán solo un subconjunto de primos para el número de cubos. Pero en cualquier caso, la implementación debe aceptar su sugerencia en el número de cubos que desea, y luego redondear internamente hasta su siguiente número aceptable de cubos.
Aquí está la redacción precisa que la última (N4660) utiliza para especificar el argumento a rehash:
a.rehash(n) : Postcondiciones: a.bucket_count() >= a.size() / a.max_load_factor() and a.bucket_count() >= n.
Esto postcondición asegura que bucket()_count() >= n, y que load_factor() permanece menor 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())).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-07-19 13:11:57
No creo que importe 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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-12-09 18:35:02
Sugeriría escribir su propio asignador para el std::unordered_map que asigna la memoria exactamente de la manera que desea.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-05 23:38:40
El constructor toma un parámetro "size_type bucket_count" de acuerdo con http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map
Así que la forma más sencilla de hacer lo que dice tu código de ejemplo es:
std::unordered_map m{ pow(2,x) };
Esto será más eficiente ya que no está definido cuántos cubos se reservarán en la construcción de lo contrario, puede que tenga que asignar y luego desasignar cuando llame a reserve después.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-10-07 18:21:10
Creo que rehashy reserve ambos funcionan solo si sabe de antemano cuánta memoria tomará su valor asignado. Si el valor asignado es complicado o cambia dinámicamente de tamaño (por ejemplo, un vector), necesitará su propia implementación. Por ejemplo, si su tamaño de memoria lo permite, puede reservar el contenedor más grande que pueda existir.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-01-14 21:12:24