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

371

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.

Kornel Kisielewicz
źródło
22
Lubię zadawać to pytanie w wywiadach: „Kiedy sortowanie szybkie jest lepsze niż sortowanie bąbelkowe?” Odpowiedź na pytanie zapewnia wgląd w praktyczne zastosowanie teorii złożoności, a nie tylko zwykłe czarno-białe stwierdzenia, takie jak O (1) jest lepszy niż O (n) lub O (k) jest równoważne O (logn) itp. ..
42
@Beh, myślę, że miałeś na myśli "kiedy sortowanie bąbelkowe jest lepsze niż szybkie sortowanie": P
Kornel Kisielewicz
2
Czy inteligentny wskaźnik byłby trywialnym kluczem?
thomthom
Oto jeden z przypadków, w którym mapa jest korzystna: stackoverflow.com/questions/51964419/…
anilbey

Odpowiedzi:

398

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).

GManNickG
źródło
3
Jeszcze jedna rzecz w dużej (r) właściwości bloku pamięci unordered_map vs. map (lub vector vs list), domyślna sterta procesu (tutaj mowa o Windows) jest serializowana. Przydzielanie (małych) bloków w dużych ilościach w aplikacji wielowątkowej jest bardzo drogie.
ROAR
4
RA: Możesz w pewien sposób kontrolować to za pomocą własnego typu alokatora w połączeniu z dowolnym kontenerem, jeśli uważasz, że ma to znaczenie dla konkretnego programu.
9
Jeśli znasz rozmiar unordered_mapi zastrzegasz to na początku - czy nadal płacisz karę za wiele wstawień? Załóżmy, że wstawiasz tylko raz, kiedy budujesz tabelę odnośników - a później tylko z niej czytasz.
thomthom,
3
@ thomthom O ile mi wiadomo, nie powinno być kary za wydajność. Powodem, dla którego wydajność wymaga trafienia, jest fakt, że jeśli tablica będzie zbyt duża, dokona powtórnego przetworzenia wszystkich elementów. Jeśli zadzwonisz do rezerwy, potencjalnie zmienisz istniejące elementy, ale jeśli zadzwonisz na początku, nie powinno być kary, przynajmniej zgodnie z cplusplus.com/reference/unordered_map/unordered_map/reserve
Richard Fung
6
Jestem całkiem pewien, że pod względem pamięci jest odwrotnie. Zakładając domyślny współczynnik obciążenia 1,0 dla nieuporządkowanego kontenera: masz jeden wskaźnik na element dla segmentu i jeden wskaźnik na element dla elementu następnego w segmencie, dlatego otrzymujesz dwa wskaźniki plus dane dla każdego elementu. Z drugiej strony, dla zamówionego kontenera typowa implementacja drzewa RB będzie miała: trzy wskaźniki (lewy / prawy / macierzysty) plus bit koloru, który z powodu wyrównania zabiera czwarte słowo. To cztery wskaźniki plus dane na każdy element.
Yakov Galka
126

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)
Blair Zajac
źródło
2
Wygląda na to, że w przypadku większości operacji mapa nieuporządkowana bije mapę. Wydarzenie po wstawieniu ...
Michael IV
7
sparsehash już nie istnieje. zostało usunięte lub usunięte.
User9102d82,
1
@ User9102d82 Zredagowałem pytanie, aby odwoływać się do linku do waybackmachine .
andreee
Tylko po to, aby inni zauważyli także inne liczby poza czasem: testy te zostały wykonane przy użyciu 4-bajtowych obiektów / struktur danych, zwanych też int. Jeśli przechowujesz coś, co wymaga większego haszowania lub jest większe (co powoduje cięższe operacje kopiowania), standardowa mapa może szybko mieć przewagę!
AlexGeorg
82

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).

Jerry Coffin
źródło
2
Zmiana rozmiaru skrótu może być wytłumiona przez dynamic hashingtechniki, które polegają na okresie przejściowym, w którym za każdym razem, gdy wstawiasz element, również odmieniasz kinne elementy. Oczywiście oznacza to, że podczas przejścia musisz przeszukać 2 różne tabele ...
Matthieu M.
2
„Przy długich ciągach znaków jako kluczach, std :: map może zakończyć wyszukiwanie, zanim jeszcze nieuporządkowana_mapa rozpocznie wyszukiwanie.” - jeśli klucz nie jest obecny w kolekcji. Jeśli jest obecny, to oczywiście należy porównać całą długość, aby potwierdzić dopasowanie. Ale również unordered_mapmusi potwierdzić dopasowanie mieszające z pełnym porównaniem, więc wszystko zależy od tego, które części procesu wyszukiwania kontrastujesz.
Steve Jessop
2
zwykle możesz zastąpić funkcję skrótu w oparciu o znajomość danych. na przykład jeśli twoje długie łańcuchy różnią się bardziej w ostatnich 20 bajtach niż w pierwszych 100, po prostu
haszuj
56

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
Gearoid Murphy
źródło
2
Dzięki za test. Aby upewnić się, że nie mierzymy hałasu, zmieniłem go, aby wykonać każdą operację wiele razy (i wstawiłem licznik zamiast 1 do mapy). Przesunąłem go nad inną liczbą klawiszy (od 2 do 1000) i do ~ 100 klawiszy na mapie, std::mapzwykle przewyższa wyniki std::unordered_map, szczególnie w przypadku kluczy całkowitych, ale ~ 100 klawiszy wydaje się, że traci przewagę i std::unordered_mapzaczyna wygrywać. Wstawienie już zamówionej sekwencji do a std::mapjest bardzo złe, otrzymasz najgorszy scenariusz (O (N)).
Andreas Magnusson
30

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.

Matthieu M.
źródło
17
+1: ważny punkt - życie było łatwiejsze, gdy korzystałem z własnej implementacji - przynajmniej wiedziałem, gdzie jest do bani:>
Kornel Kisielewicz
25

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.
użytkownik1531083
źródło
14

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).


źródło
@Roger, czy znasz przybliżoną liczbę elementów, na których mapa nieuporządkowanych najlepszych mapuje? W każdym razie zapewne napiszę test ... (+1)
Kornel Kisielewicz
1
@Kornel: Nie zajmuje wiele; moje testy obejmowały około 10 000 elementów. Jeśli chcemy naprawdę dokładnego wykresu, możesz spojrzeć na implementację mapjednego z nich unordered_map, z pewną platformą i pewnym rozmiarem pamięci podręcznej, i przeprowadzić złożoną analizę. : P
GManNickG
Zależy od szczegółów implementacji, parametrów dostrajania w czasie kompilacji (łatwe do obsługi, jeśli piszesz własną implementację), a nawet od konkretnej maszyny używanej do testów. Podobnie jak w przypadku innych pojemników, komitet określa jedynie ogólne wymagania.
13

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.

Don Hatch
źródło
12

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 ):

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

Shital Shah
źródło
Ciekawe dane; ile platform uwzględniłeś w swoich testach?
Toby Speight
1
dlaczego powinienem używać std :: map do małych tabel, kiedy wykonuję wiele zapytań, ponieważ std :: unordered_map zawsze działa lepiej niż std :: map zgodnie z 2 obrazkami, które tu umieściłeś?
ricky
Wykres pokazuje wydajność dla 0,13 M lub więcej elementów. Jeśli masz małe (może być <100) elementy, wówczas O (log n) może stać się mniejsze niż nieuporządkowana mapa.
Shital Shah
10

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.

Wendong
źródło
0

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.

Denis Sablukov
źródło
-1

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ść. "

Kunal Bansal
źródło