Pytanie wektor lub mapa, której z nich użyć?


Słyszałem, jak wiele osób mówi, że jeśli liczba elementów oczekiwanych w pojemniku jest stosunkowo niewielka, lepiej jest użyć std::vector zamiast std::map mimo że używam kontenera tylko do wyszukiwania, a nie do iteracji.

Jaki jest prawdziwy powód tego?

Oczywiście wydajność wyszukiwania mapy nie może być gorsza niż w przypadku wektora (chociaż może to być w nanosekundach / mikrosekundach), więc czy ma to coś wspólnego z wykorzystaniem pamięci?

Czy wektor radzi sobie lepiej / gorzej niż mapa w fragmentacji wirtualnej przestrzeni adresowej?

Używam biblioteki STL, która jest dostarczana wraz z Visual Studio (np. Implementacja microsoft), czy robi to jakąkolwiek różnicę od innych implementacji?


50
2018-01-18 07:06


pochodzenie




Odpowiedzi:


Zakładam, że porównujesz map<A, B> z vector<pair<A, B> >.

Po pierwsze, znalezienie elementu w bardzo małym wektorze może z łatwością być szybsze niż to samo na mapie, ponieważ cała pamięć w wektorze jest zawsze ciągła (i tym samym ładniej gra się z pamięciami podręcznymi komputerów i takimi rzeczami), a liczba porównań potrzebnych do znalezienia czegoś w wektorze może być mniej więcej takie samo, jak w przypadku mapy. Znalezienie elementu na mapie wymaga mniejszej liczby operacji w limicie bardzo dużych kontenerów.

Punkt, w którym mapy stają się szybsze od wektorów, zależy od implementacji, od procesora, danych na mapie i subtelnych rzeczy, takich jak pamięć w pamięci podręcznej procesora. Zazwyczaj punkt, w którym mapa staje się szybsza, wynosi około 5-30 elementów.

Alternatywą jest użycie kontenera hash. Często są nazywane hash_map lub unordered_map. Wymienione klasy hash_map nie są częścią oficjalnego standardu (i istnieje kilka wariantów tam); std::tr1::unordered_map jest. Mapa hash jest często szybsza niż normalna mapa dla odnośników, niezależnie od tego, ile elementów jest w niej zawartych, ale to, czy faktycznie jest ona szybsza, zależy od tego, czym jest klucz, jak jest ono zaszyfrowane, z którymi wartościami mamy do czynienia i jak klucz jest porównywany w std :: map. Nie zachowuje rzeczy w określonej kolejności, takiej jak std :: map, ale powiedziałeś, że nie dbasz o to. Polecam mapy skrótów, szczególnie jeśli klucze są liczbami całkowitymi lub wskaźnikami, ponieważ te skróty bardzo szybko.


52
2018-01-18 07:45



O dziwo stwierdziłem, że Java's HashMap jest znacznie szybsza niż mapa C ++. Ostatni akapit twojego postu może wyjaśniać dlaczego. - wmac
@wmac: Racja: porównanie Javy jest bardziej dokładne HashMapdo C ++ hash_map lub unordered_mapi Java SortedMapdo C ++ map. - Mooing Duck
Kiedy testowałem, znalazłem punkt, w którym std :: map out przemieści std :: vector na około 8000, ale tak niskie, jak 1000 na niektórych urządzeniach, kod, którego użyłem, jest dostępny w: github.com/BlackToppStudios/DAGFrameScheduler/blob/... - Sqeaky


Mapy są zwykle zaimplementowane jako drzewa wyszukiwania binarnego, a chodzenie po drzewie binarnym zawsze wiąże się z niewielkim narzutem (porównywanie, przechodzenie odnośników itd.) Wektory są w zasadzie po prostu tablicami. Dla bardzo małych ilości danych, może 8 lub 12 elementów, czasami jest to szybsze po prostu do przeszukiwania liniowego w tablicy niż do przechodzenia w binarne drzewo wyszukiwania.

Możesz sam wykonać kilka ustawień czasowych, aby sprawdzić, gdzie znajduje się punkt progu rentowności - przeprowadź wyszukiwanie w czterech elementach, a następnie w ośmiu, a następnie w szesnastym, i tak dalej, aby znaleźć odpowiednie miejsce dla konkretnej implementacji STL.

Mapy mają zazwyczaj małą liczbę przydziałów na całym stosie, podczas gdy wektory są ciągłe, więc częstość wektorów w pamięci podręcznej może być nieco lepsza w przypadkach, w których dokonuje się iteracji wszystkich elementów od przodu do tyłu.


26
2018-01-18 07:28



Nie musisz nawet przeprowadzać wyszukiwania liniowego. std :: lower_bound daje wyszukiwarkę binarną na dowolnym posortowanym pojemniku. Mapa jest przydatna, gdy istnieje wiele kluczowych wstawień, zmieniających strukturę drzewa wyszukiwania. Jeśli jest to dość statyczna kolekcja, posortowany wektor i lower_bound z łatwością dopasują mapę do wydajności wykraczającej poza zaledwie kilka elementów. Oczywiście nadal warto to porównać w praktyce! - Zoomulator


"Domyślnie używaj wektora, gdy potrzebujesz pojemnika" - Bjarne Stroustrup.

W przeciwnym razie uważam, że ten mały schemat ma bardzo dobrą pomoc:

http://homepages.e3.net.nz/~djm/cppcontainers.html


22
2018-01-18 11:39



Według Herb Sutter (gotw.ca/gotw/054.htm), biorąc pod uwagę wybór między deque a wektorem, zazwyczaj lepiej jest wybrać deque. - graham.reeds
Deque jest dobre, ponieważ jest prawie tak szybkie, jak wektor, ale ponieważ bloki deque są przydzielane niezależnie, nie trzeba przenosić wszystkiego, aby rosnąć. - Zan Lynx


Jeśli robisz wszystkie swoje wstawki jednocześnie, wykonując wiele odnośników, możesz użyć wektora i posortować go podczas wstawiania; następnie użyj parametru lower_bound, aby wykonać szybkie wyszukiwanie. Może być szybszy niż użycie mapy, nawet w przypadku dużej liczby przedmiotów.


4
2018-01-18 07:46





Myślę, że powinieneś używać kontenera, który pasuje do danych przede wszystkim. std :: vector jest używany w sytuacjach, w których używałbyś tablicy w C lub C ++ sprzed STL: chcesz, aby ciągły blok pamięci zapisywał wartości z szybkim, stałym szukaniem czasu. std :: map powinno być używane do mapowania kluczy do wartości. Podstawowym nałożeniem jest tu wektor kontra mapa z kluczem size_t jako kluczem. W takim przypadku istnieją dwie kwestie: czy indeksy są ciągłe? Jeśli nie, prawdopodobnie zmarnujesz pamięć za pomocą wektora. Po drugie, jaki czas szukacie? Wektor ma stałe wyszukiwanie czasu, podczas gdy std :: map jest zwykle implementowany jako drzewo RB, które ma czas wyszukiwania O (log n), a nawet mapa hash (taka jak TR1 unordered_map) zwykle ma gorszą złożoność, ponieważ indeks (lub jego skrót) zostanie zmapowany do zasobnika, który może zawierać wiele wartości.

Jeśli celowałeś w wektor z parami: możesz użyć elementów wektora i użyć find, by znaleźć elementy. Ale jest to wyszukiwanie binarne i praktycznie będzie tak szybkie jak std :: map.

W każdym razie spróbuj modelować dane w oczywisty sposób. Przedwczesna optymalizacja często niewiele pomaga.


3
2018-01-18 11:31





Innym sposobem, aby na to spojrzeć, jest to, że jeśli mówimy o małych pojemnikach, to ani jedno, ani drugie nie zajmie dużo czasu. Jeśli nie przeszukasz tego kontenera w bardzo ciasnej pętli, różnica czasu prawdopodobnie będzie znikoma.

W takim przypadku chciałbym sprawdzić, który kontener bardziej pasuje do tego, co chcesz zrobić. Jeśli szukasz określonej wartości, wbudowana metoda find () na mapie będzie dużo łatwiejsza (i mniej skomplikowana w użyciu) niż tworzenie pętli for i iterowanie po wektorze.

Twój czas jest wart pewnie więcej niż kilka nano-sekund tu i tam.


2
2018-01-18 14:12



Tak, zgadzam się, że zaoszczędzony czas procesora nie jest wart wysiłku. Ale co z konsumpcją pamięci? - Naveen
Ogólnie zgadzam się, ale zauważ, że algorytm std :: find () działa całkiem szczęśliwie zarówno z mapami, jak i wektorami. - j_random_hacker
Jeśli mówimy o niewielkiej ilości wpisów, to zużycie pamięci będzie ogólnie niskie ... co to jest kilka bajtów? O czym tu mówimy ... dwadzieścia? Mapa ma wbudowane find ... trochę łatwiejsze niż std :: find (). - teeks99


Zasadniczo mapy są używane do wyszukiwania.

Ale czasami std::vector może być użyty zamiast std::map nawet do wyszukiwania.

Jeśli w parach klucz-wartość będzie mniej elementów, możesz użyć wyszukiwania wielokrotnego za pomocą klawisza nawet w std::vector<std::pair<x,y>>.

Wynika to z faktu, że mieszanie wymaga czasu, szczególnie w przypadku łańcuchów mieszających i innych operacji na mapie, takich jak przechowywanie danych w stercie.

Widziałbyś tylko lepszą różnicę w std :: map, jeśli masz więcej elementów, w których musisz szukać, a także, gdy chcesz zrobić częste wyszukiwanie na liście elementów, które posiadasz.


-1
2018-03-13 03:53



std :: map nie używa skrótu do wyszukiwania. domyślnie używa std :: less jako komparatora - rmawatson