找到N ^ 2个数字的中位数,其中有N个记忆

我试图了解分布式计算,并遇到了一个寻找一大组数的中位数的问题:

假设我们有一大堆数字(可以说元素的数量是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位二进制整数(浮点数是没关系,因为你可以排序基于标志,然后根据该指数,然后根据尾数),那么你可以在解决问题的O(N^2 B / K)时间,如果你有K处理器和N^2数字。 你基本上做二分搜索:从一个等于该范围中间的支点开始,并使用你的K处理器来计算有多少个数小于等于并大于该支点。 然后你就会知道中位数是否等于枢轴位,或者大于或小于枢轴位。 继续进行二分查找。 每个二进制搜索步骤需要O(N^2 /K)时间来遍历数字列表,从而得到O(N^2 B / K)整体运行时间。

链接地址: http://www.djcxy.com/p/83827.html

上一篇: Find a median of N^2 numbers having memory for N of them

下一篇: Explanation of the Median of Medians algorithm