Function nekolib::algo::parallel_bisect

source ·

pub fn parallel_bisect<S: StatefulPred>(s: S, q: Vec<S::Input>) -> Vec<usize>

Expand description

並列二分探索を行う。

状態によって返り値の異なる述語を考える。各クエリに対して、初めて偽になる状態の番号を返す。常に真となる場合、状態の個数を返す。

Requirements

状態 $j$ の述語に $x_i$ を与えたときの返り値を $f_j(x_i)$ とする。 $f_j(x_i)$ が偽となるとき、 ${}^\forall j' > j$ について $f_{j'}(x_i)$ も偽となる。

直感的には、状態が進むにつれて真となる条件が厳しくなる述語を指す。

Idea

$i$ 番目のクエリについて、区間 $[\mathrm{ok}_i, \mathrm{bad}_i)$ を管理する。これは、 $f_{\mathrm{ok}_i}(x_i)$ は真、 $f_{\mathrm{bad}_i}(x_i)$ は偽になることを意味する。状態の個数を $m$ として、初期値は $[-1, m)$ とする。

状態を進めていきながら、ある $i$ に対して状態 $j = \lfloor(\mathrm{ok}_i+\mathrm{bad}_i)/2\rfloor$ となったとき、 $f_j(x_i)$ を計算する。これにより、答えの範囲が半分に絞れる。この一連の計算を $\log_2(m)+O(1)$ 回繰り返せばよい。

各クエリについて独立に計算するのではなく、一つの述語を共有して並列に処理することで、計算量を削減できる。

毎ループで状態 $m-1$ まで遷移する必要はなく、 $f_j(x_i)$ を計算したい $i$ が存在する最大の $j$ まで見ればよい。

use nekolib::algo::parallel_bisect;
use nekolib::traits::StatefulPred;

struct Neko(i32);
impl Neko {
    pub fn new() -> Self { Self(0) }
}

/// 状態 `i` において値 `10 * i` を持ち、値 `100` を最終状態とする。
/// この値より大きい値に対して真を返す。
impl StatefulPred for Neko {
    type Input = i32;
    fn count(&self) -> usize { 11 }
    fn next(&mut self) {
        if self.0 < 100 { self.0 += 10; }
    }
    fn pred(&self, &x: &i32) -> bool { x > self.0 }
    fn reset(&mut self) { self.0 = 0; }
}

let qs = vec![0, 1, 32, 60, 89, 99, 100, 101, 500];
assert_eq!(
    parallel_bisect(Neko::new(), qs),
    vec![0, 1, 4, 6, 9, 10, 10, 11, 11]
);

Function nekolib::algo::parallel_bisect

Requirements

Idea

Notes

Complexity

Examples