Как найти медиану значений в Hashtable в Java?

Question

У меня есть Hashtable<String, Integer> ht.

Как эффективно найти значения (целочисленного) медианного в этой хэш-таблице?

Answer 1

Вы можете использовать The Apache Commons Mathematics Library

Существует полный API для всех математических инструментов, которые могут понадобиться, например, как median, mean, standard deviation и т.д ...

Надежда, что помогает.

Answer 2

В хеш-таблице нет значимого порядка: вся точка хеш-таблицы должна равномерно распределять значения в ведрах в соответствии с их ключом. Поиск элемента, дающего ключ, очень быстро, почти постоянное время (т. Е. O (1)), но алгоритмы на основе неравенства, скажем, найдя все элементы e такие, что ключ (e) < K для заданного значения ключа K, как правило, требует сканирование таблицы, которое представляет собой O (N).

Вы можете загрузить все ключи (и только ключи) в массив, а затем использовать алгоритм (O (N)), чтобы найти ключ, соответствующий медианной. Когда у вас есть медианный ключ, вы можете использовать его для извлечения медианного элемента из своей хеш-таблицы.

Обратите внимание, что O (N) - это, по-видимому, лучшее, что вы можете сделать, чтобы найти медиану неупорядоченного набора. Если вам нужно часто находить медиану множества, то упорядоченное представление, например. на основе сбалансированных деревьев, это путь. Красно-черные деревья обычно используются для реализации таких упорядоченных карт. Ключевым поиском будет O (log (N)), который медленнее, чем O (1), но все же довольно быстрый, но набор уже упорядочен, и найти медианную информацию легко и обычно предоставляется как встроенная операция.

Быстрый медианный алгоритм поиска, который я знаю, основан на той же стратегии поворота, что и в Quicksort. Вот еще один, который я только что нашел:

http://www.cs.cornell.edu/courses/cs2110/2009su/Lectures/examples/MedianFinding.pdf