Как вычислить или приблизить медиану списка, не храня список

Вот сумасшедший подход, который Вы могли бы попробовать. Это - классическая проблема в потоковой передаче алгоритмов. Правила

1. , Вы имеете ограниченную память, говорите O(log n), где n количество объектов, Вы хотите
2. , можно посмотреть на каждый объект однажды и принять решение прямо здесь, что сделать с ним при хранении его это стоит памяти при броске его далеко, этого не стало навсегда.

идея для нахождения медианы проста. Образец O(1 / a^2 * log(1 / p)) * log(n) элементы из списка наугад, можно сделать это через выборку водохранилища (см. предыдущий вопрос ). Теперь просто возвратите медиану из своих выбранных элементов, с помощью классического метода.

гарантия - то, что индекс возвращенного объекта будет (1 +/- a) / 2 с вероятностью по крайней мере 1-p. Таким образом, существует вероятность p сбоя, можно выбрать его путем выборки большего количества элементов. И это возврат привычки медиана или гарантия, что значение возвращенного объекта где угодно близко к медиане, просто что при сортировке списка, возвращенный объект будет близко к половине списка.

Этот алгоритм использование O(log n) дополнительное пространство и выполнения в Линейное время.

Я не думаю, что возможно обойтись без наличия списка в памяти. Можно, очевидно, приблизиться с

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

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

основная идея сделать гистограмму является самой многообещающей. Это позволяет Вам накопить информацию о распределении и запросы ответа (как медиана) от него. Медиана будет приблизительна, так как Вы, очевидно, не храните все значения. Пространство памяти фиксируется так, оно будет работать с любой последовательностью длины, которую Вы имеете.

, Но Вы не можете только создать гистограмму из, говорят, что первые 100 значений и используют ту гистограмму постоянно.. изменяющиеся данные могут сделать ту гистограмму недопустимой. Таким образом, Вам нужна динамическая гистограмма, которая может изменить ее диапазон и мусорные ведра на лету.

Делают структуру, которая имеет мусорные ведра N. Вы сохраните X значений каждого перехода слота (общее количество значений N+1), а также население мусорного ведра.

Поток в Ваших данных. Запишите первые значения N+1. Если концы потока перед этим, большим, у Вас есть все загруженные значения, и можно найти точную медиану и возвратить ее. Еще используйте значения для определения первой гистограммы. Просто отсортируйте значения и используйте значения как определения мусорного ведра, каждое мусорное ведро, имеющее население 1. Нормально иметь простофиль (0 мусорных ведер ширины).

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

, Но это недостаточно.. все еще необходимо АДАПТИРОВАТЬ гистограмму к данным, поскольку это передается потоком в. Когда мусорное ведро становится переполненным, Вы теряете информацию о sub распределении того мусорного ведра. Можно зафиксировать это путем адаптации на основе некоторой эвристики... Самое легкое и большая часть устойчивого - то, если мусорное ведро достигает некоторого населения определенного порога (что-то как 10*v/N, где v =# значений, замеченных до сих пор в потоке и N, является количеством мусорных ведер), Вы РАЗДЕЛЯЕТЕ то переполненное мусорное ведро. Добавьте новое значение в средней точке мусорного ведра, дайте каждой стороне половину населения исходного мусорного ведра. Но теперь у Вас есть слишком много мусорных ведер, таким образом, необходимо УДАЛИТЬ мусорное ведро. Хорошая эвристика для этого должна найти мусорное ведро с самым маленьким продуктом населения и ширины. Удалите его и объедините его с его левым или правым соседом (какой бы ни у одного из соседей самого есть самый маленький продукт ширины и населения.).Договорились! Обратите внимание, что слияние или разделение мусорных ведер теряют информацию, но это неизбежно.. Вы только починили устройство хранения данных.

Этот алгоритм хорош в этом, он будет иметь дело с [1 111] весь типы входных потоков и давать хорошие результаты. Если у Вас есть роскошь выбора пробного заказа, случайная выборка является лучшей, так как это минимизирует разделения и слияния.