Jak wybrać między mapą a unordered_map?

84

Załóżmy, że chciałbym zmapować dane z ciągiem znaków jako kluczem. Jaki pojemnik powinienem wybrać, mapczy unordered_map? unordered_mapzajmuje więcej pamięci, więc załóżmy, że pamięć nie jest problemem, a problemem jest szybkość.

unordered_mappowinien generalnie dawać średnią złożoność O (1) z najgorszym przypadkiem O (n). W jakich przypadkach doszłoby do O (n)? Kiedy można mapuzyskać większą oszczędność czasu niż unordered_map? Czy to się dzieje, gdy n jest małe?

Zakładając, że użyłbym STL unordered_mapz domyślnym haser Vs. mapa. ciąg jest kluczem.

Jeśli mam zamiar iterować elementy, zamiast uzyskiwać dostęp do pojedynczego elementu za każdym razem, czy wolę map?

StackHeapCollision
źródło
3
Czy chcesz posortować elementy w mapowaniu?
Jakiś programista,
Która implementacja unordered_mapzużywa więcej pamięci?
Peter Wood
Na mapie mieszania zawsze występuje narzut pamięci, chociaż zazwyczaj jest on pomijalny.
ypnos
To drobna uwaga, ale jak wspominasz o iteracji, warto zauważyć, że jeśli iterujesz podczas wstawiania elementów, powinieneś preferować mapę zamiast unordered_map.
John McFarlane,

Odpowiedzi:

67

W praktyce, jeśli pamięć nie jest problemem, unordered_map jest zawsze szybsza, jeśli chcesz uzyskać dostęp do pojedynczego elementu.

Najgorszy przypadek jest teoretyczny i powiązany z pojedynczym hashem uwzględniającym wszystkie elementy. Nie ma to praktycznego znaczenia. unordered_mapDostaje wolniej jak najszybciej mieć przynajmniej log n pierwiastków należących do tej samej hash. Nie ma to również praktycznego znaczenia. W niektórych specjalnych scenariuszach można użyć określonego algorytmu mieszania, który zapewnia bardziej jednorodną dystrybucję. W przypadku zwykłych ciągów, które nie mają określonego wzorca, ogólne funkcje skrótu unordered_mapsą równie dobre.

Jeśli chcesz przemierzać mapę (używając iteratorów) w posortowany sposób, nie możesz użyć unordered_map. Wręcz przeciwnie, mapnie tylko na to pozwala, ale także może dostarczyć następny element mapy w oparciu o przybliżenie klucza (patrz lower_boundi upper_boundmetody).

ypnos
źródło
6
Ta odpowiedź jest w najlepszym razie myląca. Nie jest prawdą, że „unordered_map jest zawsze szybsza przy dostępie do pojedynczego elementu” - jedyne, co przychodzi mi do głowy, to prawda, że ​​jest zawsze szybciej amortyzowana i asymptotyczna . „Amortyzacja” jest ważnym zastrzeżeniem w praktyce: zakładając, że jest zaimplementowana jako pewnego rodzaju tablica mieszająca, jeśli dobrze pamiętam swoje tablice skrótów, gdy powiększasz ją przez wstawianie elementów, będzie ona „czkawka” z operacją Ω (n) co jakiś czas. To może być coś, co może tolerować określona aplikacja.
Don Hatch
211
                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required| 

źródło
6
Komentarz dotyczący powszechnej implementacji: Czerwono-czarne drzewo jest rodzajem zrównoważonego drzewa (a dokładniej rodzajem samobalansującego binarnego drzewa wyszukiwania).
HelloGoodbye
2
log(n)
rebalansowanie
A co z iteracją po wszystkich elementach?
Shashwat,
7

W jakich przypadkach doszłoby do O (n)?

jeśli masz tak złą funkcję skrótu, która generuje tę samą wartość skrótu dla wszystkich mieszania danych wejściowych (tj. tworzy kolizje) ...

Jaki kontener powinienem wybrać, mapować lub unordered_map?

Zawsze chodzi o wymagania i rodzaj / ilość danych, które posiadasz.

Kiedy mapa jest bardziej wydajna czasowo niż unordered_map?

To tylko różne struktury. Lepiej jest zrobić chiose, aby użyć jednego z nich w zależności od typowych przypadków użycia (biorąc pod uwagę rodzaj danych i ich ilość)

Czy działa silniej, gdy n jest małe?

W przypadku małej ilości danych wszystko zależy od konkretnej implementacji STL ... Więc czasami nawet zwykły wektor / tablica może być szybszy niż kontenery asocjacyjne ...

zaufi
źródło
7

Jaki kontener powinienem wybrać, mapować lub unordered_map? unordered_map zajmuje więcej pamięci, więc załóżmy, że pamięć nie jest problemem, a problemem jest szybkość.

Profil, a następnie zdecyduj. unordered_mapjest generalnie szybszy, ale różni się w zależności od przypadku.

W jakich przypadkach doszłoby do O (n)?

Gdy haszowanie nie jest dobre i kilka elementów jest przypisywanych do tych samych pojemników.

Kiedy mapa jest bardziej wydajna czasowo niż unordered_map? Czy to się dzieje, gdy n jest małe?

Prawdopodobnie nie, ale profiluj to, jeśli naprawdę ci zależy. Posiadanie kontenera o małym rozmiarze jako wąskiego gardła twojego programu wydaje się niezwykle mało prawdopodobne. W każdym razie proste vectorwyszukiwanie liniowe może być szybsze w takich przypadkach.


Najważniejsze przy podejmowaniu decyzji są wymagania porządkowania i brak unieważnienia iteratora. Jeśli potrzebujesz, to prawie musisz użyć map. W przeciwnym razie unordered_map.

Pubby
źródło
0

std :: map Wewnętrzne przechowywanie elementów w zrównoważonym BST. Dlatego elementy będą przechowywane w posortowanej kolejności kluczy.

std :: unordered_map przechowuje elementy przy użyciu tablicy skrótów. Dlatego elementy nie będą przechowywane w żadnej sortowanej kolejności. Będą przechowywane w dowolnej kolejności.

Zużycie pamięci :

Użycie pamięci jest większe w unordered_map w porównaniu z mapą, ponieważ unordered_map wymaga również miejsca do przechowywania tablicy skrótów.

Złożoność czasowa elementu wyszukiwania:

Złożoność czasowa wyszukiwania elementów w std :: map wynosi O (log n). Nawet w najgorszym przypadku będzie to O (log n), ponieważ elementy są przechowywane wewnętrznie jako drzewo Balanced Binary Search (BST).

Natomiast w std :: unordered_map najlepsza złożoność czasowa wyszukiwania wynosi O (1). Gdzie tak, jeśli funkcja kodu skrótu nie jest dobra, wówczas złożoność najgorszego przypadku może wynosić O (n)

Shahid Hussain
źródło