Возможный дубликат:
алгоритм скользящей медианы в C
Учитывая, что целые числа читаются из потока данных. Найдите медиану прочитанных элементов эффективным способом.
Решение, которое я прочитал: мы можем использовать максимальную кучу на левой стороне для представления элементов, которые меньше эффективной медианы, и минимальную кучу на правой стороне для представления элементов, которые превышают эффективную медиану.
После обработки входящего элемента количество элементов в кучах отличается не более чем на 1 элемент. Когда обе кучи содержат одинаковое количество элементов, мы находим среднее значение корневых данных кучи как эффективную медиану. Когда кучи не сбалансированы, мы выбираем эффективную медиану из корня кучи, содержащей больше элементов.
Но как мы построим максимальную кучу и минимальную кучу, то есть как мы узнаем эффективную медиану здесь? Я думаю, что мы вставили бы 1 элемент в max-heap, а затем следующий 1 элемент в min-heap и так далее для всех элементов. Поправь меня, если я здесь не прав.
Ответы:
Существует несколько различных решений для определения медианы бега по потоковым данным, я кратко расскажу о них в самом конце ответа.
Вопрос о деталях конкретного решения (макс. Кучи / мин. Кучи) и о том, как работает решение на основе кучи, объясняется ниже:
Для первых двух элементов добавьте меньший к maxHeap слева, а больший к minHeap справа. Затем обработайте данные потока по одному,
Тогда в любой момент времени вы можете рассчитать медиану так:
Теперь я расскажу о проблеме в целом, как и было обещано в начале ответа. Найти медиану из потока данных - сложная задача, и найти точное решение с эффективными ограничениями памяти, вероятно, невозможно в общем случае. С другой стороны, если данные имеют некоторые характеристики, которые мы можем использовать, мы можем разработать эффективные специализированные решения. Например, если мы знаем, что данные являются целочисленным типом, то мы можем использовать счетную сортировку, который может дать вам постоянную память постоянного алгоритма времени. Решение на основе кучи является более общим решением, поскольку оно может использоваться и для других типов данных (удваивается). И, наконец, если точная медиана не требуется и достаточно приближения, вы можете просто попытаться оценить функцию плотности вероятности для данных и оценить медиану, используя ее.
источник
Если вы не можете держать все элементы в памяти одновременно, эта проблема становится намного сложнее. Решение для кучи требует, чтобы вы держали все элементы в памяти одновременно. Это невозможно в большинстве реальных применений этой проблемы.
Вместо этого, как вы видите номера, следить за кол количества раз вы видите каждое целое число. Предполагая 4-байтовые целые, это 2 ^ 32 сегмента, или не более 2 ^ 33 целых (ключ и число для каждого целого), что составляет 2 ^ 35 байт или 32 ГБ. Вероятно, это будет намного меньше, чем это, потому что вам не нужно хранить ключ или счетчик для тех записей, которые равны 0 (т.е. как defaultdict в python). Требуется постоянное время для вставки каждого нового целого числа.
Затем в любой момент, чтобы найти медиану, просто используйте количество, чтобы определить, какое целое число является средним элементом. Это требует постоянного времени (хотя и большой постоянной, но тем не менее постоянной).
источник
Если дисперсия входных данных является статистически распределенной (например, нормальная, логарифмическая и т. Д.), То выборка из резервуара является разумным способом оценки процентилей / медиан из произвольно длинного потока чисел.
«Резервуар» - это бегущая, равномерная (справедливая) выборка всех входных данных - независимо от размера. Поиск медианы (или любого процентиля) - это прямая задача сортировки резервуара и опроса интересующей точки.
Поскольку резервуар имеет фиксированный размер, сортировка может считаться эффективной O (1) - и этот метод работает с постоянным временем и потреблением памяти.
источник
Самый эффективный способ вычисления процентиля потока, который я нашел, - это алгоритм P²: Радж Джейн, Имрих Хламтак: Алгоритм P² для динамического вычисления квантилей и гистограмм без сохранения наблюдений. Commun. ACM 28 (10): 1076-1085 (1985)
Алгоритм прост в реализации и работает очень хорошо. Это оценка, однако, имейте это в виду. Из аннотации:
источник
Если мы хотим найти медиану из n самых последних увиденных элементов, у этой задачи есть точное решение, для которого необходимо сохранить только n самых последних увиденных элементов в памяти. Это быстро и хорошо масштабируется.
An индексируемые skiplist опоры О (пер п) вставка, удаление и индексированный поиск произвольных элементов, сохраняя при этом порядок сортировки. В сочетании с очередью FIFO, которая отслеживает n-ю самую старую запись, решение простое:
Вот ссылки на полный рабочий код (простая для понимания версия класса и оптимизированная версия генератора с индексируемым кодом пропускаемого списка):
http://code.activestate.com/recipes/576930-efficient-running-median-using-an-indexable-skipli/
http://code.activestate.com/recipes/577073 .
источник
Интуитивно понятный способ думать об этом заключается в том, что если бы у вас было полностью сбалансированное бинарное дерево поиска, то корнем был бы медианный элемент, поскольку там было бы одинаковое количество меньших и больших элементов. Теперь, если дерево не заполнено, это не совсем так, поскольку на последнем уровне будут отсутствовать элементы.
Поэтому вместо этого мы можем получить медиану и два сбалансированных бинарных дерева, одно для элементов, меньших, чем медиана, и одно для элементов, превышающих медиану. Два дерева должны быть одинакового размера.
Когда мы получаем новое целое число из потока данных, мы сравниваем его с медианой. Если оно больше медианы, мы добавляем его в нужное дерево. Если два размера дерева отличаются более чем на 1, мы удаляем элемент min правого дерева, делаем его новой медианой и помещаем старую медиану в левое дерево. Аналогично для меньших.
источник
Эффективное - это слово, которое зависит от контекста. Решение этой проблемы зависит от количества выполненных запросов относительно количества вставок. Предположим, вы вводите N чисел и K раз к концу, который вас интересовал медианой. Сложность алгоритма на основе кучи будет O (N log N + K).
Рассмотрим следующую альтернативу. Вставьте числа в массив, и для каждого запроса запустите алгоритм линейного выбора (скажем, с помощью стержня быстрой сортировки). Теперь у вас есть алгоритм с временем выполнения O (KN).
Теперь, если K достаточно мало (редкие запросы), последний алгоритм на самом деле более эффективен, и наоборот.
источник
Разве вы не можете сделать это только с одной кучей? Обновление: нет. Смотрите комментарий.
Инвариант: после прочтения
2*n
входных данных минимальная куча содержитn
наибольшее из них.Цикл: прочитайте 2 входа. Добавьте их обоих в кучу и удалите мин кучи. Это восстанавливает инвариант.
Таким образом, когда
2n
считаны входные данные, min кучи является n-м по величине. Для усреднения двух элементов вокруг средней позиции и обработки запросов после нечетного числа входных данных потребуется немного больше сложностей.источник