Muszę zmapować klucze pierwotne (int, może long) do wartości struktur w strukturze danych o wysokiej wydajności mapy skrótów.
Mój program będzie zawierał kilkaset takich map, a każda mapa będzie miała zazwyczaj najwyżej kilka tysięcy wpisów. Jednak mapy będą stale „odświeżać” lub „burzyć”; wyobraź sobie, że przetwarzasz miliony addi deletewiadomości na sekundę.
Które biblioteki w C lub C ++ mają strukturę danych, która pasuje do tego przypadku użycia? Albo jak poleciłbyś zbudowanie własnego? Dzięki!
@roe:Operacje dodawania / usuwania są znacznie (100x) częstsze niż operacje pobierania.Odpowiedzi:
Polecam wypróbować Google SparseHash (lub wersję C11 Google SparseHash-c11 ) i sprawdzić, czy odpowiada Twoim potrzebom. Mają implementację wydajną pod względem pamięci, a także zoptymalizowaną pod kątem szybkości. Test porównawczy wykonałem dawno temu, była to najlepsza implementacja do haszowania dostępna pod względem szybkości (jednak z wadami).
źródło
Sprawdź macierze Judy na licencji LGPL . Nigdy się nie wykorzystywałem, ale kilka razy był mi reklamowany.
Możesz także spróbować przetestować kontenery STL (std :: hash_map itp.). W zależności od platformy / implementacji i dostrojenia kodu źródłowego (przydział wstępny tak dużo, jak to tylko możliwe, dynamiczne zarządzanie pamięcią jest kosztowne) mogą być wystarczająco wydajne.
Ponadto, jeśli wydajność ostatecznego rozwiązania przewyższa koszt rozwiązania, możesz spróbować zamówić system z wystarczającą ilością pamięci RAM, aby umieścić wszystko w zwykłych tablicach. Wydajność dostępu według indeksu jest bezkonkurencyjna.
To podpowiada, że możesz najpierw skoncentrować się na ulepszaniu algorytmów. Jeśli dane są tylko zapisywane, a nie czytane, to po co je w ogóle zapisywać?
źródło
Po prostu użyj
boost::unordered_map(lubtr1itp.) Domyślnie. Następnie sprofiluj swój kod i zobacz, czy ten kod jest wąskim gardłem. Dopiero wtedy radziłbym dokładnie przeanalizować swoje wymagania, aby znaleźć szybszy zamiennik.źródło
std::unordered_map90% mojego całego czasu wykonywania, mimo że używam map tylko do stosunkowo niewielkiej części przetwarzania.Jeśli masz program wielowątkowy, możesz znaleźć przydatne tabele skrótów w bibliotece bloków konstrukcyjnych wątków Intel . Na przykład tbb :: concurrent_unordered_map ma taki sam interfejs API jak std :: unordered_map, ale jego główne funkcje są bezpieczne dla wątków.
Spójrz także na szaleńczą bibliotekę Facebooka , ma ona wysokowydajną tabelę współbieżnych skrótów i listę pomijania .
źródło
khash jest bardzo wydajny. Istnieje szczegółowy benchmark autora: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/, a także pokazuje, że khash pokonuje wiele innych bibliotek skrótów.
źródło
ze źródeł Androida (stąd licencja Apache 2)
https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils
spójrz na hashmap.c, wybierz include / cutils / hashmap.h, jeśli nie potrzebujesz bezpieczeństwa wątków, możesz usunąć kod mutex, przykładowa implementacja znajduje się w libcutils / str_parms.c
źródło
Najpierw sprawdź, czy istniejące rozwiązania, takie jak libmemcache, odpowiadają Twoim potrzebom.
Jeśli nie ...
Mapy z haszowaniem wydają się być ostateczną odpowiedzią na Twoje wymagania. Zapewnia wyszukiwanie o (1) na podstawie kluczy. Większość bibliotek STL udostępnia obecnie pewnego rodzaju skróty. Skorzystaj więc z tego, który zapewnia Twoja platforma.
Po wykonaniu tej części musisz przetestować rozwiązanie, aby sprawdzić, czy domyślny algorytm haszowania jest wystarczająco dobry pod względem wydajności dla Twoich potrzeb.
Jeśli tak nie jest, powinieneś zapoznać się z dobrymi algorytmami szybkiego haszowania znalezionymi w sieci
Jeśli to nie wystarczy, możesz samodzielnie rzucić moduł haszujący, który rozwiązuje problem, który widziałeś z przetestowanymi kontenerami STL i jednym z algorytmów haszujących powyżej. Pamiętaj, aby gdzieś opublikować wyniki.
Aha i to ciekawe, że masz wiele map ... być może możesz uprościć, mając swój klucz jako 64-bitową liczbę z wysokimi bitami używanymi do rozróżnienia, do której mapy należy, i dodania wszystkich par klucz-wartość do jednego gigantycznego skrótu. Widziałem hashe, które mają około stu tysięcy symboli, które działają doskonale na podstawowym algorytmie haszowania liczb pierwszych.
Możesz sprawdzić, jak to rozwiązanie działa w porównaniu z setkami map ... myślę, że to mogłoby być lepsze z punktu widzenia profilowania pamięci ... proszę, opublikuj gdzieś wyniki, jeśli wykonasz to ćwiczenie
Uważam, że czymś więcej niż algorytmem haszowania może być ciągłe dodawanie / usuwanie pamięci (czy można tego uniknąć?) I profil użycia pamięci podręcznej procesora, które mogą być bardziej kluczowe dla wydajności aplikacji
powodzenia
źródło
Wypróbuj tabele skrótów z różnych szablonów kontenerów . Ma
closed_hash_mapmniej więcej taką samą prędkość jak Googledense_hash_map, ale jest łatwiejszy w użyciu (brak ograniczeń dotyczących zawartych wartości) i ma również inne zalety.źródło
Proponuję uthash . Po prostu
#include "uthash.h"dołącz, a następnie dodajUT_hash_handledo struktury i wybierz jedno lub więcej pól w swojej strukturze, które będą działać jako klucz. Słowo o wydajności tutaj .źródło
http://incise.org/hash-table-benchmarks.html gcc ma bardzo dobrą implementację. Pamiętaj jednak, że musi uwzględniać bardzo złą standardową decyzję:
http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/
Oznacza to zasadniczo, że norma mówi, że wdrożenie MUSI BYĆ oparte na połączonych listach. Zapobiega otwartemu adresowaniu, które ma lepszą wydajność.
Myślę, że Google rzadko używa otwartego adresowania, chociaż w tych testach porównawczych tylko wersja gęsta przewyższa konkurencję. Jednak rzadka wersja przewyższa całą konkurencję pod względem użycia pamięci. (również nie ma żadnego plateau, czysta linia prosta z liczbą elementów)
źródło