Вопрос про медиану и алгоритмы

[Gaziz]

Всем привет,

Сорри если это ужу здесь спрашивалось. Объясните не программисту как решаются вот такие задачи:

- дан большой массив целых чисел который не влезает в память. Как найти его медиану?
- как находить всех друзей друзей у произвольного количества пользователей соц. сетей - какие использовать алгоритмы
- дано 10000 петобайт данных - найти количество битов выставленных в "1".

[Marmot]

- дан большой массив целых чисел который не влезает в память. Как найти его медиану?

В каком виде дан? Насколько точное значение медианы нужно, каков диапазон значений чисел?

- как находить всех друзей друзей у произвольного количества пользователей соц. сетей - какие использовать алгоритмы

эээ, а данные в каком виде?

- дано 10000 петобайт данных - найти количество битов выставленных в "1".

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

[Gaziz]

>> - дан большой массив целых чисел который не влезает в память. Как найти его медиану?
>В каком виде дан? Насколько точное значение медианы нужно, каков диапазон значений чисел?

Например массив лежит на 2000 машинах. Нужно найти с погрешностью в 1%.

[Marmot]

>> - дан большой массив целых чисел который не влезает в память. Как найти его медиану?
>В каком виде дан? Насколько точное значение медианы нужно, каков диапазон значений чисел?

Например массив лежит на 2000 машинах. Нужно найти с погрешностью в 1%.

аааа, тогда, прикидываем диапазон значений, делим этот диапазон на разумное число кусочков , 10К, например, потом на каждой машине в массив из 10К считаем куда сколько попало.
Потом сливаем все эти гистограмы вместе, и находим медиану.

[Gaziz]

> Потом сливаем все эти гистограмы вместе, и находим медиану.

Спасибо! А что находится в гистограмме? И как это относится к медиане?

[Marmot]

> Потом сливаем все эти гистограмы вместе, и находим медиану.

Спасибо! А что находится в гистограмме? И как это относится к медиане?

http://ru.wikipedia.org/wiki/%D0%9C%D0% ... %BA%D0%B0)

[LeoV]

Искусство программирования (англ. The Art of Computer Programming) — фундаментальная монография известного американского математика и специалиста в области компьютерных наук Дональда Кнута, посвященная рассмотрению и анализу важнейших алгоритмов, используемых в информатике. В 1999 году книга была признана одной из двенадцати лучших физико-математических монографий столетия.

Любимая книга всех времен и народов

[Waterbyte]

Например массив лежит на 2000 машинах. Нужно найти с погрешностью в 1%.

как непрограммист, я бы сказал, что эта погрешность достижима уже на шестой-седьмой тысяче элементов случайной выборки. то есть выборки размером 10 тысяч элементов должно хватить за глаза. из каждой пятой машины вытянуть по 25 элементов массива, слить в один, и искать там медиану.

насчёт друзей друзей в соцсетях не знаю. наверное, сначало как-то надо задачку формализовать, а потом уже алгоритмизировать.

[putanik]

1. y(k+1)=y(k) + step_size(k) * sign(x(k)-y(k));
stochastic approximation step_size(k) = 1/k;


2. назовите любое разумое число объяснив его "алгоритмом" название которого состоит из любых двух заумных фамилий. медианных алгоритмов десятки, если не сотни. все равно никто всех их не знает.

3. запрограммировать алгоритм - лиха беда начало. отладить и оттестировать более-менее сложный алгоритм без знания теории - нереально.

[Marmot]

3. запрограммировать алгоритм - лиха беда начало. отладить и оттестировать более-менее сложный алгоритм без знания теории - нереально.

Поэтому лучше всего использовать простые алгоритмы

[Waterbyte]

- дано 10000 петобайт данных - найти количество битов выставленных в "1".

мне кажется, примерно половина всех битов будет выставлена в 1. то есть около 10^4*10^15*8/2. если и ошибсо, то не думаю, что очень сильно.

[Gaziz]

Есть интересная задача про 100 дверей. С наскока не смог ее решить и подсмотрел решение у интересного парня - Игоря Клейнера
http://www.youtube.com/watch?v=Z41uWyelHKE