Policy Based Data Structures

この記事はCompetitive Programming (2) Advent Calendar 2018およびISer Advent Calendar 2018 1日目の記事です。

CodeForcesTopCoderで海外勢がよくヘッダーに

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

とかをインクルードしていますが、これのことです。日本語の記事が見当たらなかったので書くか〜と思いましたが、書き始めると普通に見つかってしまいました。

hogloid.hatenablog.com

ということでもうちょっと詳しく書くことにします。

Policy Based Data Structures (PBDS)

何ができるか

すごく拡張性のあるデータ構造ですが、標準の機能をそのまま使って得られるオイシイ機能はこのぐらいです(もちろん自作クラスと組合せたりするとこの限りではありません)。実装削減や、いざというときの高速化に役立つかもしれません。

使い方

ここを見ればだいたいのパターンの実装が書かれていますが、GNUのpbdsではないのでコンパイラGNU G++の場合はnamespaceのところを using namespace __gnu_pbds; に書き換えてあげてから実行してあげてください。

以下ではこれらのメインの機能を軽く紹介します。

tree

std::setの上位互換です。

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;

で宣言できます。tb_tree_tagは内部構造に赤黒木を指定しており、たとえばsplay木を使いたいときは代わりにsplay_tree_tagを指定すればいいです。

insert, erase

setと同じでinsert, erase関数です

k番目の値を取得

find_by_order(k)でk番目の要素のイテレータが返ります

kが何番目か

order_of_key(k)でk以上で最小の数が何番目か、つまりk未満の数が何個あるかわかります。実質lower_boundですね

コードです。 Submission #3643481 - AtCoder Regular Contest 033

hash table

std::unordered_mapは実装の制約上非効率な実装になっているようで*、速度が要求される場合にはgp_hash_tableが良いようです。

gp_hash_table<int, int> m;

で宣言できます。templateの第三引数にHash関数を指定できるので通常のunordered_mapと同様なHack対策が可能です。

使い方はunordered_mapとほぼほぼ同じなので省略します。

priority_queue

std::priority_queueは、内部のヒープにpairing heapを使用しているようですが*、pbdsではいくつかのヒープをタグとして指定できます。各操作の計算量は以下のような感じです。

f:id:xuzijian629:20181130063646p:plain
Tagと計算量の関係(#性能比較 にあるリンク先より)

pairing heapが案外優秀なので基本的にstd::priority_queueでいいような気がしますが、要素のmodifyとかをしたいときはpbdsが活きますね。

Thin Heapでダイクストラを書いてみましたが、std::priority_queueのほうが速かったです、、 Aizu Online Judge

trie

通常のtrieと同様、文字列の挿入、prefixによる検索ができます。実装にパトリシア木を指定することで愚直なtrie木よりも高速な検索が可能です。

trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> t;

で宣言できます。以下、コード例(#使い方 の部分に貼った実装の中の一例)です。

trie_prefix_search.cc

これも結構便利だとは思うんですが、trie木を使って即終了!wみたいな問題はまずないと思いますし、Aho-Corasick等に応用するなら自作クラスや自作policyと組み合わせる必要がありそうです。

性能比較

本家のドキュメンテーションに詳細に記載されています。treeは基本的に赤黒木を指定すれば速いです。

参考文献

C++ STL: Policy based data structures - Codeforces

C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures - Codeforces

Chapter 22. Policy-Based Data Structures

pb_ds(1) - 一个oier的战斗 - CSDN博客

pb_ds(2) - 一个oier的战斗 - CSDN博客

網羅的に読みたい人は3つ目、もう少し細かい機能をざっと確認したい方は4つ目、5つ目の記事をおすすめします。

まとめ

tree, gp_hash_tableは使えそう!それ以外は微妙かなあ、、?