分桶法, 平方分割与分布式计算(由POJ2104想到的)

大任务的分工

起初电脑都是单cpu单核的, 因为工艺上升空间大, 所以摩尔定律速度增长没啥问题. 后来工艺达到瓶颈, cpu一下子变成好几个核心来组成. 分布式计算应运而生, 分布式算法也越来越重要. 很多本来看起来无法分工完成的任务, 经过巧妙的转化, 都能够分工完成, 充分利用了现代处理器多核心多线程并发运算的特性.

POJ2104

POJ这道题目是给出一个数列 a1, a2, a3, …, an 和m个查询. 对于每一个查询(i, j, k)找出从ai到aj的升序排列数列中的第k个数.

简单的说就是在很大的一个数列当中找第k大, 而且找很多回. 朴素的方法就是对区间进行排序, 然后找出第k个就是了. 但是这样的弊端有两个:

因为n太大, 所以排序很慢. 在实际工程中, 机器都是可以进行分布式计算的, 一个快速排序简单粗暴, 无法用上分布式计算的特性;
由于进行多次查询, 每次查询的区间不一样, 导致每一次排序的结果都不能被下一次所利用, 不能达到记忆化多次利用的效果.

所以如果能找出先分割成为若干个小问题, 每个小问题都能进行预处理保存好计算结果, 然后查询的时候只要将涉及到的小问题的已经计算好的数据用某种方式进行合并就可以快好准的处理这个问题.

为了能够分割问题, 必须把单纯的对区间排序转换为统计区间内小于某个数的元素的个数. 通过二分x, 找出这么一个x, 在区间内小于等于x的个数不到k个, 小于等于x的个数不少于k个, 那么这个x就是题目所求. 而统计区间内小于x的个数这个任务是可以分而治之的.

平方分割——分任务的优化

设一个大任务包含N个元素, 把他分成K份小任务, 每份小任务的规模就是N/K. 一般情况下, 为了不出现K=1或者K=N这样的极端导致算法退化, 取K=sqrt(N), 这样 N/K = K = sqrt(N).

但是在实际问题中, 所求的区间并不一定刚好是某几个桶的覆盖, 而是左边涉及半个桶, 中间是若干个桶, 右边又多出来半个桶的数据. 这时候就需要两个步骤:

对所有整个桶包含在区间内的桶进行整体处理;
对所有被拆分的桶的每一个元素进行处理.

这就导致了这个分任务的方法可以进一步优化. 在POJ2104中, 第一步的复杂度是每个桶O(log b), 第二步的复杂度是每个元素O(1). 因此我们更应该调整K, 使得桶的数量比桶内的元素要少一些. 这道题真是神, 桶内元素设为1000刚好AC, 1200就RE, 100就TLE.

/**
* I love coding
* @Author: Jecvay
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define DBG 0
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "


inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////

#define inf 0x4F4F4F4F
const int maxn = 1e5 + 10;
const int B = 1290;   // every bucket contain B elements.

int n, m;
int A[maxn];
int num[maxn];
vector<int> bucket[maxn/B];

/////////////////

void init() {
  for (int i = 0; i < n; i++) {
    bucket[i/B].push_back(A[i]);
    num[i] = A[i];
  }
  sort(num, num + n);
  for (int i = 0; i < n / B; i++)
    sort(bucket[i].begin(), bucket[i].end());
}


int main() {
  n = gint();
  m = gint();
  for (int i = 0; i < n; i++) {
    A[i] = gint();
  }
  init();
  int I, J, k;
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &I, &J, &k);
    // 二分法求[l, r)区间中第k个数
    int l = I-1, r = J;
    int lb = -1, ub = n - 1;
    while (ub - lb > 1) {
      int md = (lb + ub) / 2;
      int x = num[md];
      int tl = l, tr = r, c = 0;

      // 计算区间两端不完全占据一个桶而多出来的部分
      while (tl < tr && tl % B) {
        if (A[tl] <= x)
          c++;
        tl++;
      }
      while (tl < tr && tr % B) {
        tr--;
        if (A[tr] <= x)
          c++;
      }

      // 对每一个完整的桶进行计算, 可分布式计算
      while (tl < tr) {
        int b = tl / B;
        c += upper_bound(bucket[b].begin(), bucket[b].end(), x)
              - bucket[b].begin();
        tl += B;
      }

      if (c >= k) ub = md;
      else lb = md;
    }
    printf("%dn", num[ub]);
  }
  return 0;
}



/*

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

*/

本文链接

大任务的分工

POJ2104

平方分割——分任务的优化

回复