PAM bibliotek
PAM (Parallel Augmented Maps) är ett parallellt C++-bibliotek med öppen källkod som implementerar gränssnittet för sekvens, beställda uppsättningar , beställda kartor och utökade kartor . Biblioteket är tillgängligt på GitHub. Den använder den underliggande balanserade binära trädstrukturen med hjälp av joinbaserade algoritmer . PAM stöder fyra balanseringsscheman, inklusive AVL-träd , rödsvarta träd , treaps och viktbalanserade träd .
PAM är ett parallellbibliotek och är också säkert för samtidighet. Dess parallellitet kan stödjas av cilk , OpenMP eller schemaläggaren i PBBS. Teoretiskt är alla algoritmer i PAM arbetseffektiva och har polylogaritmiskt djup. PAM använder underliggande beständig trädstruktur så att flerversionshantering är tillåten. PAM stöder också effektiv GC.
Gränssnitt
Sekvenser
För att definiera en sekvens måste användarna ange nyckeltypen för sekvensen.
PAM stöder funktioner på sekvenser inklusive konstruktion, hitta en post med en viss rang, första, sista, nästa, föregående, storlek, tom, filtrera, kartförminska, sammanlänkning, etc.
Beställda set
För att definiera en beställd uppsättning måste användarna ange nyckeltypen och jämförelsefunktionen som definierar en total beställning på nyckeltypen.
Utöver sekvensgränssnittet stöder PAM även funktioner för beställda uppsättningar inklusive infogning, radering, union , intersection , difference , etc.
Beställda kartor
För att definiera en beställd karta måste användarna ange nyckeltypen, jämförelsefunktionen på nyckeltypen och värdetypen.
Utöver det beställda set-gränssnittet stöder PAM även funktioner för beställda kartor, såsom infogning med kombinerande värden.
Förstärkta kartor
För att definiera en utökad karta måste användarna specificera nyckeltypen, jämförelsefunktionen på nyckeltypen, värdetypen, den utökade värdetypen, basfunktionen, kombinerafunktionen och kombinationsfunktionens identitet.
Utöver det beställda kartgränssnittet stöder PAM även funktioner för utökade kartor, såsom aug_range.
Förutom trädstrukturerna implementerar PAM även prefixstrukturen för utökade kartor.
Implementering för exempelapplikationer
Biblioteket tillhandahåller också exempelimplementeringar för ett antal applikationer, inklusive 1D stabbing-fråga (med intervallträd , 2D -intervallfråga (med ett intervallträd och en sveplinjealgoritm ), 2D-segmentfråga (med ett segmentträd och en sveplinjealgoritm ), 2D rektangelfråga (med en trädstruktur och en sveplinjealgoritm ), inverterad indexsökning , etc.
Används i applikationer
Biblioteket har testats i olika applikationer, inklusive riktmärken för databaser, 2D- segmentträd , 2D- intervallträd , inverterat index och multiversion samtidighetskontroll .
externa länkar
- PAM , det parallella utökade kartbiblioteket.