C++ STL Mapa kontra prędkość wektorowa

Question

W tłumaczeniu mojego eksperymentalnego języka programowania mam tablicę symboli. Każdy symbol składa się z nazwy i wartości (wartością może być np .: ciąg znaków, int, funkcja itd.).

Początkowo reprezentowałem tabelę z wektorem i sprawdzałem przez sprawdzanie symboli, czy podana jest nazwa danego symbolu.

Potem chociaż pomocą mapy, w moim przypadku map<string,symbol>, byłoby lepsze niż iteracja wektora cały czas ale:

To trochę trudno wyjaśnić tę część, ale spróbuję.

Jeśli zmienna zostanie pobrana po raz pierwszy w programie w moim języku, należy oczywiście znaleźć jej pozycję w tabeli symboli (używając teraz wektora). Gdybym wykonywał iteracje w wektorze za każdym razem, gdy linia zostanie wykonana (myślę o pętli), byłaby to strasznie powolna (jak obecnie jest, prawie tak wolna jak partia Microsoftu).

Więc mogę korzystać z mapy, aby pobrać zmienną: SymbolTable[ myVar.Name ]

Ale pomyśl z następujących czynności: Jeśli zmienna, nadal stosując wektor, znajduje się po raz pierwszy, można przechowywać jego dokładną pozycję całkowitą w wektorze z tym. Oznacza to: Następnym razem, gdy jest to potrzebne, mój interpreter wie, że został "zbuforowany" i nie przeszukuje tabeli symboli, ale robi coś w rodzaju SymbolTable.at(myVar.CachedPosition).

Teraz moja (raczej trudne?) Pytanie:

• powinienem używać wektor do tablicy symboli wraz z buforowanie położenie zmiennej w wektorze?

• Czy powinienem raczej używać mapy? Czemu? Jak szybki jest operator []?

• Czy powinienem użyć czegoś zupełnie innego?

Answer 1

Skutecznie masz wiele alternatyw.

Biblioteki istnieć:

• Loki::AssocVector: interfejs mapie realizowanego przez vector par, szybciej niż mapy małych lub mrożonych zestawów powodu cache miejscowości.
• : zapewnia zarówno List with fast lookup, jak i przykład implementacji MRU List (najczęściej używany), który buforuje ostatnio dostępne elementy.

Krytycy

• Mapa spojrzeć w górę i odzyskiwanie wziąć O(log N), ale elementy mogą być rozproszone po całej pamięci, a tym samym nie gra dobrze ze strategii buforowania.
• Wektor jest bardziej przyjazny dla pamięci podręcznej, jednak jeśli go nie posortujesz, uzyskasz O(N) wydajność na find, czy jest to dopuszczalne?
• Dlaczego nie używać numeru unordered_map? Zapewniają one wyszukiwanie i pobieranie (chociaż stała może być wysoka) i są z pewnością dostosowane do tego zadania. Jeśli spojrzysz na artykuł w Wikipedii pod adresem Hash Tables, zobaczysz, że dostępnych jest wiele strategii i na pewno możesz wybrać taki, który będzie pasował do twojego konkretnego wzorca użytkowania.

Answer 2

Normalnie należy użyć tabeli symboli, aby wyszukać zmienną o nazwie podanej w źródle. W tym przypadku masz tylko nazwę do pracy, więc nie ma gdzie przechowywać zapisaną w pamięci pozycję zmiennej w tabeli symboli. Powiedziałbym, że dobry wybór to map. Operator [] zajmuje czas proporcjonalny do logu liczby elementów na mapie - jeśli okaże się, że jest wolny, możesz użyć mapy mieszania, takiej jak std::tr1::unordered_map.

Answer 3

std :: operator mapy [] zajmuje czas O (log (n)). Oznacza to, że jest dość wydajny, ale nadal powinieneś unikać powtarzania w kółko. Zamiast przechowywania indeksu, być może możesz zapisać odniesienie do wartości lub iterator do kontenera? Dzięki temu unika się konieczności wykonywania wyszukiwania.

Answer 4

Mapa jest dobrą rzeczą do użycia w tabeli symboli. ale operator[] dla map nie jest. Ogólnie, jeśli nie piszesz jakiegoś trywialnego kodu, powinieneś użyć funkcji członka mapy zamiast operator[]. Semantyka operator[] jest nieco skomplikowana i prawie na pewno nie robimy tego, co chcemy, jeśli poszukiwany symbol nie znajduje się na mapie.

Jeśli chodzi o wybór między map i unordered_map, różnica w wydajności jest bardzo mało prawdopodobna, aby była istotna przy wdrażaniu prostego języka interpretacji. Jeśli korzystasz z mapy, masz gwarancję, że będzie ona obsługiwana przez wszystkie obecne implementacje Standard C++.

Answer 5

Mapa jest O (log N), więc nie tak szybkie jak wyszukiwanie pozycyjne w tablicy. Dokładne wyniki będą jednak zależeć od wielu czynników, dlatego najlepszym sposobem jest połączenie z kontenerem w taki sposób, aby umożliwić późniejszą zamianę implementacji. Oznacza to, że napisz funkcję "wyszukiwania", którą można efektywnie zaimplementować za pomocą dowolnego odpowiedniego kontenera, aby umożliwić sobie przełączanie i porównywanie prędkości różnych implementacji.

Answer 6

Kiedy większość tłumaczy interpretuje kod, najpierw kompiluje go jako język pośredni. Te języki pośrednie często odwołują się do zmiennych według indeksu lub wskaźnika, zamiast nazwy.

Na przykład, Python (implementacja C) zmienia zmienne lokalne na referencje według indeksu, ale zmienne globalne i zmienne klasy są przywoływane przez nazwę za pomocą tabeli mieszania.

Proponuję zapoznać się z wprowadzającym tekstem na kompilatorach. Operator

Answer 7

mapie za [] wynosi O (log (n)), patrz Wikipedia: http://en.wikipedia.org/wiki/Map_(C%2B%2B)

myślę jak szukasz często symboli, za pomocą mapy to z pewnością prawo. Może mapa skrótu (std::unordered_map) może poprawić wydajność.

Answer 8

Jeśli zamierzasz używać vector i masz problemy z buforowaniem ostatniego wyniku wyszukiwania symbolu, możesz zrobić to samo (buforuj ostatni wynik wyszukiwania), jeśli tablica symboli została zaimplementowana jako a map (ale w przypadku korzystania z map prawdopodobnie nie byłoby wiele korzyści dla pamięci podręcznej). Dzięki map zyskujesz dodatkową zaletę, że wszelkie niezbukowane symbole wyszukiwania będą bardziej wydajne niż wyszukiwanie w vector (zakładając, że vector nie jest posortowane - i utrzymywanie sortowania wektorowego może być kosztowne, jeśli musisz sortuj więcej niż raz).

Weź Neil's advice; map jest ogólnie dobrą strukturą danych dla tabeli symboli, ale musisz upewnić się, że używasz jej poprawnie (i nie dodając symboli przypadkowo).

Answer 9

a (O (log (n))) lub hashtable ("amortyzowany" O (1)) byłby pierwszym wyborem - użyj mechanizmów niestandardowych, jeśli uznasz, że jest to wąskie gardło. Zasadniczo, używanie skrótu lub tokenizowania danych wejściowych jest pierwszą optymalizacją.

Zanim je sprofilujesz, ważne jest, abyś wyodrębnił wyszukiwanie, abyś mógł z łatwością go wymienić i profilować.

---

std::map może ciut wolniej dla niewielkiej liczby elementów (ale wtedy, to naprawdę nie ma znaczenia).

Answer 10

Mówisz: "Jeśli zmienna, wciąż korzystająca z wektora, zostanie znaleziona za pierwszym razem, mogę zapisać jej dokładną pozycję całkowitą w wektorze.".

Możesz zrobić to samo z mapą: wyszukaj zmienną za pomocą find i zamiast tego wskaż pozycję iterator, wskazując na nią.

Answer 11

Przy wyszukiwaniu wartości za pomocą klucza łańcuchowego typ danych mapy jest odpowiedni, o czym informują inni użytkownicy.

Implementacje map STL są zwykle realizowane za pomocą self-balancing trees, podobnie jak struktura danych red black tree, a ich operacje zajmują czas O (logn).

Moja rada jest, aby owinąć tabeli kodów manipulacji w funkcji
jak table_has(name), table_put(name) i table_get(name).

W ten sposób można łatwo zmienić wewnętrzną reprezentację tablic symboli, jeśli użytkownik odczuje niską wydajność w czasie wykonywania, a ponadto można je później osadzić w funkcjach pamięci podręcznej procedur.

Answer 12

Mapa będzie się skalować znacznie lepiej, co będzie ważną funkcją. Jednak nie zapominaj, że podczas korzystania z mapy możesz (w przeciwieństwie do wektora) wziąć wskaźniki i odniesienia. W tym przypadku można łatwo "buforować" zmienne z mapą równie dokładnie jak wektor. Mapa prawie na pewno jest właściwym wyborem.