nekolib/algo/
parallel_bisect.rs

1//! 並列二分探索。
2
3use super::super::traits::stateful_predicate;
4
5use stateful_predicate::StatefulPred;
6
7/// 並列二分探索を行う。
8///
9/// 状態によって返り値の異なる述語を考える。
10/// 各クエリに対して、初めて偽になる状態の番号を返す。
11/// 常に真となる場合、状態の個数を返す。
12///
13/// # Requirements
14/// 状態 $j$ の述語に $x\_i$ を与えたときの返り値を $f\_j(x\_i)$ とする。
15/// $f\_j(x\_i)$ が偽となるとき、${}\^\\forall j\' > j$ について $f\_{j\'}(x\_i)$ も偽となる。
16///
17/// 直感的には、状態が進むにつれて真となる条件が厳しくなる述語を指す。
18///
19/// # Idea
20/// $i$ 番目のクエリについて、区間 $[\\mathrm{ok}\_i, \\mathrm{bad}\_i)$ を管理する。
21/// これは、$f\_{\\mathrm{ok}\_i}(x\_i)$ は真、$f\_{\\mathrm{bad}\_i}(x\_i)$
22/// は偽になることを意味する。
23/// 状態の個数を $m$ として、初期値は $[-1, m)$ とする。
24///
25/// 状態を進めていきながら、ある $i$ に対して
26/// 状態 $j = \\lfloor(\\mathrm{ok}\_i+\\mathrm{bad}\_i)/2\\rfloor$ となったとき、
27/// $f\_j(x\_i)$ を計算する。これにより、答えの範囲が半分に絞れる。
28/// この一連の計算を $\\log\_2(m)+O(1)$ 回繰り返せばよい。
29///
30/// 各クエリについて独立に計算するのではなく、
31/// 一つの述語を共有して並列に処理することで、計算量を削減できる。
32///
33/// 毎ループで状態 $m-1$ まで遷移する必要はなく、
34/// $f\_j(x\_i)$ を計算したい $i$ が存在する最大の $j$ まで見ればよい。
35///
36/// # Notes
37/// 永続データ構造が作れるのであれば、単にそれを用いて各クエリについて二分探索を行えばよい。
38/// また、クエリの個数が少なく、述語の計算コストが高くない場合は、
39/// 各々について線形探索を行う方が高速な場合もありうる。
40///
41/// # Complexity
42/// 状態 $0$ から状態 $m-1$ までの遷移を高々 $\\log\_2(m)+O(1)$ 回行う。
43/// また、各クエリに対して述語の呼び出しを $\\log\_2(m)+O(1)$ 回行う。
44///
45/// # Examples
46/// ```
47/// use nekolib::algo::parallel_bisect;
48/// use nekolib::traits::StatefulPred;
49///
50/// struct Neko(i32);
51/// impl Neko {
52///     pub fn new() -> Self { Self(0) }
53/// }
54///
55/// /// 状態 `i` において値 `10 * i` を持ち、値 `100` を最終状態とする。
56/// /// この値より大きい値に対して真を返す。
57/// impl StatefulPred for Neko {
58///     type Input = i32;
59///     fn count(&self) -> usize { 11 }
60///     fn next(&mut self) {
61///         if self.0 < 100 { self.0 += 10; }
62///     }
63///     fn pred(&self, &x: &i32) -> bool { x > self.0 }
64///     fn reset(&mut self) { self.0 = 0; }
65/// }
66///
67/// let qs = vec![0, 1, 32, 60, 89, 99, 100, 101, 500];
68/// assert_eq!(
69///     parallel_bisect(Neko::new(), qs),
70///     vec![0, 1, 4, 6, 9, 10, 10, 11, 11]
71/// );
72/// ```
73pub fn parallel_bisect<S: StatefulPred>(
74    mut s: S,
75    q: Vec<S::Input>,
76) -> Vec<usize> {
77    let sn = s.count();
78    let qn = q.len();
79    let mut ok = vec![0; qn];
80    let mut bad = vec![sn + 1; qn];
81
82    loop {
83        let mut ev = vec![vec![]; sn + 1];
84        let mut max = None;
85        for i in 0..qn {
86            if bad[i] - ok[i] <= 1 {
87                continue;
88            }
89            let mid = ok[i] + (bad[i] - ok[i]) / 2;
90            ev[mid].push(i);
91            max = Some(max.unwrap_or(0).max(mid));
92        }
93        if max.is_none() {
94            break;
95        }
96
97        s.reset();
98        for j in 1..=max.unwrap() {
99            for &i in &ev[j] {
100                if s.pred(&q[i]) {
101                    ok[i] = j;
102                } else {
103                    bad[i] = j;
104                }
105            }
106            s.next();
107        }
108    }
109
110    bad.into_iter().map(|x| x - 1).collect()
111}
nekolib/algo/parallel_bisect.rs

nekolib/algo/
parallel_bisect.rs
