-2

質問は次のようになります。N台のマシンがあり、各マシンがN個の要素を格納して操作できると仮定すると、すべてのN^2要素の中央値を最低のコストで見つけるにはどうすればよいでしょうか。

それは本当に私をとても悩ませます、皆さんからの答えを得ることを望んでいます、ありがとう！

申し訳ありませんが、単純すぎて書き留めておきます。各マシンに格納されている要素はランダムであり、順序はありません。また、コストにはI / Oコストだけでなく、マシン間の通信、RAM、時間もすべて考慮する必要があります。中央値を取得するための最も効率的な方法を見つけたいだけです。

これらは私が思いついたいくつかの解決策です：

  1. マージソートなどの外部ソートを使用して、中央値を見つけます。
  2. バケットソートを使用し、すべての要素をその値に従ってX個の連続するバケットに分割します。これにより、中央値がどのバケットにあるかを判断できます。バケットをスキャンすると、中央値が取得されます。
  3. 「アルゴリズム入門」のO（N）アルゴリズムでk番目の数を見つけることはここでうまくいくはずだと思いますか？

しかし、それでも、これらのソリューションはすべて、その仕事をするために追加のマシンを必要とします。これらのN台のマシンだけを使用して中央値を取得できる方法があるかどうか疑問に思っていますか？

ありがとう！

4

3 に答える 3

0

正確に取得するのではなく、推定できますか?

その場合、定数 K を選択し、K 係数多項式を各マシンのデータに当てはめ、係数を中央のマシンに送信して加算し、中央値を次のように求めます。

  1. 範囲全体で曲線を積分して、曲線の下の領域を見つける
  2. 根探索アルゴリズムを実行して、領域を半分に分割する点を見つけます。

K が大きいほど、誤差は少なくなります。K が小さいほど、効率的になります。

于 2012-04-20T18:33:25.167 に答える
0

すべての値 (すべての店舗の合計) をカウントするプロセスが必要です。中間のインデックスを選択します。インデックスを調整して、適切なマシン上のアイテムの開始位置からオフセットします。そのマシンにアイテムを並べ替えて、そのインデックスの値を返すように依頼します。

于 2012-04-20T16:49:20.600 に答える
0 
Step 1: Sort the numbers at each machine individually
Step 2: Send the median at each machine to a central place
Step 3: Sort the medians and send it to each machine
Step 4: For each element in the sorted medians calculate the rank at machine level
Step 5: Calculate the rank of each element over all machines (just sum the rank)
Step 6: Find two elements in the sorted medians between which the global median exists
Step 7: For the next iteration consider only elements between those two medians 
        and repeat the whole thing again

最悪の場合、2 回目の反復で残りのすべての要素が 1 台のマシンに配置されます。

複雑さ: O(nlogn) であることは確かです (つまり、口蓋化を含めると O(n^2logn) になる可能性があります)。

于 2012-04-20T17:13:24.723 に答える