PAMライブラリ

PAM（Parallel Augmented Maps）は、シーケンス、順序付きセット、順序付きマップ、拡張マップのインターフェースを実装したオープンソースの並列C++ライブラリです。^{[ 1 ]}このライブラリはGitHubで入手できます。このライブラリは、結合ベースのアルゴリズムを用いたバランスの取れた二分木構造を基盤としています。^[¹^] PAMは、 AVL木、赤黒木、treap、重みバランス木を含む4つのバランススキームをサポートしています。

PAMは並列ライブラリであり、並行処理に対しても安全です。その並列性は、cilk、OpenMP 、または PBBSのスケジューラによってサポートされます。^{[ 2 ]}理論上、PAMのすべてのアルゴリズムは作業効率が高く、多重対数的な深さを持ちます。PAMは、マルチバージョン化を可能にする永続的なツリー構造を基盤として採用しています。また、PAMは効率的なGCもサポートしています。

インタフェース

シーケンスを定義するには、ユーザーはシーケンスのキータイプを指定する必要があります。

PAM は、構築、特定のランクのエントリの検索、最初、最後、次、前、サイズ、空、フィルター、マップ削減、連結などのシーケンスに関する機能をサポートします。

順序付きセットを定義するには、キータイプと、キータイプに基づく完全な順序付けを定義する比較関数を指定する必要があります。

PAM は、シーケンスインターフェイスに加えて、挿入、削除、結合、交差、差異などの順序付きセットの機能もサポートします。

順序付きマップを定義するには、キータイプ、キータイプの比較関数、および値のタイプを指定する必要があります。

PAM は、順序付きセットインターフェイスに加えて、結合値による挿入などの順序付きマップの機能もサポートします。

拡張マップを定義するには、キータイプ、キータイプの比較関数、値のタイプ、拡張値のタイプ、基本関数、結合関数、および結合関数の ID を指定する必要があります。

順序付きマップインターフェースに加えて、PAM は aug_range などの拡張マップの機能もサポートします。

PAM はツリー構造に加えて、拡張マップのプレフィックス構造も実装します。

^ ^a ^b ^c ^dサン、イハン;フェリゾビッチ、ダニエル。ガイ・E・ベロック（2018年3月23日）。「PAM: 並列拡張マップ」。ACM SIGPLAN の通知。53 (1): 290–304 .土井: 10.1145/3200691.3178509。ISSN 0362-1340 。2020 年9 月 5 日に取得。
^問題ベースベンチマークスイートライブラリ
^ Sun, Yihan; Blelloch, Guy E.; Lim, Wan Shen; Pavlo, Andrew (2019年10月1日). 「マルチバージョンインデックスを持つハイブリッドワークロードにおける効率的なスナップショット分離のサポートについて」 . Proceedings of the VLDB Endowment . 13 (2): 211– 225. doi : 10.14778/3364324.3364334 . ISSN 2150-8097 . S2CID 204841857 .
^ Sun, Yihan; Blelloch, Guy E. (2019年1月1日). 「拡張マップを用いた並列範囲、セグメント、および矩形クエリ」 . 2019 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX) . Society for Industrial and Applied Mathematics: 159– 173. arXiv : 1803.08621 . doi : 10.1137/1.9781611975499.13 . ISBN 978-1-61197-549-9。
^ Ben-David, Naama; Blelloch, Guy E.; Sun, Yihan; Wei, Yuanhao (2019年6月17日). 「遅延制限と高精度ガベージコレクションを備えたマルチバージョン同時実行性」.第31回ACMアルゴリズムとアーキテクチャにおける並列性シンポジウム. Association for Computing Machinery. pp. 241– 252. doi : 10.1145/3323165.3323185 . ISBN 9781450361842。