?

Log in

No account? Create an account
Нэцкэ

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

Задачка 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.

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

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

Если у нас поток символов очень большой длины, то удобнее всего сделать массив для гистограммы, который покроет 16 битные целые. И два раза пробежаться по потоку (для старших 16 бит и для младших 16 бит), рассчитав гистограмму частоты вхождения каждого числа и взяв медиану по гистограмме. Места займет всего 8*2^16 байт, т.е. меньше мегабайта.

http://stackoverflow.com/questions/3572640/interview-question-find-median-from-mega-number-of-integers/3576479#3576479

Если у нас массив с числами и он уже помещается в памяти, то можно применить метод Медиан Медианов:
http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Он линеен по времени и использует сортировку "на месте", т.е. в исходном массиве.

Пример воплощения алгоритма:
http://books.google.ru/books?id=qhaOxkQANEgC&lpg=PA75&ots=dC9cXH7rQw&dq=BFPRT%20implementation&pg=PA75#v=onepage&q&f=false


realurix сказал подсказал, что эта задачка на знание и понимание теоремы кодирования Шеннона. Этого я не очень понял, поскольку теорема Шеннона она про сжатие и передачу сигнала по каналу с шумом. Единственный похожий на эту задачу подход я обнаружил в Алгоритме сжатия Шеннона — Фано, там строится частотная таблица точь-в-точь, как наша гистограмма.
Tags: , ,

Comments

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

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

вы не путаете медиану с арифметическим средним?
Я на всякий случай переспросил, саму теорему я пока не смотрел. Число, количество повторов, очевидно нельзя хранить, ибо чисел может быть много.
Не путаю. Медиана - это такое значение в ранжированной (упорядоченной) последовательности, для которого 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.

Убрав из последовательности "хвост" и "нос" мы получаем интервал чисел, в котором должна находиться медиана. Для оставшейся последовательности можно повторить процедуру еще уменьшив интервал. Только обязательно нужно еще как-то учитывать отдельно число отброшенных чисел больше и меньше интервала. В общем, можно обойтись без сортировки последовательности.
А сколько итераций потребуется в среднем для просчета медианы с помощью подсчета разрядов?
Не больше, чем половина числа разрядов. Т.е., сложность будет равна O(N*log2(N)/2).
то есть сложность сортировки, что, наверное, неудивительно.
Сложность сортировки qsort O(N^2). Омикрон - это, по определению, верхняя граница (наихудший случай).

Не подскажете, о какой сортировке Вы говорили, имея в виду O(N*log(N))?
Сложность сортировки qsort в среднем O(N log N). Но есть методы, например, http://en.wikipedia.org/wiki/Heapsort у которых и в худшем случае O(N log N). Другое дело, что на практике, алгоритм, не меняющий элементы местами, будет все равно быстрее.
Если в среднем, то тогда сложность вычисления медианы равна O(N). ;-))

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

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

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

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

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

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

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


Edited at 2011-08-23 10:24 am (UTC)
Кстати, построив гистограмму по первым нескольким миллионам элементов, уже можно понять какие две корзины - кандидаты на содержание медианы.

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


Edited at 2011-08-26 09:48 am (UTC)