Jak wybrać między mapą a unordered_map?

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?

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

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

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

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.

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)