Как найти медиану массива

Найти медиану из потока данных

В этом посте мы обсудим, как найти медиану в потоке текущих целых чисел.

Описание проблемы:

Медиана — это среднее значение в упорядоченном целочисленном списке. Если размер списка четный, среднего значения нет. Таким образом, медиана — это среднее из двух средних значений.

Разработайте структуру данных, которая поддерживает следующие две операции:

void addNum (int num) — добавить целое число из потока данных в структуру данных.

double findMedian () — возвращает медиану всех элементов на данный момент.

Пошаговое решение проблемы:

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

Временная сложность find () в приведенном выше подходе будет O (1), но, добавляя каждый раз, мы должны увеличивать размер массива на единицу, копировать в новый массив, а затем находить медиану, так что это довольно дорого O (n). Давайте подумаем, можем ли мы сделать лучше ……. .

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

a) нет элементов в верхнем ›нет элементов в нижнем, тогда очевидно, что последний элемент в отсортированном верхнем является медианным.

б) нет элементов в верхнем ‹нет элементов в нижнем, тогда очевидно, что первый элемент в отсортированном нижнем является медианным.

c) нет элементов в верхнем = нет элементов в нижнем, то медиана (последний элемент в отсортированном верхнем + первый элемент в отсортированном нижнем) / 2;

Инициализация: мы можем реализовать верхний уровень с помощью minHeap, а нижний — с помощью MaxHeap.

Добавить:

Временная сложность этого составляет O (logn).

Кейсы:

а) если обе кучи пусты, мы добавляем первый элемент в minHeap (мы также можем добавить в maxHeap).

б) Если num равно ‹minHeap (который хранит верхнюю половину в порядке убывания) пиковый элемент, это означает, что num не имеет места в minHeap с в настоящее время. Таким образом, его можно разместить в maxHeap при условии maxQueue.size () ≤minQueue.size ().

В противном случае мы извлекаем верхний элемент maxTop из maxHeap и сравниваем его с num, затем помещаем минимум (maxTop, num) в maxHeap и максимум от (maxTop, num) до minHeap.

c) Если num — это ›minHeap (который хранит верхнюю половину в порядке убывания) пиковый элемент, это означает, что num не имеет места в maxHeap с в настоящее время. Таким образом, его можно поместить в minHeap при условии maxQueue.size () ≥minQueue.size ().

В противном случае мы выталкиваем верхний элемент minTop из minHeap и предлагаем maxHeap, а num — minHeap.

Медианный результат:

Временная сложность этого составляет O (1).

Кейсы:

а) Если оба размера кучи равны, то медиана равна

б) В противном случае медиана находится на пике кучи, размер которой больше.

Name already in use

semester-work-median / README.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Поиск медианы в массиве за O(N)

Медиа́на набора чисел — число, которое находится в середине этого набора, если его упорядочить по возрастанию, то есть такое число, что половина из элементов набора не меньше него, а другая половина не больше.

Например, медианой набора <11, 9, 3, 5, 5>является число 5, так как оно стоит в середине этого набора после его упорядочивания: <3, 5, 5, 9, 11>. Если в выборке чётное число элементов, медиана может быть не определена однозначно: тогда для числовых данных чаще всего используют полусумму двух соседних значений (то есть медиану набора <1, 3, 5, 7>принимают равной 4). В математической статистике медиана может использоваться как одна из характеристик выборки или совокупности чисел.

Нахождение медианы списка может казаться тривиальной задачей, но ее выполнение за линейное время требует серьезного подхода. Для этого используется алгоритм, который является частным случаем «quickselect», разработанного Тони Хоаром, который также изобрел алгоритм сортировки с похожим названием — quicksort. Это рекурсивный алгоритм, и он может находить любой элемент (не только медиану).

В среднем pivot разбивает список на две приблизительно равных части. Поэтому каждая последующая рекурсия оперирует с 1⁄2 данных предыдущего шага.

Девиз команды «А кто такие фиксики — большой-большой секрет!»

Описание основных частей семестрового проекта.

Проект состоит из следующих частей:

/ include — реализация алгоритма (исходный код и заголовочные файлы); — контрольные тесты производительности структуры данных (поиск медианы); — наборы данных для запуска контрольных тестов;

• �� С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
• �� Система автоматизации сборки CMake (версия 3.12.x и выше).
• �� Java Development Kit (версия 8 и выше).
• �� Рекомендуемый объем оперативной памяти — не менее 4 ГБ.
• �� Свободное дисковое пространство объемом

Сборка и запуск

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):

Для ручной сборки проекта в терминале введите:

Генерация тестовых данных

Генерация тестового набора данных в формате comma-seperated values (CSV)

1. Склонируйте проект генератора набора случайных чисел ЗДЕСЬ к себе на устройство
2. Ознакомьтесь с инструкциями генерации
3. Сгенерируйте наборы данных

Контрольные тесты (benchmarks)

1. Последовательно добавляются элементы из файла со сгенерированным набором данных
2. Засекается время
3. Выполняется алгоритм поиска медианы
4. Фиксируется время
5. Время записывается в файл-результат

Результаты наших тестов: ЗДЕСЬ

Список контрольных тестов

Footer

© 2023 GitHub, Inc.

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Мой любимый алгоритм: нахождение медианы за линейное время

Самым прямолинейным способом нахождения медианы является сортировка списка и выбор медианы по её индексу. Самая быстрая сортировка сравнением выполняется за O(n log n) , поэтому от неё зависит время выполнения 1 , 2 .

У этого способа самый простой код, но он определённо не самый быстрый.

Нахождение медианы за среднее время O(n)

Следующим нашим шагом будет нахождение медианы в среднем за линейное время, если нам будет везти. Этот алгоритм, называемый «quickselect», разработан Тони Хоаром, который также изобрёл алгоритм сортировки с похожим названием — quicksort. Это рекурсивный алгоритм, и он может находить любой элемент (не только медиану).

1. Выберем индекс списка. Способ выбора не важен, на практике вполне подходит и случайный. Элемент с этим индексом называется опорным элементом (pivot).
2. Разделим список на две группы:
   1. Элементы меньше или равные pivot, lesser_els
   2. Элементы строго большие, чем pivot, great_els
   • Если в lesser_els есть k или больше элементов, рекурсивно обходим список lesser_els в поисках k-того элемента.
   • Если в lesser_els меньше, чем k элементтов, рекурсивно обходим список greater_els . Вместо поиска k мы ищем k-len(lesser_els) .

   Чтобы найти с помощью quickselect медиану, мы выделим quickselect в отдельную функцию. Наша функция quickselect_median будет вызывать quickselect с нужными индексами.

   В реальном мире Quickselect отлично себя проявляет: он почти не потребляет лишних ресурсов и выполняется в среднем за O(n) . Давайте докажем это.

   Доказательство среднего времени O(n)

   В среднем pivot разбивает список на две приблизительно равных части. Поэтому каждая последующая рекурсия оперирует с 1 ⁄₂ данных предыдущего шага.

   Существует множество способов доказательства того, что этот ряд сходится к 2n. Вместо того, чтобы приводить их здесь, я сошлюсь на замечательную статью в Википедии, посвящённую этому бесконечному ряду.

   Quickselect даёт нам линейную скорость, но только в среднем случае. Что, если нас не устраивает среднее, и мы хотим гарантированного выполнения алгоритма за линейное время?

   Детерминированное O(n)

   В предыдущем разделе я описал quickselect, алгоритм со средней скоростью O(n) . «Среднее» в этом контексте означает, что в среднем алгоритм будет выполняться за O(n) . С технической точки зрения, нам может очень не повезти: на каждом шаге мы можем выбирать в качестве pivot наибольший элемент. На каждом этапе мы сможем избавляться от одного элемента из списка, и в результате получим скорость O(n^2) , а не O(n) .

   С учётом этого, нам нужен алгоритм для подбора опорных элементов. Нашей целью будет выбор за линейное время pivot, который в худшем случае удаляет достаточное количество элементов для обеспечения скорости O(n) при использовании его вместе с quickselect. Этот алгоритм был разработан в 1973 году Блумом (Blum), Флойдом (Floyd), Праттом (Pratt), Ривестом (Rivest) и Тарьяном (Tarjan). Если моего объяснения вам не хватит, то можете изучить их статью 1973 года. Вместо того, чтобы описывать алгоритм, я подробно прокомментирую мою реализацию на Python:

   Давайте докажем, что медиана медиан является хорошим pivot. Нам поможет, если мы представим визуализацию нашего алгоритма выбора опорных элементов:

   

   Красным овалом обозначены медианы фрагментов, а центральным кругом — медиана медиан. Не забывайте, мы хотим, чтобы pivot разделял список как можно ровнее. В худшем возможном случае каждый элемент в синем прямоугольнике (слева вверху) будет меньше или равен pivot. Верхний правый прямоугольник содержит 3 ⁄₅ половины строк — 3/5*1/2=3/10 . Поэтому на каждом этапе мы избавляемся по крайней мере от 30% строк.

   Но достаточно ли нам отбрасывать 30% элементов на каждом этапе? На каждом этапе наш алгоритм должен выполнять следующее:

   • Выполнять работу O(n) по разбиению элементов
   • Для рекурсии решать одну подзадачу размером в 7 ⁄₁₀ от исходной
   • Для вычисления медианы медиан решать одну подзадачу размером с 1 ⁄₅ от исходной

   Не так уж просто доказать, почему это равно O(n) . Быстрое решение заключается в том, чтобы положиться на основную теорему о рекуррентных соотношениях. Мы попадаем в третий случай теоремы, при котором работа на каждом уровне доминирует над работой подзадач. В этом случае общая работа будет просто равна работе на каждом уровне, то есть O(n) .

   Подводим итог

   У нас есть quickselect, алгоритм, который находит медиану за линейное время при условии наличия достаточно хорошей опорного элемента. У нас есть алгоритм медианы медиан, алгоритм O(n) для выбора опорного элемента (который достаточно хорош для quickselect). Соединив их, мы получили алгоритм нахождения медианы (или n-ного элемента в списка) за линейное время!

   Медианы за линейное время на практике

   В реальном мире почти всегда достаточно случайного выбора медианы. Хотя подход с медианой медиан всё равно выполняется за линейное время, на практике его вычисление длится слишком долго. В стандартной библиотеке C++ используется алгоритм под названием introselect, в котором применено сочетание heapselect и quickselect; предел его выполнения O(n log n) . Introselect позволяет использовать обычно быстрый алгоритм с плохим верхним пределом в сочетании с алгоритмом, который медленнее на практике, но имеет хороший верхний предел. Реализации начинают с быстрого алгоритма, но возвращаются к более медленному, если не могут выбрать эффективные опорные элементы.

   В завершение приведу сравнение элементов, используемых в каждой из реализаций. Это не скорость выполнения, а общее количество элементов, которые рассматривает функция quickselect. Здесь не учитывается работа по вычислению медианы медиан.

   

   Именно этого мы и ожидали! Детерминированный опорный элемент почти всегда рассматривает при quickselect меньшее количество элементов, чем случайный. Иногда нам везёт и мы угадываем pivot с первой попытки, что проявляется как впадины на зелёной линии. Математика работает!

   How to calculate the median of an array?

   I’m trying to calculate the total, mean and median of an array thats populated by input received by a textfield. I’ve managed to work out the total and the mean, I just can’t get the median to work. I think the array needs to be sorted before I can do this, but I’m not sure how to do this. Is this the problem, or is there another one that I didn’t find? Here is my code:

   Sorting the array is unnecessary and inefficient. There’s a variation of the QuickSort (QuickSelect) algorithm which has an average run time of O(n); if you sort first, you’re down to O(n log n). It actually finds the nth smallest item in a list; for a median, you just use n = half the list length. Let’s call it quickNth (list, n).

   The concept is that to find the nth smallest, choose a ‘pivot’ value. (Exactly how you choose it isn’t critical; if you know the data will be thoroughly random, you can take the first item on the list.)

   Split the original list into three smaller lists:

   • One with values smaller than the pivot.
   • One with values equal to the pivot.
   • And one with values greater than the pivot.

   You then have three cases:

   1. The "smaller" list has >= n items. In that case, you know that the nth smallest is in that list. Return quickNth(smaller, n).
   2. The smaller list has < n items, but the sum of the lengths of the smaller and equal lists have >= n items. In this case, the nth is equal to any item in the "equal" list; you’re done.
   3. n is greater than the sum of the lengths of the smaller and equal lists. In that case, you can essentially skip over those two, and adjust n accordingly. Return quickNth(greater, n — length(smaller) — length(equal)).

   If you’re not sure that the data is thoroughly random, you need to be more sophisticated about choosing the pivot. Taking the median of the first value in the list, the last value in the list, and the one midway between the two works pretty well.

   If you’re very unlucky with your choice of pivots, and you always choose the smallest or highest value as your pivot, this takes O(n^2) time; that’s bad. But, it’s also very unlikely if you choose your pivot with a decent algorithm.

   Читать:

   Как открыть картинку в новом окне html