找出N^2个数字的中位数，其中N个数字有记忆

Question

我试图学习分布式计算，并遇到了一个寻找大量数字的中位数的问题：

假设我们有一大组数字（假设元素数为 N*K），它们无法放入内存（大小为 N）。我们如何找到这些数据的中位数？假设在内存上执行的操作是独立的，即我们可以考虑有K台机器，每台机器最多可以处理N个元素。

我认为中位数可以用于这个目的。我们可以一次将N个数装入内存。我们在< code>O(logN)时间内找到该集合的中值，并保存它。

然后我们保存所有这些K个中位数，找出中位数的中位数。同样是O（logK），到目前为止，复杂性一直是O（K*logN logK）。

但是这个中位数只是一个大概的中位数。我认为使用它作为支点来获得最佳性能是最理想的，但为此我们需要将所有的N*K个数字放入内存中。

既然我们有了一个好的近似支点，我们怎么能找到集合的实际中位数呢？

Answer 1

如果您假设您的数字是< code>B位二进制整数(浮点也可以，因为您可以先根据符号排序，然后根据指数排序，再根据尾数排序)，那么如果您有< code>K个处理器和N^2数，您可以在O(N^2时间内解决这个问题。你基本上做二分搜索法:从等于范围中间的枢轴开始，使用你的< code>K处理器来计算有多少个数字小于、等于和大于枢轴。然后你就会知道中位数是等于中枢还是大于或小于中枢。继续二分搜索法。O(N^2 /K)花费二分搜索法的每一步时间来遍历数字列表，从而给O(N^2 B / K)总的运行时间。

Answer 2

取其中的N个随机样本。在依赖于c的恒定概率下，该随机样本的中位数在中位数的c*N位内。如果你这样做两次，那么，在恒定概率下，你已经将中位数的可能位置缩小到线性多。做任何你喜欢的可怕的事情来选择适当排名的元素。

Answer 3

为什么不构建直方图？即属于几个类别中的每一个的案例（值）的数量。类别应为变量的连续、非重叠区间。

使用该直方图，您可以对中值进行初步估计(即中值在[a，b]之间)，并知道有多少个值落在该区间(H)内。如果H

如果H

请注意，对于每个分区，您只需要存储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 个元素有任何了解。