10 億の数字と 100 のコンピューターがある場合、これらの数字の中央値を特定する最善の方法は何ですか?
私が持っている1つの解決策は次のとおりです。
最初にm1 < m2 < m3 ...マージSet1しSet2、結果のセットで (マージされた) の中央値よりも小さいすべての数値を破棄できますSet12。したがって、いつでも同じサイズのセットがあります。ちなみに、これは並行して行うことはできません。何か案は？
ああ、私の脳がギアを入れたところです。今、賢明な提案があります。これがインタビューだったら手遅れかもしれませんが、気にしないでください。
マシン 1 は「コントロール マシン」と呼ばれるものであり、議論のために、すべてのデータから開始し、それを他の 99 台のマシンに均等に送信するか、またはデータをマシン間で均等に分散し始めるかのいずれかです。そのデータの 1/99 を他のそれぞれに送信します。パーティションは等しい必要はなく、ちょうど近いです。
他の各マシンはそのデータをソートし、最初に低い値を見つけることを優先する方法でソートします。したがって、たとえばクイックソートでは、常にパーティションの下部が最初にソートされます[*]。できるだけ早くデータを昇順で制御マシンに書き戻します (ソートを続行するために非同期 IO を使用し、おそらく Nagle をオンにして、少し実験します)。
制御マシンは、データが到着すると 99 通りのマージを実行しますが、マージされたデータを破棄し、見た値の数を数えるだけです。中央値は、2 億分の 1 および 20 億分の 1 と 1 分の 1 の値の平均として計算されます。
これは、「群れの中で最も遅い」という問題に悩まされています。アルゴリズムは、中央値未満のすべての値が選別機によって送信されるまで完了できません。そのような値の 1 つが、そのデータの区画内で非常に高くなる可能性は十分にあります。したがって、データの最初の分割が完了すると、推定実行時間は、データの 1/99 を並べ替えて制御コンピューターに送り返す時間と、制御がデータの 1/2 を読み取る時間の合計になります。 . 「組み合わせ」は、最大値とそれらの時間の合計の間のどこかにあり、おそらく最大値に近いです。
私の本能は、ネットワークを介してデータを送信する方が、ソートするよりも高速である (中央値を選択するだけでなく) ためには、非常に高速なネットワークである必要があるということです。たとえば、データを含む RAM に均等にアクセスできる 100 個のコアがある場合など、ネットワークが瞬間的であると推定できる場合は、より良い見通しになる可能性があります。
ネットワーク I/O が制限される可能性が高いため、少なくとも制御マシンに返されるデータについては、いくつかのトリックを実行できる可能性があります。たとえば、「1,2,3,.. 100」を送信する代わりに、おそらくソーティング マシンは「101 未満の 100 の値」を意味するメッセージを送信できます。次に、制御マシンは修正されたマージを実行できます。この場合、すべての範囲の上限値の中で最小のものを見つけ、すべてのソート マシンにそれが何であったかを伝えます。多くの値がその値より下で「カウント」され、(b) その時点からソートされたデータの送信が再開されます。
より一般的に言えば、コントロール マシンが 99 台の選別マシンで遊べる巧妙なチャレンジ/レスポンス型の推測ゲームがおそらくあるでしょう。
ただし、これにはマシン間の往復が含まれますが、私の単純な最初のバージョンでは回避されます。私はそれらの相対的なパフォーマンスを盲目的に推定する方法を本当に知りません.トレードオフは複雑であるため、これが実際の問題であると仮定すると、私が自分で考えるよりもはるかに優れたソリューションがそこにあると思います.
[*] 利用可能なスタックの許可 - O(N) の余分なスペースがない場合、最初に実行する部分の選択は制限されます。しかし、十分な余分なスペースがある場合は、選択することができます。十分なスペースがない場合は、最初のいくつかのパーティションの小さな部分を最初に実行することにより、少なくともコーナーをカットするために必要なものを使用できます.
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"
ここで逆張りになるのは嫌ですが、並べ替えが必要だとは思いません。また、10 億/100 の数値を並べ替えるアルゴリズムは遅くなると思います。1 台のコンピューター上のアルゴリズムを考えてみましょう。
1) 10 億から無作為に 1000 個の値を選択し、それらを使用して数値の分布、特に範囲を把握します。
2) 値を並べ替える代わりに、計算した分布に基づいて値をバケットに割り当てます。バケットの数は、コンピューターが効率的に処理できるように選択されますが、それ以外の場合は、できるだけ大きくする必要があります。バケットの範囲は、各バケットにほぼ同数の値が入るようにする必要があります (これはアルゴリズムにとって重要ではありませんが、効率に役立ちます。100,000 バケットが適切な場合があります)。各バケットの値の数に注意してください。これは O(n) プロセスです。
3) 中央値がどのバケット範囲にあるかを調べます。これは、各バケットの合計数を調べるだけで実行できます。
4) そのバケットの値を調べて、実際の中央値を見つけます。おそらく10,000個の数字しかソートしていないので、必要に応じてここでソートを使用できます。そのバケット内の値の数が多い場合は、並べ替えるのに十分な数になるまで、このアルゴリズムを再度使用できます。
このアプローチは、コンピューター間で値を分割することによって簡単に並列化します。各コンピューターは、各バケットの合計を、ステップ 3 を実行する「制御」コンピューターに報告します。ステップ 4 では、各コンピューターは、関連するバケット内の (並べ替えられた) 値を制御コンピューターに送信します (これらのアルゴリズムを両方同時に実行することもできます。しかし、おそらくそれだけの価値はありません）。
バケットの数が十分に大きい場合、ステップ 3 と 4 の両方が自明であるため、プロセス全体は O(n) です。
10億は、現代のコンピューターにとって実際には非常に退屈な作業です. ここでは 4 GB 相当の 4 バイト整数について話しています... 4 GB ... 一部のスマートフォンの RAM です。
public class Median {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int[] numbers = new int[1_000_000_000];
System.out.println("created array after " + (System.currentTimeMillis() - start) + " ms");
Random rand = new Random();
for (int i = 0; i < numbers.length; i++) {
numbers[i] = rand.nextInt();
}
System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms");
Arrays.sort(numbers);
System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms");
if (numbers.length % 2 == 1) {
System.out.println("median = " + numbers[numbers.length / 2 - 1]);
} else {
int m1 = numbers[numbers.length / 2 - 1];
int m2 = numbers[numbers.length / 2];
double m = ((long) m1 + m2) / 2.0;
System.out.println("median = " + new DecimalFormat("#.#").format(m));
}
}
私のマシンでの出力：
created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196
したがって、これは単一のコアを使用して 2 分以内 (1:43 のうち 0:10 は乱数を生成するためのもの) で私のマシンで完了し、完全な並べ替えも実行しています。本当に空想的なものは何もありません。
これは確かに、より大きな数のセットにとって興味深い作業です。ここで強調したいのは、10億はピーナッツです. したがって、驚くほど単純なタスクに複雑なソリューションを投入する前に、よく考えてください ;)
これは人々を驚かせるかもしれませんが、数値が 32 ビット (またはそれ以下) に収まるほど小さい整数である場合は、バケット ソートを実行してください。任意の数の 32 ビット int に対して 16GB の RAM しか必要とせず、O(n) で実行されます。これは、合理的な n、たとえば 10 億の分散システムよりも優れているはずです。
ソートされたリストを取得したら、中央値を選択するのは簡単です。実際、ソートされたリストを作成する必要はありませんが、バケットを見るだけで作成できます。
簡単な実装を以下に示します。16 ビット整数でのみ機能しますが、32 ビットへの拡張は簡単です。
#include <stdio.h>
#include <string.h>
int main()
{
unsigned short buckets[65536];
int input, n=0, count=0, i;
// calculate buckets
memset(buckets, 0, sizeof(buckets));
while (scanf("%d", &input) != EOF)
{
buckets[input & 0xffff]++;
n++;
}
// find median
while (count <= n/2)
{
count += buckets[i++];
}
printf("median: %d\n", i-1);
return 0;
}
10 億 (10 9 ) の数字を含むテキスト ファイルを使用し、timeそのように実行する
time ./median < billion
私のマシンでの実行時間は 1m49.293s です。実行時間のほとんどはおそらくディスク IO です。
この数値セットの中央値
2、3、5、7、11、13、67、71、73、79、83、89、97
は67です。
この数値セットの中央値
2、3、5、7、11、13、67、71、73、79、83、89
は40です。
質問が約 1,000,000,000 integers(x) で、0 >= x <= 2,147,483,647 であり、OP が (要素(499,999,999) + 要素(500,000,000)) / 2 (数値がソートされている場合) を探していたと仮定します。 また、100 台すべてのコンピューターがすべて等しいと仮定します。
ラップトップと GigE を使用して...
私が見つけたのは、私のラップトップが 1.3 秒で 10,000,000 個の Int32 をソートできるということでした。したがって、大まかな見積もりでは、10 億個の数値の並べ替えに 100 x 1.3 秒 (2 分 10 秒) かかることになります;)。
ギガビット イーサネットでの 40MB ファイルの一方向のファイル転送の推定値は 0.32 秒です。これは、すべてのコンピューターからのソート結果が約 32 秒で返されることを意味します (コンピューター 99 は、開始後 30 秒までファイルを取得しませんでした)。そこから、最も低い 499,999,998 の数字を破棄し、次の 2 を足して 2 で割ります。
これは、投票されたアルゴリズム (n log n) - 順序統計分散選択アルゴリズム - O(n)よりも高速に実行できます。この
問題を、ソートされていない配列で k 番目の数を見つけるという元の問題に単純化します。
- 並べ替えヒストグラム O(n) のカウント
数値の範囲に関するいくつかのプロパティを想定する必要があります。範囲はメモリに収まりますか? - 外部マージソート - O(n log n) - 上で説明
基本的に、最初のパスで数値をソートし、2 番目のパスで中央値を見つけます。
- 数値の分布について何かわかっている場合は、他のアルゴリズムを作成できます。
詳細と実装については、
http ://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html を参照してください。
O(n)奇妙なことに、コンピューターが十分にある場合は、中央値検出アルゴリズムを使用するよりも並べ替えを行った方がよいと思います。(ただし、コアが非常に遅い場合を除き、私は 1 つだけを使用し、O(n)1e9 の数値のみに中央値検出アルゴリズムを使用します。ただし、1e12 の場合は、あまり実用的ではない可能性があります。)
とにかく、この問題に対処するために log n 個以上のコアがあり、電力消費は気にせず、ただ答えを早く得られるとしましょう。さらに、すべてのデータがすでにメモリにロードされている SMP マシンであると仮定します。(たとえば、Sun の 32 コア マシンはこのタイプです。)
1 つのスレッドがリストをやみくもに同じサイズの断片に切り刻み、他の M スレッドにそれらを並べ替えるように指示します。それらのスレッドは、時間内に熱心にそうし(n/M) log (n/M)ます。次に、中央値だけでなく、たとえば 25 パーセンタイルと 75 パーセンタイルも返します (わずかに異なる数値を選択すると、最悪のケースがより適切になります)。これで、4M 範囲のデータが得られました。次に、これらの範囲を並べ替えて、その数値よりも小さいか、その数値を含むすべての範囲を破棄すると、データの半分を破棄するような数値が見つかるまで、リストを上方向に処理します。それが中央値の下限です。上限についても同じことを行います。これには時間のようなものがかかりM log M、すべてのコアがそれを待たなければならないので、本当に無駄ですM^2 log M潜在的な時間。これで、単一のスレッドが他のスレッドに範囲外のすべてのデータを破棄するよう指示し (パスごとに約半分を破棄する必要があります)、繰り返します。これは、データが既にソートされているため、非常に高速な操作です。log(n/M)残りのデータを取得して標準のO(n)中央値ファインダーを使用する方が高速になるまで、これを何度も繰り返す必要はありません。
したがって、全体の複雑さは のようなものO((n/M) log (n/M) + M^2 log M log (n/M))です。したがって、これは、説明したシナリオにO(n)当てはまります。M >> log(n/M)M^3 log M < n
非効率であることを考えると、これは本当に悪い考えだと思いますが、より高速です。
より簡単な方法は、重み付けされた数値を使用することです。
この問題を解決するには、1 台のコンピューターで十分です。
しかし、100 台のコンピューターがあると仮定しましょう。あなたがしなければならない唯一の複雑なことは、リストをソートすることです。それを100パーツに分割し、1パーツを各コンピューターに送り、そこでソートさせ、その後パーツをマージします。
次に、ソートされたリストの中央から番号を取得します (つまり、インデックスが 5 000 000 000 の場合)。
それはあなたのデータに依存します。最悪のシナリオは、それが一様に分布した数になることです。
この場合、次の例のように O(N) 時間で中央値を見つけることができます。
数値が 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (範囲は 1 ～ 10) であるとします。 .
1-3、4-7、8-10 の 3 つのバケットを作成します。上と下のサイズが同じであることに注意してください。
バケツに数字を入れて、最大値と最小値のそれぞれにいくつ入るかを数えます
平均は真ん中のバケツに入り、残りは無視します
3 つのバケットを作成します: 4、5-6、7。Low はカウント 5 で始まり、最大 3 で、High は最小 8 でカウント 5 です。
数値ごとに、低バケットと高バケット、最大バケットと最小バケットに該当する数をカウントし、中間バケットを保持します。
これで、中央値を直接計算できます。次のような状況があります。
old low low middle high old high
x x x x x 4 4 4 4 4 4 5 6 6 7 7 x x x x x
したがって、中央値は 4.5 です。
分布について少し知っていると仮定すると、範囲を定義して速度を最適化する方法を微調整できます。いずれにせよ、1 + 1/3 + 1/9... = 1.5 であるため、パフォーマンスは O(N) と一致するはずです。
エッジケースのため、最小値と最大値が必要です (たとえば、中央値が古い安値の最大値と次の要素の間の平均である場合)。
これらの操作はすべて並列化できます。各コンピューターに 1/100 のデータを与え、各ノードで 3 つのバケットを計算し、保持しているバケットを分散できます。これにより、各数値が平均で 1.5 回 (O(N)) 渡されるため、ネットワークを効率的に使用できます。ノード間で最小数のみを渡す場合でも、それを打ち負かすことができます (たとえば、ノード 1 に 100 個の数があり、ノード 2 に 150 個の数がある場合、ノード 2 はノード 1 に 25 個の数を与えることができます)。
分布について詳しく知らない限り、実際には要素を少なくとも 1 回カウントする必要があるため、ここで O(N) よりもうまくできるとは思えません。
これは、ノード間でソートされていないデータ (ログ ファイルなど) を使用して、次の方法でノード上で実行できます。
1 つの親ノードと 99 の子ノードがあります。子ノードには 2 つの API 呼び出しがあります。
親ノードは、すべての子ノードで stats() を呼び出し、すべてのノードの最小値と最大値を記録します。
二分探索は、次の方法で実行できます。
1 つの親ノードと 99 の子ノードがあります。子ノードには 2 つの API 呼び出しがあります。
親ノードは、すべての子ノードで stats() を呼び出し、すべてのノードの最小値と最大値を記録します。
二分探索は、次の方法で実行できます。
stats() と compare() が O(N/Mlogn/M) ソートで事前計算できる場合、事前計算のメモリー複雑度が O(N) の O(N/M) 事前計算計算。次に、一定時間でcompare()を実行できるため、すべて(事前計算を含む)はO(N/MlogN/M)+O(logN)で実行されます
間違いがあれば教えてください！
10^9 の数字を分割します。10^7 を各コンピューターに分割し、それぞれに 80MB を割り当てます。各コンピューターはその番号を並べ替えます。次に、コンピューター 1 は、コンピューター 2、コンピューター 3 および 4 などからの数値を使用して、自分の数値をマージソートします。次に、コンピューター 1 は、数値の半分を 2 に、3 を 4 に、などに書き戻します。次に、1 マージは、コンピューターからの数値をソートします。 1,2,3,4、それらを書き戻します。等々。コンピューターの RAM のサイズによっては、各ステップで個々のコンピューターにすべての数値を書き戻さなくても済む場合があります。コンピューター 1 の数値をいくつかのステップで累積できる場合がありますが、計算は自分で行います。
ああ、最後に 500000000 番目と 500000001 番目の値の平均を取得します (ただし、そこに十分な 00 があることを確認してください。まだ行っていません)。
編集：@Roman - それが本当だとしても信じられないなら、私が命題の真偽を明らかにしても意味がありません。私が言おうとしたのは、力ずくの力がレースで賢さを打ち負かすことがあるということです。実装できると確信しているアルゴリズムを考案するのに約 15 秒かかりました。このアルゴリズムは機能し、さまざまなサイズの入力とコンピューターの数に適応でき、コンピューターの特性に合わせて調整できます。ネットワーキングの取り決め。あなたや他の誰かが、より洗練されたアルゴリズムを考案するのに 15 分かかると言うなら、私にはソリューションをコード化して実行を開始するのに 14 分 45 秒のアドバンテージがあります。
しかし、私はこれがすべて主張であることを率直に認めます。私は何も測定していません。
スティーブ・ジェソップの答えが最速だと思います。
ネットワークデータ転送サイズがボトルネックである場合は、別のアプローチがあります。
Divide the numbers into 100 computers (10 MB each).
Loop until we have one element in each list
Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median.
Send the medians to a central computer and find the median of medians. Then send the median back to each computer.
For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part.
When we have one number in each list, send them to the central computer and find and return the median.
中央値を見つけるには、トーナメント ツリー法を使用できます。各リーフ ノードが配列になるように、1000 個のリーフ ノードを持つツリーを作成できます。次に、異なる配列間で n/2 トーナメントを実施します。n/2 トーナメント後のルートの値が結果です。
http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
個別の整数の数が (たとえば) 40 億であることがわかっている場合、それらを 64k バケットにバケット化し、クラスター内の各マシン (100 台のコンピューター) から各バケットの分散カウントを取得できます。これらすべてのカウントを組み合わせます。ここで、中央値を持つバケットを見つけます。今回は、ターゲット バケットにある 64k 要素のバケットのみを要求します。これには、「クラスター」に対する O(1) (具体的には 2) クエリが必要です。:D
これはどうですか:- 各ノードは 100 分の 10 の数字を取ることができます。各ノードで要素をソートし、中央値を見つけることができます。中央値の中央値を見つけます。すべてのノードの中央値未満の数のカウントを集計することにより、中央値の中央値が作る x%:y% 分割を見つけることができます。ここで、すべてのノードに、中央値の中央値よりも小さい要素を削除するように依頼します (30%:70% の分割を例にとると)。30% の数値が削除されます。10 億の 70% は 7 億です。300 万未満のノードを削除したすべてのノードは、それらの余分なノードをメイン コンピューターに送り返すことができます。メイン コンピューターは、すべてのノードがほぼ同じ数のノード (700 万) を持つように再分散します。問題が 7 億の数に減ったので.... 1 つのコンプで計算できるより小さなセットが得られるまで続けます。
まず、1 台のマシンで n 個の数値の中央値を見つける方法を考えてみましょう。私は基本的にパーティショニング戦略を使用しています。
問題 :selection(n,n/2) :最小数から n/2 番目の数を見つけます。
たとえば、中央の要素 k を選択し、データを 2 つのサブ配列に分割します。1 番目にはすべての要素 < k が含まれ、2 番目にはすべての要素 >= k が含まれます。
sizeof(1st sub-array) >= n/2 の場合、このサブ配列に中央値が含まれていることがわかります。次に、2 番目のサブアレイを捨てることができます。この問題を解決するselection(sizeof 1st sub-array,n/2) .
それ以外の場合は、この 1 番目のサブ配列を破棄して選択を解決します (2 番目のサブ配列、n/2 - sizeof(1 番目のサブ配列))
再帰的に実行します。
時間の複雑さはO(n) 予想時間です。
多くのマシンがある場合、反復ごとに配列を処理して分割する必要があり、配列を差分マシンに分散します。各マシンはアレイのチャンクを処理し、要約をハブ制御マシンに送り返します。つまり、1 番目のサブアレイのサイズと 2 番目のサブアレイのサイズです。ハブ マシンは集計を合計し、さらに処理するサブアレイ (1 番目または 2 番目) と選択の 2 番目のパラメーターを決定し、それを各マシンに送り返します。等々。
このアルゴリズムは、map reduce を使用して非常にきれいに実装できますか?
それはどのように見えますか？
数値が明確ではなく、特定の範囲にのみ属している場合、つまり、数値が繰り返されている場合、99 台のマシンに数値を均等に分配し、1 台のマシンをマスターとして保持するという簡単な解決策が思い浮かびます。現在、すべてのマシンは指定された数値を繰り返し処理し、各数値のカウントをハッシュ セットに格納します。その特定のコンピューターに割り当てられた一連の数値で数値が繰り返されるたびに、ハッシュ セット内のカウントが更新されます。
次に、すべてのマシンがハッシュ セットをマスター マシンに返します。マスター マシンはハッシュ セットを結合し、ハッシュ セットで見つかった同じキーの数を合計します。たとえば、マシン #1 のハッシュ セットには ("1",7) のエントリがあり、マシン #2 のハッシュ セットには ("1",9) のエントリがあったため、マスター マシンはハッシュ セットを結合するときに次のエントリを作成します。 ("1", 16) など。
ハッシュ セットがマージされたら、キーを並べ替えるだけで、並べ替えられたハッシュ セットから (n/2) 番目のアイテムと (n+2/2) 番目のアイテムを簡単に見つけることができます。
10 億の数字が異なる場合、この方法は役に立ちません。
私のペニーの価値は、他の人によってすでに持ち出されたすべての後に:
単一のマシンで中央値を見つけるのは O(N) です: https://en.wikipedia.org/wiki/Selection_algorithm。
N 個の番号を 100 台のマシンに送信することも O(N) です。したがって、100 台のマシンを使用して興味深いものにするためには、通信が比較的高速である必要があるか、N/100 が実行可能であるのに単一のマシンでは処理できないほど N が大きいか、または気にせずに数学的な問題を検討したいだけのいずれかです。データ通信。
手短に言えば、合理的な制限内で、効率分析に影響を与えずに数値を送信/配布できると仮定します。
次に、1 台のマシンが一般的な処理の「マスター」に割り当てられる次のアプローチを検討してください。これは比較的高速であるため、「マスター」も各マシンが実行する共通タスクに参加します。
時間の複雑さ:
中央値を概算する方法を提案します。:) これらの 10 億の数字がランダムな順序になっている場合、10 億の数字の 1/100 または 1/10 をランダムに選択し、100 マシンで並べ替えてから、それらの中央値を選択できると思います。または、10 億の数字を 100 の部分に分割し、各機械に各部分の 1/10 をランダムに選択させ、それらの中央値を計算させます。その後、100 個の数値が得られ、100 個の数値の中央値を簡単に計算できます。単なる提案です。数学的に正しいかどうかはわかりません。でも、数学が苦手なマネージャーに結果を見せてもいいと思います。
10 億の数字を 100 のマシンに分割します。各マシンには 10^7 の数字があります。
マシンに着信する数値ごとに、その数値を頻度マップに格納します (数値 -> カウント)。また、各マシンに最小数を保存します。
各マシンの中央値を見つける: 各マシンの最小数から始めて、中央値インデックスに達するまでカウントを合計します。各マシンの中央値は、およそになります。5*10^6 より小さい数値と大きい数値。
すべての中央値の中央値を見つけます。これは、約より小さく、大きくなります。50*10^7 の数値。これは 10 億の数値の中央値です。
次に、2 番目のステップの最適化: 周波数マップに格納する代わりに、カウントを可変ビット配列に格納します。例：マシンの最小数から始めて、これらは頻度カウントです：
[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count
上記は、次のようにビット配列に格納できます。
[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000
各マシンは 10^7 の数しか処理しないため、合計で各マシンに約 10^7 ビットのコストがかかることに注意してください。10^7 ビット = 1.25*10^6 バイト、つまり 1.25MB
したがって、上記のアプローチでは、ローカルの中央値を計算するために各マシンに 1.25MB のスペースが必要になります。また、中央値の中央値は、これらの 100 のローカル中央値から計算でき、10 億の数値の中央値になります。
Steve Jessop の答えは間違っています。
次の 4 つのグループを検討してください。
{2、4、6、8、10}
{21, 21, 24, 26, 28}
{12, 14, 30, 32, 34}
{16, 18, 36, 38, 40}
中央値は 21 で、これは 2 番目のグループに含まれています。
4 つのグループの中央値は 6、24、30、36 で、合計の中央値は 27 です。
したがって、最初のループの後、4 つのグループは次のようになります。
{6, 8, 10}
{24, 26, 28}
{12, 14, 30}
{16, 18, 36}
21 はすでに誤って破棄されています。
このアルゴリズムは、2 つのグループがある場合のみサポートします。