Niedawna rozmowa unordered_map
w C ++ uświadomiła mi, że powinienem używać tego unordered_map
w większości przypadków, w których map
wcześ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 int
czy std::string
jako 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::map
over a std::unordered_map
w 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::map
w ciągu std::unordered_map
w przypadku typów prostych, jak int
i 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.
źródło
Odpowiedzi:
Nie zapominaj, że
map
utrzymuje 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_map
generalnie zużywa więcej pamięci.map
ma tylko kilka wskaźników domowych i pamięć dla każdego obiektu. Przeciwnie,unordered_map
ma 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,map
powinien okazać się lepszy, ponieważ brakuje dużej tablicy.Więc jeśli potrzebujesz czystego wyszukiwania, powiedziałbym, że
unordered_map
jest 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_map
zamiastmap
w 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).
źródło
unordered_map
i 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.Jeśli chcesz porównać szybkość swoich
std::map
istd::unordered_map
wdroż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źródło
Powtarzam w przybliżeniu ten sam punkt, który przedstawił GMan: w zależności od rodzaju zastosowania
std::map
moż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::map
poró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::map
może zakończyć wyszukiwanie, zanimunordered_map
nawet 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).
źródło
dynamic hashing
techniki, które polegają na okresie przejściowym, w którym za każdym razem, gdy wstawiasz element, również odmieniaszk
inne elementy. Oczywiście oznacza to, że podczas przejścia musisz przeszukać 2 różne tabele ...unordered_map
musi potwierdzić dopasowanie mieszające z pełnym porównaniem, więc wszystko zależy od tego, które części procesu wyszukiwania kontrastujesz.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.
źródło
std::map
zwykle przewyższa wynikistd::unordered_map
, szczególnie w przypadku kluczy całkowitych, ale ~ 100 klawiszy wydaje się, że traci przewagę istd::unordered_map
zaczyna wygrywać. Wstawienie już zamówionej sekwencji do astd::map
jest bardzo złe, otrzymasz najgorszy scenariusz (O (N)).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_map
STL: będą musieli wybrać konkretną implementację, ponieważ wątpię, czy pójdą dalejPolicy
, 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::map
lubloki::AssocVector
( a może dla zamrożonych zestawów danych).Nie zrozum mnie źle, chciałbym skorzystać z
std::unordered_map
i 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.źródło
Znaczące różnice, które tak naprawdę nie zostały odpowiednio wymienione tutaj:
map
utrzymuje iteratory na wszystkich elementach w stanie stabilnym, w C ++ 17 możesz nawet przenosić elementy z jednegomap
na 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_map
używaniestd::hash
zgodnie 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 / ).źródło
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
map
jednego z nichunordered_map
, z pewną platformą i pewnym rozmiarem pamięci podręcznej, i przeprowadzić złożoną analizę. : PPowody 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.
źródło
Podsumowanie
Przyjęcie zamówienia nie jest ważne:
std::unordered_map
std::map
. To dlatego, że są na nim czytaneO(log n)
.std::map
to dobra opcja.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 świeciestd::map
byłoby nieuporządkowane i mielibyśmystd::ordered_map
jako osobny typ.Wydajność
Poniżej dwa wykresy powinny mówić same za siebie ( źródło ):
ź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
map
realizacji, trwa 200 ms, aby zakończyć pracę. W przypadkuunordered_map
+ wstawieniemap
zajmuje 70 msunordered_map
i 80 msmap
. 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.źródło
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.źródło
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ść. "
źródło