Wstępne przydzielanie segmentów w C++ unordered_map

Question

Używam unordered_map z gnu ++ 0x do przechowywania ogromnej ilości danych. Chcę wstępnie przydzielić przestrzeń dla dużej liczby elementów, ponieważ mogę związać całkowitą wykorzystaną przestrzeń.

Co chciałbym być w stanie zrobić to zadzwonić:

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

gdzie x jest znany.

unordered_map nie obsługuje tego. Wolałbym raczej użyć unordered_map, jeśli to możliwe, ponieważ ostatecznie stanie się częścią standardu.

Niektóre inne ograniczenia:

potrzebują niezawodnych O (1) dostęp i mutacji mapy. Pożądane funkcje mieszające i porównawcze są już niestandardowe i nieco droższe. Mutacja O (log n) (jak w przypadku std :: map) jest zbyt droga.

-> Kosztowne hash i porównanie również powodują, że wzrost oparty na amortyzacji jest zbyt drogi. Każda dodatkowa wstawka wymaga operacji O (n) z tych funkcji, co powoduje dodatkowy kwadratowy termin w czasie działania algorytmu, ponieważ wymagania dotyczące wykładniczej pamięci masowej wymagają przyrostów O (n).

Answer 1

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

jeśli pow(2, x) jest liczbą wiaderek, które mają zostać wstępnie przydzielone. Można także:

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

ale teraz pow(2, x) jest liczba elementów planujesz na wstawienie. Obie funkcje nic nie robią, ale przygotowują wiadra. Nie wstawiają żadnych elementów. Oba mają być używane dokładnie dla twojego przypadku użycia.

Uwaga: Nie masz gwarancji, że otrzymasz dokładnie wiadra . W niektórych wdrożeniach wykorzystywana będzie tylko pewna ilość wiader, która jest potęgą 2. Inne wdrożenia będą wykorzystywać tylko pierwszą liczbę wiader. Jeszcze inni będą używać tylko podzbioru liczb pierwszych dla liczby wiader. Ale w każdym przypadku, implementacja powinna zaakceptować twoją podpowiedź na liczbę żądanych kubełków, a następnie wewnętrznie zaokrąglić do następnej dopuszczalnej liczby wiader.

Oto precyzyjne sformułowanie, że najnowsza (N4660) używa do określenia argumentu rehash:

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

Ten warunek zapewnia, że ​​bucket()_count() >= n i że load_factor() pozostaje mniejszy niż lub równy max_load_factor().

Następnie reserve(n) jest definiowane rehash(n):

a.reserve(n): jak a.rehash(ceil(n/a.max_load_factor())).

Answer 2

Sugerowałbym napisanie własnego przydziału dla std::unordered_map, który przydziela pamięć dokładnie tak, jak chcesz.

Answer 3

Nie sądzę, że ważne jest, aby nieuporządkowana mapa miała wstępnie przydzieloną pamięć. Oczekuje się, że STL będzie O (n) zamortyzowanym czasem wprowadzania. Oszczędź sobie kłopotu z pisaniem własnego przydziału, dopóki nie zorientujesz się, że jest to wąskie gardło twojego kodu, według mnie.

Answer 4

myślę mikstura i rezerwa zarówno pracować tylko wtedy, gdy z góry wiadomo, ile pamięci mapowane wartość zajmie. Jeśli odwzorowana wartość jest skomplikowana lub dynamicznie zmienia się jej rozmiar (np. Wektor), potrzebna jest jej własna implementacja. Na przykład, jeśli twój rozmiar pamięci na to pozwala, możesz zarezerwować największy kontener, jaki może się zdarzyć.

Answer 5

Konstruktor przyjmuje parametr „size_type bucket_count” według http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

więc najprostszym sposobem na to, co się przykładowy kod mówi się:

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

To będzie bardziej skuteczny, ponieważ jest to nieokreślone ile wiadra będą zarezerwowane na budowę, w przeciwnym razie może być konieczne alokowanie, a następnie zwolnienie, gdy wezwiesz rezerwę później.