我试图学习分布式计算，遇到了一个寻找大量数字中值的问题：
假设我们有一组大的数字(假设元素的数量是N*K)，这些数字无法放入内存(大小为N)。我们如何找到这些数据的中位数？假设对存储器执行的操作是独立的，即我们可以考虑有K个机器，每个机器最多可以处理N个元素。
我认为中位数可以用于此目的。我们可以一次将N个数字加载到内存中。我们找到了该集合在O(logN)时间内的中值并将其保存
然后我们保存所有的K个中值，求出中值的中值。再次是O(logK)，到目前为止复杂性是O(K*logN + logK)。
但这个中位数只是一个近似的中位数。我认为将其用作获得最佳情况性能的枢轴是最佳的，但为此，我们需要在内存中拟合所有N*K个数字。
既然我们有一个很好的近似枢轴，我们如何才能找到集合的实际中值？
为什么不构建一个直方图？即，属于几个类别中每一个类别的案例(值)的数量。类别应该是一个连续的、不重叠的变量间隔。
有了这个直方图，你可以对中值进行第一次估计(即，中值在[a，b]之间)，并知道有多少值落入这个区间(H)。如果H<N、 再次读取数字，忽略该间隔之外的数字，并将该间隔内的数字移动到RAM。找到中位数。
如果H>N，则对间隔进行新的分区并重复该过程。它不应该超过2或3次迭代。
请注意，对于每个分区，您只需要存储a、b、Delta和包含每个子分区中的值数的数组。
编辑。结果比我预想的要复杂一些。在估计中值落入的区间后的每次迭代中，我们还应该考虑在该区间的右侧和左侧留下"多少"直方图。我也改变了停车条件。无论如何，我做了一个C++实现。
#include <iostream>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
//This is N^2... or just the number of values in your array,
//note that we never modify it except at the end (just for sorting
//and testing purposes).
#define N2 1000000
//Number of elements in the histogram. Must be >2
#define HISTN 1000
double findmedian (double *values, double min, double max);
int getindex (int *hist);
void put (int *hist, double min, double max, double val, double delta);
int main ()
{
//Set max and min to the max/min values your array variables can hold,
//calculate it, or maybe we know that they are bounded
double max=1000.0;
double min=0.0;
double delta;
double values[N2];
int hist[HISTN];
int ind;
double median;
int iter=0;
//Initialize with random values
srand ((unsigned) (time(0)));
for (int i=0; i<N2; ++i)
values[i]=((double)rand()/(double)RAND_MAX);
double imin=min;
double imax=max;
clock_t begin=clock();
while (1) {
iter++;
for (int i=0; i<HISTN; ++i)
hist[i]=0;
delta=(imax-imin)/HISTN;
for (int j=0; j<N2; ++j)
put (hist, imin, imax, values[j], delta);
ind=getindex (hist);
imax=imin;
imin=imin+delta*ind;
imax=imax+delta*(ind+1);
if (hist[ind]==1 || imax-imin<=DBL_MIN) {
median=findmedian (values, imin, imax);
break;
}
}
clock_t end=clock();
std::cout << "Median with our algorithm: " << median << " - " << iter << "iterations of the algorithm" << std::endl;
double time=(double)(end-begin)/CLOCKS_PER_SEC;
std::cout << "Time: " << time << std::endl;
//Let's compare our result with the median calculated after sorting the
//array
//Should be values[(int)N2/2] if N2 is odd
begin=clock();
std::sort (values, values+N2);
std::cout << "Median after sorting: " << values[(int)N2/2-1] << std::endl;
end=clock();
time=(double)(end-begin)/CLOCKS_PER_SEC;
std::cout << "Time: " << time << std::endl;
return 0;
}
double findmedian (double *values, double min, double max) {
for (int i=0; i<N2; ++i)
if (values[i]>=min && values[i]<=max)
return values[i];
return 0;
}
int getindex (int *hist)
{
static int pd=0;
int left=0;
int right=0;
int i;
for (int k=0; k<HISTN; k++)
right+=hist[k];
for (i=0; i<HISTN; i++) {
right-=hist[i];
if (i>0)
left+=hist[i-1];
if (hist[i]>0) {
if (pd+right-left<=hist[i]) {
pd=pd+right-left;
break;
}
}
}
return i;
}
void put (int *hist, double min, double max, double val, double delta)
{
int pos;
if (val<min || val>max)
return;
pos=(val-min)/delta;
hist[pos]++;
return;
}
我还包括了中值(排序)的天真计算，以便与算法的结果进行比较。4或5次迭代就足够了。这意味着我们只需要从网络或硬盘上读取4-5次。
一些结果：
N2=10000
HISTN=100
Median with our algorithm: 0.497143 - 4 iterations of the algorithm
Time: 0.000787
Median after sorting: 0.497143
Time: 0.001626
(Algorithm is 2 times faster)
N2=1000000
HISTN=1000
Median with our algorithm: 0.500665 - 4 iterations of the algorithm
Time: 0.028874
Median after sorting: 0.500665
Time: 0.097498
(Algorithm is ~3 times faster)
如果你想将算法并行化，每台机器可以有N个元素并计算直方图。一旦计算完毕，他们就会将其发送到主机，主机会对所有直方图进行求和(很简单，它可能非常小……算法甚至可以处理2个间隔的直方图)。然后，它将向从属机器发送新指令(即新间隔)，以便计算新的直方图。注意，每台机器不需要具有关于其他机器所拥有的N个元素的任何知识。
随机抽取其中的N个样本。在恒定概率依赖于c的情况下，该随机样本的中值在中值的c*N个位置内。如果你这样做两次，那么，在恒定的概率下，你已经将中值的可能位置缩小到线性多。做任何你喜欢的可怕的事情来选择合适等级的元素。
如果你假设你的数字是B位二进制整数(浮点也很好，因为你可以根据符号、指数和尾数进行排序)，那么如果你有K处理器和N^2数字，你就可以在O(N^2 B / K)时间内解决问题。你基本上是做二进制搜索的：从一个等于范围中间的枢轴开始，使用K处理器计算有多少数字小于、等于和大于枢轴。然后，您将知道中间值是等于枢轴，还是大于或小于枢轴。继续二进制搜索。每个二进制搜索步骤都需要O(N^2 /K)时间来遍历数字列表，从而得到O(N^2 B / K)的总运行时间。