9

キーがシーケンスの数を表し、値がこの数がシーケンスに出現する頻度をカウントするマップの場合、Java でのアルゴリズムの実装はどのように中央値を計算するようになりますか?

例えば：

1,1,2,2,2,2,3,3,3,4,5,6,6,6,7,7

地図で：

Map<Int,Int> map = ...
map.put(1,2)
map.put(2,4)
map.put(3,3)
map.put(4,1)
map.put(5,1)
map.put(6,3)
map.put(7,2)

double median = calculateMedian(map);
print(median);

次のようになります。

> print(median);
3
>

だから私が探しているのは、のJava実装ですcalculateMedian。

4

4 に答える 4

5

線形時間

数字の合計がわかっている場合 (あなたの場合は 16)、マップの最初または最後から移動して、(n/2) 番目の要素に到達するまでカウントを合計できます。 sum は、 floor(n/2) 番目と ceil(n/2) 番目の要素 = medianの平均に偶数です。

合計数がわからない場合は、それらすべてを少なくとも 1 回は実行する必要があります。

サブリニア時間

データ構造を決定し、前処理を行うことができる場合は、選択アルゴリズムに関するウィキペディアを参照してください。サブリニア アルゴリズムも得られる可能性があります。データの分布についてある程度わかっている場合は、サブリニア時間も取得できます。

編集：したがって、カウントのあるシーケンスがあるという仮定の下で、私たちができることは

  • key -> countペアを挿入している間、別のマップを維持します-key -> running_total
  • このようにして、最後のキーの running_total を見ることで total_count を取得できる構造が得られます
  • 二分探索を実行して、実行中の合計が total_count/2 に近い要素を見つけることができます。

これにより、メモリ使用量が 2 倍になりますが、中央値では O(log n) のパフォーマンスが得られ、total_count では O(1) のパフォーマンスが得られます。

于 2010-06-16T12:21:23.683 に答える
5

グアバの使用：

Multiset<Integer> values = TreeMultiset.create();
Collections.addAll(values, 1,1,2,2,2,2,3,3,3,4,5,6,6,6,7,7);

あなたの質問に対する答えは次のとおりです。

return Iterables.get(values, (values.size() - 1) / 2);

本当。それでおしまい。 (または、正確に言うと、サイズが偶数であるかどうかを確認し、2 つの中央の値を平均します。)

カウントが特に大きい場合は、マルチセットを使用しentrySetて実行中の合計を保持する方が高速ですが、通常は最も簡単な方法で問題ありません。

于 2010-06-16T15:21:43.657 に答える
2
  • を使用しますSortedMap。つまり、TreeMap
  • マップを 1 回反復して、要素の総数、つまりすべての出現の合計を計算します。
  • もう一度反復して、合計の半分に達するまで発生を合計します。合計が合計の半分を超えた数が中央値です
  • オフバイワンエラーを広範囲にテストする
于 2010-06-16T11:59:31.397 に答える
1

簡単だがあまり効率的ではないアルゴリズムの場合、次のようにします。

1. マップをリストに展開します。

実際に話された: マップを反復処理し、キー「値-時間」を新しいリストに追加します。最後にリストをソートします。

//...
List<Integer> field = new ArrayList<Integer>();
for (Integer key:map) {
  for (int i = 0; i < map.get(key); i++) {
    field.add(key);
  }
}
Collections.sort(field);

2. 中央値を計算する

次に、メソッドを実装する必要がありますint calculateMedian(List<Integer> sorted)。これは、必要な中央値の種類によって異なります。サンプルの中央値だけの場合、結果は中間値 (要素数が奇数のリストの場合) または中間値 2 つの平均 (長さが偶数のリストの場合) になります。リストはソートする必要があることに注意してください。

（参照：サンプル中央値/ウィキペディア）

OK、OK、クリスは効率について言及していませんでしたが、マップを拡張せずにサンプルの中央値 (!) を計算する方法のアイデアを次に示します...

Set<Integer> sortedKeys = new TreeSet<Integer>(map.keySet()); // just to be sure ;)
Integer median = null;  // Using Integer to have a 'invalid/not found/etc' state
int total = 0;
for (Integer key:sortedKeys) {
  total += map.get(key);
}
if (isOddNumber(total)) { // I don't have to implement everything, do I?
  int counter = total / 2;  // index starting with 0
  for (Integer key:sortedKeys) {
    middleMost -= map.get(key);
    if (counter < 0) {
      // the sample median was in the previous bin
      break;
    }
    median = key;
  }
} else {
  int lower = total/2;
  int upper = lower + 1;
  for (Integer key:sortedKeys) {
    lower -= map.get(key);
    upper -= map.get(key);
    if (lower < 0 && upper < 0) {
      // both middlemost values are in the same bin
      break;
    } else (lower < 0 || upper < 0) {
      // lower is in the previous, upper in the actual bin
      median = (median + key) / 2; // now we need the average
      break;
    }
    median = key;
  }
}

(手元にコンパイラがありません。構文エラーが多い場合は、疑似コードとして扱ってください;))

于 2010-06-16T12:06:21.093 に答える