biblioteka PAM
PAM (Parallel Augmented Maps) to równoległa biblioteka C++ o otwartym kodzie źródłowym, implementująca interfejs dla sekwencji, uporządkowanych zestawów , uporządkowanych map i rozszerzonych map . Biblioteka jest dostępna na GitHubie. Wykorzystuje podstawową zrównoważoną strukturę drzewa binarnego przy użyciu algorytmów opartych na łączeniu . PAM obsługuje cztery schematy równoważenia, w tym drzewa AVL , drzewa czerwono-czarne , treaps i drzewa zbalansowane wagowo .
PAM jest biblioteką równoległą i jest również bezpieczna dla współbieżności. Jego równoległość może być wspierana przez cilk , OpenMP lub harmonogram w PBBS. Teoretycznie wszystkie algorytmy w PAM są wydajne i mają głębię polilogarytmiczną. PAM wykorzystuje podstawową trwałą strukturę drzewa, tak że dozwolone jest wiele wersji. PAM obsługuje również wydajne GC.
Interfejs
Sekwencje
Aby zdefiniować sekwencję, użytkownicy muszą określić typ klucza sekwencji.
PAM obsługuje funkcje w sekwencjach, w tym konstruowanie, znajdowanie wpisu o określonej randze, pierwszy, ostatni, następny, poprzedni, rozmiar, puste, filtrowanie, zmniejszanie mapy, łączenie itp.
Zamówione zestawy
Aby zdefiniować uporządkowany zestaw, użytkownicy muszą określić typ klucza i funkcję porównania definiującą całkowite uporządkowanie według typu klucza.
Oprócz interfejsu sekwencji PAM obsługuje również funkcje dla uporządkowanych zestawów, w tym wstawianie, usuwanie, łączenie , przecinanie , różnica itp.
Zamówione mapy
Aby zdefiniować uporządkowaną mapę, użytkownicy muszą określić typ klucza, funkcję porównania dla typu klucza i typ wartości.
Oprócz interfejsu zestawu uporządkowanego, PAM obsługuje również funkcje map uporządkowanych, takie jak wstawianie z łączeniem wartości.
Rozszerzone mapy
Aby zdefiniować rozszerzoną mapę , użytkownicy muszą określić typ klucza, funkcję porównania dla typu klucza, typ wartości, typ wartości rozszerzonej, funkcję bazową, funkcję łączenia i tożsamość funkcji łączenia.
Oprócz uporządkowanego interfejsu mapy, PAM obsługuje również funkcje rozszerzonych map, takie jak aug_range.
Oprócz struktur drzewiastych, PAM implementuje również strukturę prefiksów dla rozszerzonych map.
Implementacja dla przykładowych aplikacji
Biblioteka zawiera również przykładowe implementacje dla wielu aplikacji, w tym kwerendy przebijające 1D (przy użyciu drzew interwałowych , kwerendy zakresowej 2D (przy użyciu drzewa rozpiętości i algorytmu linii wymiatającej ), kwerendy segmentowej 2D (przy użyciu drzewa segmentowego i algorytmu linii wymiatającej ), kwerendy 2D zapytanie prostokątne (przy użyciu struktury drzewiastej i algorytmu zmiatania ), przeszukiwanie odwróconego indeksu itp.
Stosowany w aplikacjach
Biblioteka została przetestowana w różnych aplikacjach, w tym w testach porównawczych baz danych, drzewie segmentowym 2D, drzewie interwałowym 2D , odwróconym indeksie i kontroli współbieżności wielu wersji .
Linki zewnętrzne
- PAM , równoległa rozszerzona biblioteka map.