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]

У Шеннона много теорем. В том числе и теорема о кодировании. Из нее следует, что вполне достаточно посчитать частоту единичных значений каждого разряда.

Числа представляются в позиционной нормальной форме. Т.е., как полином. Или как сумма An*2^n+...+A2*2^2+A1*2^1+A0*2^0. Для вычисления медианы нужно просуммировать все числа, а пототм разделить сумму на количество чисел. Это же самое можно сделать суммируя количество единиц в соответствующих разрядах, если прямое суммирование невозможно по каким-либо причинам (ограничения на разрядную сетку).

[realurix]

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

[_winnie]

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

Неточно, зато в одни проход.
Часто - достаточно точно.

[_winnie]

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

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