От новичка до гуру: Курсы программирования на CyberDuff

Эффективный с точки зрения памяти способ вычисления медианы большого набора данных?

Если один компьютер может хранить только 1 миллион чисел, как узнать среднее число из 100 миллионов чисел?

median algorithm computer-science memory-efficient complexity-theory
25.09.2009

  • Заголовок stackoverflow.com/questions/1311764/ 25.09.2009
  • В лучшем случае это должна быть вики сообщества. 25.09.2009
  • Это правильный вопрос, связанный с программированием, как вычислить медиану с эффективным использованием памяти. Это просто приходит как головоломка. 25.09.2009
  • Используйте метод медианы медиан. 25.09.2009

Ответы:


1

Упростите задачу: отсортируйте 100 миллионов чисел с помощью сортировки слиянием. , возьмем 50-миллионный элемент.

25.09.2009
  • Но компьютер может хранить только 1 миллион чисел, как мне найти 50-миллионное? 25.09.2009
  • На ленте (ну точно, это уже не 80-е. Я имел в виду на диске), на 50-миллионной позиции. У вас есть хранилище для ваших 100 миллионов элементов, верно? Потому что, если вы этого не сделаете (элементы читаются из потока), упражнение может быть доказано невозможным с помощью аргумента подсчета. 25.09.2009
  • Неправильно, чтобы 100 миллионов чисел принимали 50-миллионный элемент, потому что 100 миллионов — четное число, поэтому нужно взять среднее значение 50-миллионного и 50-миллионного + 1 элемент. 06.02.2012

    • 2

    Выполните внешнюю сортировку, а затем просканируйте один раз медиану.

    Надеюсь, настоящая проблема заключалась в том, «как выполнить внешнюю сортировку»? (Если это домашнее задание... Я хочу помочь правильно. :-)

    25.09.2009
  • Вот что я подумал. :) Но я не уверен, что это правильный ответ, поэтому спросил здесь. 25.09.2009
  • Должен быть способ сделать это с буквальным ограничением, что устройство может хранить только 1 миллион чисел. Использование внешней сортировки похоже на мошенничество. Теперь я буду всю ночь думать об этом. 25.09.2009
  • Хех, я сам задавался этим вопросом. Это действительно хороший вопрос. 25.09.2009

    • 3

    Использование 101 компьютера и сортировка-слияние, как база данных.

    25.09.2009
  • Ржунимагу. Этот ответ должен стать лучшей шуткой программиста! 25.09.2009
  • Я приму это как один из моих ответов. :) 25.09.2009

    • 4

    Найдите средний миллион чисел, а затем сообщите их медиану. (Хммм, а теперь как найти эти средние миллионные числа...)

    25.09.2009
    Новые материалы
    Отслеживание состояния с течением времени с дифференцированием снимков
    Время от времени что-то происходит и революционизирует часть моего рабочего процесса разработки. Что-то более забавное вместо типичного утомительного и утомительного процесса разработки. В..
    Я предполагаю, что вы имеете в виду методы обработки категориальных данных.
    Я предполагаю, что вы имеете в виду методы обработки категориальных данных. Пожалуйста, проверьте мой пост Инструментарий специалиста по данным для кодирования категориальных переменных в..
    Игра в прятки с данными
    Игра в прятки с данными Я хотел бы, чтобы вы сделали мне одолжение и ответили на следующие вопросы. Гуглить можно в любое время, здесь никто не забивается. Сколько регионов в Гане? А как..
    «Раскрытие математических рассуждений с помощью Microsoft MathPrompter и моделей больших языков»
    TL;DR: MathPrompter от Microsoft показывает, как использовать математические рассуждения с большими языковыми моделями; 4-этапный процесс для улучшения доверия и рассуждений в математических..
    Раскройте свой потенциал в области разработки мобильных приложений: Абсолютная бесплатная серия
    Глава 6: Работа в сети и выборка данных Глава 1: Введение в React Native Глава 2: Основы React Native Глава 3: Создание пользовательского интерфейса с помощью React Native Глава 4:..
    Все о кейсах: Camel, Snake, Kebab & Pascal
    В программировании вы сталкивались с ними при именовании переменной, класса или функции. Поддержание согласованности типов и стилей случаев делает ваш код более читабельным и облегчает совместную..
    Как работает дистанционное парное программирование и почему оно может изменить вашу жизнь
    Серебряная пуля от одиночества и отвлекающих факторов во время обучения программированию Независимо от того, работаете ли вы или учитесь удаленно, велика вероятность, что одиночество и..