Как рассчитать точную медиану отсортированного массива, не занимая весь массив и с постоянным пространством?

Question

Мне нужно прочитать отсортированный массив из ввода в awk / gawk и получить медиану. Я не хочу хранить весь массив и пытаюсь получить постоянное место для расчета.

Вам известен какой-нибудь алгоритм, делающий это? Учитывая, что массив отсортирован, но его размер неизвестен.

Заранее спасибо!

Answer 1

Не существует алгоритма для точного определения медианы отсортированной последовательности неизвестной длины, которая работает с фиксированным объемом памяти.

Чтобы увидеть это, рассмотрим такой алгоритм.Скажем, у него есть буфер длины N для хранения элементов из последовательности.Пока этот буфер не заполнен, алгоритм просто помещает в него элементы, отслеживая медиану при этом.

Когда алгоритм сканирует N+1-й элемент и далее, он должен выбрать один элемент для отбрасывания на каждом шаге.Предположим, он уже отсканировал 2N элементов, уронив половину из них.Давайте дадим ему преимущество сомнения и скажем, что он еще не отбросил медиану входного потока.

Рассмотрим, когда он сканирует 2N+1 -й элемент.Какой предмет он должен уронить?Он не может отбросить наименьший элемент, который у него был до сих пор, поскольку после этого элемента ввод может быть исчерпан, и в этом случае самым низким может быть медиана.Аналогично для любого возможного элемента, который он может отбросить, у входной последовательности есть будущее, которое делает этот отброшенный элемент медианой.

Если вы готовы принять приблизительные результаты, то этот оценщик может работать для вас.

Answer 2

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

Answer 3

По сути, вы запрашиваете «алгоритм» для определения размера N массива, потому что медиана будет номером элемента (N+1)/2 (игнорируя четные / нечетные детали на данный момент).

Я не могу придумать алгоритм, который не включает два прохода.По определению, вам нужен первый проход, чтобы выяснить N.

Во время сканирования элемента i+1 вы можете сохранить буфер предыдущих элементов i/2.Когда вы достигнете конца массива, медиана будет просто первым значением в буфере, то есть потребуется только один проход.Проблема в том, что вам нужно было бы выделить достаточно памяти для буфера, чтобы он содержал N/2 элементов - но вы не знаете, что такое N, поэтому вы не знаете, насколько большим должен быть буфер!Также, если значения N слишком велики для хранения, как вы указали в вопросе, то предположительно значения N/2 также слишком велики для хранения (в противном случае мой совет: просто удвойте объем ОЗУ).

Так что этот буферный подход не вариант.Два прохода это.Один, чтобы выяснить N, другой, чтобы получить элемент (N+1)/2.