Parallel binary search
(Mylib/Algorithm/parallel_binary_search.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

• CODE THANKS FESTIVAL 2017 H - Union Sets

References

• http://pazzle1230.hatenablog.com/entry/2017/12/26/163616
• https://betrue12.hateblo.jp/entry/2019/08/14/152227
• http://codeforces.com/blog/entry/45578

Verified with

• test/aoj/0575/main.test.cpp

Code

#pragma once
#include <cmath>
#include <vector>

namespace haar_lib {
  template <typename Init, typename Process, typename Checker>
  std::vector<int> parallel_binary_search(int M, int Q, Init init, Process process, Checker checker) {
    std::vector<int> lb(Q, -1), ub(Q, M);

    while (1) {
      bool check = true;
      std::vector<std::vector<int>> mids(M);
      for (int i = 0; i < Q; ++i) {
        if (std::abs(lb[i] - ub[i]) > 1) {
          check   = false;
          int mid = (lb[i] + ub[i]) / 2;
          mids[mid].push_back(i);
        }
      }

      if (check) break;

      init();

      for (int i = 0; i < M; ++i) {
        process(i);
        for (int j : mids[i]) {
          if (checker(j)) {
            ub[j] = i;
          } else {
            lb[j] = i;
          }
        }
      }
    }

    return ub;
  }
}  // namespace haar_lib

#line 2 "Mylib/Algorithm/parallel_binary_search.cpp"
#include <cmath>
#include <vector>

namespace haar_lib {
  template <typename Init, typename Process, typename Checker>
  std::vector<int> parallel_binary_search(int M, int Q, Init init, Process process, Checker checker) {
    std::vector<int> lb(Q, -1), ub(Q, M);

    while (1) {
      bool check = true;
      std::vector<std::vector<int>> mids(M);
      for (int i = 0; i < Q; ++i) {
        if (std::abs(lb[i] - ub[i]) > 1) {
          check   = false;
          int mid = (lb[i] + ub[i]) / 2;
          mids[mid].push_back(i);
        }
      }

      if (check) break;

      init();

      for (int i = 0; i < M; ++i) {
        process(i);
        for (int j : mids[i]) {
          if (checker(j)) {
            ub[j] = i;
          } else {
            lb[j] = i;
          }
        }
      }
    }

    return ub;
  }
}  // namespace haar_lib

Back to top page