Czy jest jakaś zaleta korzystania z mapy nad unordered_map w przypadku trywialnych kluczy?

Niedawna rozmowa unordered_mapw C ++ uświadomiła mi, że powinienem używać tego unordered_mapw większości przypadków, w których mapwcześniej go użyłem , ze względu na efektywność wyszukiwania ( zamortyzowane O (1) vs. O (log n) ). Najwięcej razy używam mapę, używam albo intczy std::stringjako kluczowy typu; stąd nie mam problemów z definicją funkcji skrótu. Im dłużej o tym myślałem, tym bardziej zdawałem sobie sprawę, że nie mogę znaleźć żadnego powodu, aby użyć std::mapover a std::unordered_mapw przypadku kluczy o prostych typach - spojrzałem na interfejsy i nie znalazłem żadnego znaczące różnice, które wpłynęłyby na mój kod.

Stąd pytanie: czy jest jakiś prawdziwy powód do korzystania std::mapw ciągu std::unordered_mapw przypadku typów prostych, jak inti std::string?

Pytam z ściśle programistycznego punktu widzenia - wiem, że nie jest to w pełni uważane za standardowe i może powodować problemy z portowaniem.

Spodziewam się również, że jedna z poprawnych odpowiedzi może brzmieć „jest bardziej wydajna dla mniejszych zestawów danych” z powodu mniejszego obciążenia (czy to prawda?) - dlatego chciałbym ograniczyć pytanie do przypadków, w których ilość klucze są nietrywialne (> 1 024).

Edycja: duh, zapomniałem oczywistości (dzięki GMan!) - tak, mapy są oczywiście uporządkowane - wiem o tym i szukam innych powodów.

Nie zapominaj, że maputrzymuje swoje elementy uporządkowane. Jeśli nie możesz się poddać, oczywiście nie możesz tego użyć unordered_map.

Należy również pamiętać o tym, że unordered_mapgeneralnie zużywa więcej pamięci. mapma tylko kilka wskaźników domowych i pamięć dla każdego obiektu. Przeciwnie, unordered_mapma dużą tablicę (w niektórych implementacjach mogą być dość duże), a następnie dodatkową pamięć dla każdego obiektu. Jeśli musisz być świadomy pamięci, mappowinien okazać się lepszy, ponieważ brakuje dużej tablicy.

Więc jeśli potrzebujesz czystego wyszukiwania, powiedziałbym, że unordered_mapjest to właściwa droga. Ale zawsze są kompromisy, a jeśli nie możesz sobie na nie pozwolić, nie możesz z nich skorzystać.

Właśnie z własnego doświadczenia zauważyłem ogromną poprawę wydajności (mierzoną, oczywiście), gdy korzystałem z niej unordered_mapzamiast mapw tabeli przeglądów głównej jednostki.

Z drugiej strony stwierdziłem, że było to znacznie wolniejsze przy wielokrotnym wstawianiu i usuwaniu elementów. Doskonale nadaje się do względnie statycznej kolekcji elementów, ale jeśli robisz mnóstwo wstawień i usunięć, mieszanie + segmentowanie wydaje się sumować. (Uwaga, to było po wielu iteracjach).

Jeśli chcesz porównać szybkość swoich std::mapi std::unordered_mapwdrożeń, możesz użyć projektu Google Sparsehash , który ma program Time_Hash_map. Na przykład z gcc 4.4.2 w systemie Linux x86_64

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)

Powtarzam w przybliżeniu ten sam punkt, który przedstawił GMan: w zależności od rodzaju zastosowania std::mapmoże być (i często jest) szybszy niż std::tr1::unordered_map(przy użyciu implementacji zawartej w VS 2008 SP1).

Należy pamiętać o kilku skomplikowanych czynnikach. Na przykład, std::mapporównujesz klucze, co oznacza, że ​​zawsze patrzysz tylko na początek klucza, aby odróżnić prawą i lewą gałąź drzewa. Z mojego doświadczenia wynika, że ​​prawie jedyny raz, kiedy patrzysz na cały klucz, to jeśli używasz czegoś takiego jak int, które możesz porównać w jednej instrukcji. Przy bardziej typowym typie klucza, takim jak std :: string, często porównujesz tylko kilka znaków.

Z kolei przyzwoita funkcja skrótu zawsze patrzy na cały klawisz. IOW, nawet jeśli wyszukiwanie tabeli ma stałą złożoność, sam skrót ma z grubsza liniową złożoność (choć na długości klucza, a nie liczby elementów). Z długimi łańcuchami jako kluczami, std::mapmoże zakończyć wyszukiwanie, zanim unordered_mapnawet rozpocznie wyszukiwanie.

Po drugie, chociaż istnieje kilka metod zmiany rozmiaru tabel skrótów, większość z nich jest dość powolna - do tego stopnia, że ​​o ile wyszukiwania nie są znacznie częstsze niż wstawianie i usuwanie, std :: map często będzie szybsze niż std::unordered_map.

Oczywiście, jak wspomniałem w komentarzu do twojego poprzedniego pytania, możesz również użyć tabeli drzew. Ma to zarówno zalety, jak i wady. Z jednej strony ogranicza najgorszy przypadek do drzewa. Pozwala również na szybkie wstawianie i usuwanie, ponieważ (przynajmniej kiedy to zrobiłem) użyłem stałej wielkości tabeli. Wyeliminowanie zmiany rozmiaru wszystkich tabel pozwala znacznie uprościć tabelę skrótów i zwykle jest szybsza.

Jeszcze jedna uwaga: wymagania dla map mieszających i drzewiastych są różne. Hashowanie oczywiście wymaga funkcji skrótu i ​​porównania równości, gdzie uporządkowane mapy wymagają porównania mniejszego niż. Oczywiście wspomniana hybryda wymaga obu. Oczywiście w zwykłym przypadku używania łańcucha jako klucza nie jest to tak naprawdę problemem, ale niektóre typy kluczy lepiej porządkują niż hashowanie (lub odwrotnie).

Zaintrygowała mnie odpowiedź @Jerry Coffin, która zasugerowała, że ​​zamówiona mapa będzie wykazywać wzrost wydajności na długich ciągach, po pewnych eksperymentach (które można pobrać z pastebin ), stwierdziłem, że dotyczy to tylko kolekcji losowych ciągów, gdy mapa jest inicjowana za pomocą posortowanego słownika (zawierającego słowa ze znaczną ilością nakładających się prefiksów), reguła ta załamuje się, prawdopodobnie ze względu na zwiększoną głębokość drzewa niezbędną do odzyskania wartości. Wyniki pokazano poniżej, pierwsza kolumna liczbowa to czas wstawiania, druga to czas pobierania.

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298

Chciałbym tylko zaznaczyć, że ... istnieje wiele rodzajów unordered_map.

Sprawdź artykuł w Wikipedii na mapie skrótów. W zależności od zastosowanej implementacji cechy dotyczące wyszukiwania, wstawiania i usuwania mogą się znacznie różnić.

I to mnie najbardziej martwi po dodaniu unordered_mapSTL: będą musieli wybrać konkretną implementację, ponieważ wątpię, czy pójdą dalej Policy, więc utkniemy z implementacją do przeciętnego użytku i nic do pozostałe przypadki ...

Na przykład niektóre mapy skrótów mają liniowe powtórzenie skrótu, w którym zamiast powtórzenia całej mapy skrótu na raz część jest powtórzona przy każdym wstawieniu, co pomaga amortyzować koszt.

Kolejny przykład: niektóre mapy skrótów używają prostej listy węzłów dla segmentu, inne używają mapy, inne nie używają węzłów, ale znajdują najbliższe miejsce, a na koniec niektóre wykorzystują listę węzłów, ale zmieniają jej kolejność, tak aby ostatni dostęp do elementu jest z przodu (jak pamięć podręczna).

Więc w tej chwili wolę std::maplub loki::AssocVector( a może dla zamrożonych zestawów danych).

Nie zrozum mnie źle, chciałbym skorzystać z std::unordered_mapi mogę w przyszłości, ale trudno jest „zaufać” przenośności takiego kontenera, gdy pomyślisz o wszystkich sposobach jego wdrożenia i różnych wynikach tego.

Znaczące różnice, które tak naprawdę nie zostały odpowiednio wymienione tutaj:

• maputrzymuje iteratory na wszystkich elementach w stanie stabilnym, w C ++ 17 możesz nawet przenosić elementy z jednego mapna drugi bez unieważniania iteratorów na nich (i jeśli są poprawnie zaimplementowane bez potencjalnej alokacji).
• map czasy dla pojedynczych operacji są zazwyczaj bardziej spójne, ponieważ nigdy nie wymagają dużych alokacji.
• unordered_mapużywanie std::hashzgodnie z implementacją w libstdc ++ jest podatne na DoS, jeśli jest zasilane niezaufanym wejściem (używa MurmurHash2 ze stałym seedem - nie że seedowanie naprawdę by pomogło, patrz https://emboss.github.io/blog/2012/12/14/ breaking-murmur-hash-flooding-dos-reloaded / ).
• Bycie uporządkowanym umożliwia efektywne wyszukiwanie zakresu, np. Iteracja po wszystkich elementach z kluczem ≥ 42.

Tabele skrótów mają wyższe stałe niż popularne implementacje map, które stają się znaczące dla małych kontenerów. Maksymalny rozmiar to 10, 100, a może nawet 1000 lub więcej? Stałe są takie same jak zawsze, ale O (log n) jest bliskie O (k). (Pamiętaj, że złożoność logarytmiczna jest nadal bardzo dobra).

To, co czyni dobrą funkcję skrótu, zależy od cech danych; więc jeśli nie planuję patrzeć na niestandardową funkcję skrótu (ale z pewnością mogę zmienić zdanie później i łatwo, ponieważ pisałem cholernie blisko wszystkiego) i mimo że domyślne ustawienia są wybierane tak, aby działały przyzwoicie dla wielu źródeł danych, znajduję uporządkowaną charakter mapy wystarcza na początku, że nadal domyślnie mapuję, a nie tablicę skrótów w tym przypadku.

W ten sposób nie musisz nawet myśleć o pisaniu funkcji skrótu dla innych (zwykle UDT) i po prostu pisz op <(co i tak chcesz).

Powody podano w innych odpowiedziach; tutaj jest inny.

operacje std :: map (zrównoważone drzewo binarne) są amortyzowane przez O (log n), aw najgorszym przypadku O (log n). operacje std :: unordered_map (tablica skrótów) są amortyzowane przez O (1), aw najgorszym przypadku O (n).

W praktyce wygląda to tak, że tablica skrótów „czkawka” co jakiś czas z operacją O (n), co może, ale nie musi, być tolerowane przez twoją aplikację. Jeśli to nie toleruje, wolisz std :: map niż std :: unordered_map.

Podsumowanie

Przyjęcie zamówienia nie jest ważne:

• Jeśli zamierzasz zbudować duży stół raz i zrobić wiele zapytań, użyj std::unordered_map
• Jeśli zamierzasz zbudować mały stolik (może mieć mniej niż 100 elementów) i wykonać wiele zapytań, użyj std::map. To dlatego, że są na nim czytane O(log n).
• Jeśli zamierzasz często zmieniać tabelę, być może jest std::map to dobra opcja.
• Jeśli masz wątpliwości, po prostu użyj std::unordered_map.

Kontekst historyczny

W większości języków mapa nieuporządkowana (inaczej słowniki oparte na haszowaniu) jest mapą domyślną, jednak w C ++ mapa jest uporządkowana jako mapa domyślna. Jak to się stało? Niektórzy ludzie błędnie zakładają, że komitet C ++ podjął tę decyzję w swojej wyjątkowej mądrości, ale prawda jest niestety brzydsza.

Powszechnie uważa się, że C ++ zakończyło się domyślnie mapą uporządkowaną, ponieważ nie ma zbyt wielu parametrów, jak można je zaimplementować. Z drugiej strony implementacje oparte na haszowaniu mają mnóstwo rzeczy do omówienia. Aby uniknąć blokad w standaryzacji, po prostu dogadali się z zamówioną mapą. Około 2005 r. Wiele języków miało już dobre implementacje oparte na haszowaniu, więc komitetowi łatwiej było zaakceptować nowe std::unordered_map. W idealnym świecie std::mapbyłoby nieuporządkowane i mielibyśmy std::ordered_mapjako osobny typ.

Wydajność

Poniżej dwa wykresy powinny mówić same za siebie ( źródło ):

Niedawno wykonałem test, który umożliwia 50000 scalanie i sortowanie. Oznacza to, że jeśli klucze ciągów są takie same, scal ciąg bajtów. Ostateczne wyniki powinny zostać posortowane. Obejmuje to sprawdzenie każdego wstawienia.

Dla maprealizacji, trwa 200 ms, aby zakończyć pracę. W przypadku unordered_map+ wstawienie mapzajmuje 70 ms unordered_mapi 80 ms map. Implementacja hybrydowa jest więc o 50 ms szybsza.

Powinniśmy pomyśleć dwa razy, zanim skorzystamy z map. Jeśli potrzebujesz tylko danych do posortowania w końcowym wyniku programu, rozwiązanie hybrydowe może być lepsze.

Mały dodatek do wszystkich powyższych:

Lepsze użycie map, gdy potrzebujesz uzyskać elementy według zakresu, ponieważ są one sortowane i możesz po prostu iterować nad nimi od jednej granicy do drugiej.

Od: http://www.cplusplus.com/reference/map/map/

„Wewnętrznie elementy na mapie są zawsze sortowane według klucza według określonego ścisłego kryterium słabego uporządkowania wskazanego przez wewnętrzny obiekt porównawczy (typu Porównaj).

kontenery map są generalnie wolniejsze niż kontenery nieuporządkowane_map, aby uzyskać dostęp do poszczególnych elementów według ich klucza, ale umożliwiają bezpośrednią iterację podzbiorów w oparciu o ich kolejność. "