MS. Разбор полетов-2

[fantaseour]

Задачка 2 с вариацией:
There is a file that contains 10G(1000000000) number of integers, please find the Median of these integers. you are given 2G memory to do this.

Вариация: у нас есть большой, но не огромный массив с целыми числами вместо файла.

Собственно по ссылке в моем исходном посте и было указано два решения

Comments

[realurix]

Не путаю. Медиана - это такое значение в ранжированной (упорядоченной) последовательности, для которого 50% членов имеет не большее значение и 50% имеет не меньшее значение. Это определение содержит ряд моментов, затрудняющие использование и вычисление медианы. Если имеется чётное количество случаев и два средних значения различаются, то медианой может служить любое число между ними (например, в выборке {1,2,3,4} медианой может служить любое число из интервала (2,3)). На практике в этом случае чаще всего используют среднее арифметическое двух средних значений. Если есть ряд {1,1,2,2,2,2,2}, то медианой, по определению, будет 2.

Смысл медианы - среднее наиболее вероятное значение. Например, пусть были уплачены налоги {5,5,5,6,10000}. Медиана последовательности показывает, что средний человек платит налог в размере 5. На практике рассчитать медиану при больших последовательностях очень сложно - сначала нужно отсортировать последовательность.

Для случайных последовательностей медиана совпадает со средним арифметическим. Для последовательностей с "тяжелым хвостом" медиана меньше среднего арифметического, а для последовательностей с "легкой головой" больше.

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

Однако, при просчете количества ненулевых разрядов мы сразу получаем интервал, в котором находится медиана. Убираем те старшие разряды, сумма колличества которых меньше половины чисел в последовательности. Возьмем последовательность {2,2,2,5,32}. Колличество ненулевых разрядов будет таким:
A0 => 1
A1 => 3
A2 => 1
A3 => 0
A4 => 1
Отсюда видно, что нужно отбросить 4 и 2 разряды, чтобы отсечь "тяжелый хвост". Т.е., медиана должна быть меньше 2^1+2^0=3. И отсюда же видно, что нужно отсечь 0-й разряд. Т.е., медиана должна быть больше 2^0=1. Сканируя второй раз последовательность находим единственное число - 2. В данном случае можно не сканировать второй раз, поскольку 1 < 2 < 3.

Убрав из последовательности "хвост" и "нос" мы получаем интервал чисел, в котором должна находиться медиана. Для оставшейся последовательности можно повторить процедуру еще уменьшив интервал. Только обязательно нужно еще как-то учитывать отдельно число отброшенных чисел больше и меньше интервала. В общем, можно обойтись без сортировки последовательности.

[realurix]

Не больше, чем половина числа разрядов. Т.е., сложность будет равна O(N*log2(N)/2).

[realurix]

Сложность сортировки qsort O(N^2). Омикрон - это, по определению, верхняя граница (наихудший случай).

Не подскажете, о какой сортировке Вы говорили, имея в виду O(N*log(N))?

[realurix]

Если в среднем, то тогда сложность вычисления медианы равна O(N). ;-))

Самым эффективным методом будет метод построения гистограммы. Но у него есть один недостаток - заранее неизвестны минимальное и максимальное число. Поэтому первый проход используется для определения максимального и минимального чисел. Вторым проходом строится гистограмма для K интервалов. Выбирается в качестве наибольшего и нименьшего значений тот интервал, в котором находится медиана. Затем делается еще один проход построения гситограммы, но уже для K интервалов из выбранного интервала. И так далее, пока не будет найдена медиана. Сложность O(N+N*ln(N)/ln(K)). Сложность можно уменьшить на один проход (на N), если на первом этапе сделать отсев "тяжелого хвоста" и "легкого клюва". В итоге получаем O(N*logK(N)). Для 10G чисел для K=1000 число проходов будет 4 или 5.

[realurix]

Не больше, чем половина числа разрядов. Т.е., сложность будет равна O(N*log2(N)/2).

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

Этим алгоритмом сразу отсекаются "тяжелый хвост" и легкий "клюв". Эффективность алгоритма зависит от характера последовательности чисел. Я не утверждаю, что это оптимальный алгоритм. Но это, надеюсь, довольно неожиданное применение свойств чисел в позиционной нормальной форме. ;-))

[_winnie]

ИМХО, это какой-то очень сложный способ с гистограммами.

Только в гистограммах используется не двоичные разряды для записи чисел, а например система по основанию 65536.

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

[realurix]

Не сложнее линейных гистограмм. Это построение гистограмм в логарифмическом масштабе. Первый проход при построении линейных гистограм нужен для выяснения наибольшего и наименьшего значения для того, чтобы разбить интервал (min,max) на K интервалов. Для того, чтобы первый проход не был пустым, то его можно заполнить построением логарифмической гистограммы, благодаря которой легко отсеиваются "тяжелый хвост" и "легкий клюв", убирая примерно до 30% значений. Только до отбрасывания ненужных старших и младших разрядов нужно найти целую часть логарифма по основанию 2 среднего арифметического, и из значений разрядов вычесть это среднее арифметическое. При втором и следующих проходах из каждого значения нужно вычитать среднее арифметическое. Так центрируется медиана. Если не центрировать, то наименьшие значения (легкий клюв) будут плохо отбрасываться. Поскольку отбрасывание ненужных разрядов происходит как справа, так и слева, то удаление разрядов происходит с двух сторон и, значит, число проходов не может превышать половины числа разрядов. Только и всего.