Boroda aka Hamster (fantaseour) wrote,
Boroda aka Hamster
fantaseour

Category:

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: bing!, cs, tech
Subscribe

  • Так. Чуть не бросил дневник :)

    Ну вот, хотел не бросать и опять сюда не пишу :( Потому, что в будние дни сил нет писать, а в выходные вот то у меня ДР, то у пасынка. То просто…

  • 46

    Дня рожденья пост. Ну ничего, мы еще позажигаем :)

  • (no subject)

    Я очень люблю конференции. Они зажигают в разработчике свечечку, которую он потом бережно несет в себе через весь год! Когда-то давно, я с завистью…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments

  • Так. Чуть не бросил дневник :)

    Ну вот, хотел не бросать и опять сюда не пишу :( Потому, что в будние дни сил нет писать, а в выходные вот то у меня ДР, то у пасынка. То просто…

  • 46

    Дня рожденья пост. Ну ничего, мы еще позажигаем :)

  • (no subject)

    Я очень люблю конференции. Они зажигают в разработчике свечечку, которую он потом бережно несет в себе через весь год! Когда-то давно, я с завистью…