並列二分探索

data_structure/parallel_binary_search.hpp · GitHub で見る

共通ページ

更新を先頭から順に適用したとき、各問い合わせの条件が初めて成立する更新回数を求めます。複数の二分探索をまとめ、同じ時刻までの更新を共有します。

#include "lib/data_structure/parallel_binary_search.hpp"
#include "lib/data_structure/union_find.hpp"
#include <vector>

int main() {
    std::vector<std::pair<int,int>> edges{ {0,1}, {2,3}, {1,2} };
    std::vector<std::pair<int,int>> queries{ {0,0}, {0,1}, {0,3}, {0,4} };
    UnionFind uf;
    auto answer = parallel_binary_search(int(edges.size()), int(queries.size()),
        [&] { uf = UnionFind(5); },
        [&](int id) { auto [u,v] = edges[id]; uf.merge(u,v); },
        [&](int id) { auto [u,v] = queries[id]; return uf.same(u,v); });
    // answer = {0, 1, 3, -1}
}

この例では、辺を追加して初めて連結になる時刻を求めています。初めから成立する問い合わせは 0、最後まで成立しない問い合わせは -1 です。

関数	内容・返り値
parallel_binary_search(update_count,query_count,reset,apply,check)	各問い合わせが初めて成立する更新回数を、問い合わせ ID 順の std::vector<int> で返す

update_count・query_count は非負の int です。更新 ID は [0,update_count)、問い合わせ ID は [0,query_count) です。値や更新内容、問い合わせの引数は呼び出し側で保持します。

• reset()：共通の状態を、更新を 1 回も適用していない初期状態へ戻します。
• apply(update_id)：指定した更新を 1 回適用します。各周回では ID の昇順に 0 から呼ばれます。
• check(query_id)：その時点の状態で条件が成立するかを bool に変換できる値で返します。

更新を k 回適用した状態とは、更新 0 から k-1 までを適用した状態です。返り値の各要素は [0,update_count] の最小の成立回数、または -1 です。

各問い合わせの条件は、更新回数について false から true へ単調に変化する必要があります。常に true・常に false の条件も扱えます。更新そのものは可換である必要はなく、登録した順番で適用します。reset は毎回同じ初期状態を再現してください。check の結果は呼び出し回数や問い合わせを評価する順番に依存させないでください。

例以外には、非負の加算を繰り返して区間和がしきい値に到達する時刻や、辺の追加によって連結成分の大きさがしきい値以上になる時刻などを求められます。

問い合わせがなければ空配列を返し、コールバックは呼びません。更新がない場合は reset() を 1 回呼び、初期状態で各問い合わせを判定します。条件や問い合わせの重複にも対応します。

reset() は関数内から最初に呼ばれるので、呼び出し前に状態を初期化する必要はありません。返却後の状態は初期状態や全更新後の状態とは限りません。コールバックを通じて同じ状態を参照するには、例のように参照キャプチャを使えます。

更新数を \(M\)、問い合わせ数を \(Q\)、初期化・更新 1 回・判定 1 回の時間をそれぞれ \(R,A,C\) とします。\(M\ge2\) の場合、全体は \(O((R+MA+QC)\log M)\) 時間、呼び出し側の状態を除く追加空間は \(O(Q)\) です。時刻ごとの並べ替えは整数キーの基数ソートで行い、1 周回 \(O(Q)\) 時間です。\(M=0,1\) では、初期化 1 回、更新は高々 \(M\) 回、判定は高々 \(2Q\) 回です。

依存ライブラリ

• 64 bit キーの安定基数ソート

検証コード

• test/parallel_binary_search.test.cpp

コード

#ifndef PARALLEL_BINARY_SEARCH_HPP
#define PARALLEL_BINARY_SEARCH_HPP

#include "../components/radix_sort.hpp"
#include <cassert>
#include <cstdint>

template<class Reset, class Apply, class Check>
std::vector<int> parallel_binary_search(int update_count, int query_count, Reset reset, Apply apply, Check check) {
	assert(update_count >= 0 && query_count >= 0);
	std::vector<int> answer(query_count, -1);
	if (!query_count) return answer;
	reset();
	std::vector<int> active;
	active.reserve(query_count);
	for (int id = 0; id < query_count; ++id) {
		if (check(id)) answer[id] = 0;
		else active.push_back(id);
	}
	if (active.empty() || !update_count) return answer;
	for (int i = 0; i < update_count; ++i) apply(i);
	std::size_t kept = 0;
	for (int id : active) if (check(id)) active[kept++] = id;
	active.resize(kept);
	if (active.empty()) return answer;
	std::vector<int> low(query_count), high(query_count, update_count);
	std::vector<std::pair<std::uint32_t, int>> middle;
	middle.reserve(active.size());
	for (;;) {
		middle.clear();
		for (int id : active) if (high[id] - low[id] > 1)
			middle.emplace_back(std::uint32_t(low[id] + (high[id] - low[id]) / 2), id);
		if (middle.empty()) break;
		stable_radix_sort(middle, [](const auto &entry) { return entry.first; });
		reset();
		int time = 0;
		for (auto [target, id] : middle) {
			while (std::uint32_t(time) < target) apply(time++);
			if (check(id)) high[id] = time;
			else low[id] = time;
		}
	}
	for (int id : active) answer[id] = high[id];
	return answer;
}

#endif

Back to top page