При меньших размерах окна n log n
сортировка может работать. Есть ли лучшие алгоритмы для достижения этой цели?
algorithms
median
Мик
источник
источник
Ответы:
Нехорошо сортировать массив для вычисления медианы. Медианы (и другие квантили) обычно вычисляются с использованием алгоритма быстрого выбора со сложностью .O ( n )
Вы также можете посмотреть мой ответ на недавний связанный с этим вопрос здесь .
источник
Вот статья, описывающая один из возможных алгоритмов. Исходный код включен и довольно серьезное приложение (обнаружение гравитационных волн на основе лазерной интерферометрии), так что вы можете ожидать, что он будет хорошо протестирован.
источник
Если вы готовы терпеть приближение, есть другие методы. Например, одно приближение - это значение, ранг которого находится на некотором (указанном пользователем) расстоянии от истинной медианы. Например, медиана имеет (нормализованный) ранг 0,5, и если вы укажете погрешность 10%, вам потребуется ответ с рангом от 0,45 до 0,55.
Если такой ответ уместен, то есть много решений, которые могут работать на скользящих окнах данных. Основная идея состоит в том, чтобы поддерживать выборку данных определенного размера (примерно 1 / ошибка) и вычислять медиану для этой выборки. Можно показать, что с высокой вероятностью, независимо от характера входных данных, результирующая медиана удовлетворяет свойствам, которые я упоминал выше.
Таким образом, главный вопрос заключается в том, как сохранить текущую выборку данных определенного размера, и для этого существует множество подходов, включая метод, известный как отбор проб из пласта. Например, этот документ: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136
источник
Если вы сохраняете окно данных длины k в виде отсортированного двусвязного списка, то с помощью бинарного поиска (для вставки каждого нового элемента по мере его перемещения в окно) и кругового массива указателей (чтобы сразу найти элементы, которые необходимо удалить), каждый сдвиг окна требует O (log (k)) усилий для вставки одного элемента, только O (1) усилий для удаления элемента, сдвинутого из окна, и только O (1) усилий для поиска медиана (потому что каждый раз, когда один элемент вставляется или удаляется в список, вы можете обновить указатель на медиану за O (1) раз). Таким образом, общее усилие по обработке массива длины N составляет O ((nk) log (k)) <= O (n log (k)). Это лучше, чем любой другой метод, предложенный до сих пор, и это не приближение, это точно.
источник
Как вы упоминали, сортировка будет
O(n·log n)
для окна длиныn
. Выполнение этого перемещения добавляет еще однуl=vectorlength
общую стоимостьO(l·n·log n)
.Самый простой способ добиться этого - сохранить упорядоченный список последних n элементов в памяти при переходе от одного окна к следующему. Поскольку удаление / вставка одного элемента из / в упорядоченный список являются обоими,
O(n)
это приведет к затратам наO(l·n)
.псевдокод:
источник
Вот решение O (1) для нахождения текущей медианы и O (log n) для добавления нового номера http://www.dsalgo.com/RunningMedian.php
источник
Если вы можете жить с оценкой вместо истинной медианы, алгоритм Ремедиана (PDF) является однопроходным с низкими требованиями к памяти и четко определенной точностью.
источник
Я использовал эту библиотеку RunningStats C ++ во встроенном приложении. Это самая простая библиотека статистики, которую я когда-либо нашел.
По ссылке:
источник