Как рассчитать медиану карты <Int, Int>?

Question

Для карты, где ключ представляет номер последовательности и значение, подсчитывающее частоту появления этого числа в последовательности, как будет выглядеть реализация алгоритма в 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.

Answer 1

Линейное время

Если вам известно общее количество чисел (в вашем случае это 16), вы можете перейти от начала или конца карты и подвести итоги.пока вы не доберетесь до круглого (n / 2) -го элемента или в случае, если сумма будет даже средней к полу (n / 2) -го и ceil (n / 2) -ых элементов = медиана .

Если вы не знаете общего количества, вам придется хотя бы один раз пройти их все.

Сублинейное время

Если вы можете решитьна структуру данных и может сделать предварительную обработку см. википедию по алгоритм выбора , и вы можете получить даже сублинейный алгоритм.Вы также можете получить сублинейное время, если знаете что-то о распределении данных.

РЕДАКТИРОВАТЬ: Таким образом, при условии, что у нас есть последовательность с подсчетами, мы можем сделать это

• в то время каквставка пар key -> count поддерживает другую карту - key -> running_total
• , таким образом, у вас будет структура, в которой вы сможете получить total_count, посмотрев на последний ключ running_total
• и вы сможете выполнить бинарный поиск, чтобы найти элемент, в котором итоговая сумма близка к total_count / 2

Это удвоит использование памяти, но даст O (log n) производительность для медианы и O (1) для total_count.

Answer 2

Использование Гуава :

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);

Действительно. Вот и все. (Или проверьте, является ли размер четным, и усредните два центральных значения, если быть точным.)

Если счет особенно велик, было бы быстрее использовать entrySet мультимножества и сохранить текущую сумму, но обычно проще всего подойдет.

Answer 3

• Используйте SortedMap, то есть TreeMap
• . Итерируйте карту один раз, чтобы вычислить общее количество элементов, т.е. сумму всех вхождений
• Итерируйте сноваи складывайте события до тех пор, пока не достигнете половины общего количества.Число, которое привело к тому, что сумма превысила половину от общей суммы, представляет собой медиану
• Обширный тест на ошибки «один на один»

Answer 4

Для простого, но, возможно, не очень эффективного алгоритма я бы сделал это так:

1.разверните карту до списка.

практически произнесено: переберите карту и добавьте ключ 'value-times' в новый список.Наконец, сортируйте список.

//...
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).Это зависит от того, какая медиана вам нужна.Если это просто пример медианы, то результатом является либо самое среднее значение (для списков с нечетным числом элементов), либо среднее значение двух средних значений (для списков с четной длиной).Обратите внимание, что список должен быть отсортирован!

(Ссылка: Пример Медиана / Википедия )

---

ОК, ОК, хотя Крис не упомянулэффективность, вот идея, как рассчитать медиану образца (!) без расширения карты ...

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;
  }
}

(у меня нет компилятора под рукой - если он имеет много синтаксических ошибок, трактуйте его как псевдокод, пожалуйста;))