Найти медиану из N^2 чисел, имеющих память для N из них
Я пытался узнать о распределенных вычислениях и столкнулся с проблемой нахождения медианы большого набора чисел:
Предположим, что у нас есть большой набор чисел (допустим, количество элементов равно N*K), которые не могут поместиться в памяти (размер N). Как мы находим медиану этих данных? Предположим, что операции, выполняемые над памятью, являются независимыми, т.е. мы можем считать, что существует K машин, каждая из которых может обрабатывать не более N элементов.
Я думал, что медиана медиан может быть использована для этой цели. Мы можем загрузить N номеров одновременно в память. Мы находим медиану этого набора в O(logN)
время и сохранить его.
Затем мы сохраняем все эти K медианы и находим медиану медиан. Снова O(logK)
До сих пор сложность была O(K*logN + logK)
,
Но эта медиана является лишь приблизительной медианой. Я думаю, что будет оптимально использовать его как опорную точку для достижения наилучшей производительности, но для этого нам нужно будет разместить все числа N * K в памяти.
Как мы можем найти фактическую медиану множества теперь, когда у нас есть хороший приблизительный круг?
3 ответа
Почему бы вам не построить гистограмму? Т.е. количество дел (значений), попадающих в каждую из нескольких категорий. Категории должны быть последовательными непересекающимися интервалами переменной.
С помощью этой гистограммы вы можете сделать первую оценку медианы (то есть медиана находится между [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)
общее время работы.