Нетривиальный алгоритм вычисления медианы скользящего окна

Мне нужно рассчитать бегущую медиану:

Ввод: , , вектор . $n$ $k$ $(x_1, x_2, \dotsc, x_n)$
Вывод: vector , где - это медиана . $(y_1, y_2, \dotsc, y_{n-k+1})$ $y_i$ $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$

(Нет мошенничества с приближениями; я хотел бы иметь точные решения. Элементы являются большими целыми числами.) $x_i$

Существует тривиальный алгоритм, который поддерживает дерево поиска размера ; общее время работы . (Здесь «дерево поиска» относится к некоторой эффективной структуре данных, которая поддерживает вставки, удаления и срединные запросы в логарифмическом времени.) $k$ $O(n \log k)$

Тем не менее, это кажется немного глупым для меня. Мы эффективно изучим всю статистику заказов во всех окнах размера , а не только в медианах. Более того, на практике это не слишком привлекательно, особенно если велико (большие деревья поиска имеют тенденцию быть медленными, накладные расходы на потребление памяти нетривиальны, эффективность кеширования часто низкая и т. Д.). $k$ $k$

Можем ли мы сделать что-нибудь существенно лучше?

Существуют ли нижние оценки (например, является ли тривиальный алгоритм асимптотически оптимальным для модели сравнения)?

Изменить: Дэвид Эппштейн дал хороший нижний предел для модели сравнения! Интересно, возможно ли все же сделать что-то немного более умное, чем тривиальный алгоритм?

Например, можем ли мы сделать что-то в этом духе: разделить входной вектор на части размера ; сортировать каждую часть (отслеживая исходные позиции каждого элемента); а затем использовать кусочно отсортированный вектор, чтобы эффективно найти текущие медианы без каких-либо вспомогательных структур данных? Конечно, это все равно будет , но на практике сортировка массивов, как правило, происходит намного быстрее, чем поддержка деревьев поиска. $k$ $O(n \log k)$

Изменить 2: Saeed хотел увидеть некоторые причины, почему я думаю, сортировка быстрее, чем операции дерева поиска. Вот очень быстрые тесты для , : $k = 10^7$ $n = 10^8$

≈ 8 с: сортировка векторов с элементами каждый $n/k$ $k$
≈ 10 с: сортировка вектора с элементами $n$
≈ 80 с: вставок и удалений в хеш-таблице размера $n$ $k$
≈ 390 с: вставок и удалений в сбалансированном дереве поиска размера $n$ $k$

Хеш-таблица существует только для сравнения; это не имеет прямого использования в этом приложении.

Таким образом, мы имеем почти 50-кратное различие в производительности сортировки и сбалансированных операциях дерева поиска. И все станет намного хуже, если мы увеличим . $k$

(Технические детали: Данные = случайные 32-разрядные целые числа. Компьютер = типичный современный ноутбук. Тестовый код был написан на C ++ с использованием стандартных библиотечных процедур (std :: sort) и структур данных (std :: multiset, std :: unsorted_multiset). Я использовал два разных компилятора C ++ (GCC и Clang) и две разные реализации стандартной библиотеки (libstdc ++ и libc ++). Традиционно std :: multiset был реализован как высокооптимизированное красно-черное дерево.)

ds.algorithms ds.data-structures lower-bounds Юкка Суомела
источник

Я не думаю , что вы будете в состоянии улучшить

. Причина в том, если вы посмотрите на окно

, вы никогда не можете исключить ни одно из чисел

n l o g k

$nlogk$

x_{t}, . . ., x_{t + k - 1}

$x_t,...,x_{t+k-1}$

из медианы будущего окна. Это означаетчто в любое время вы должны держатькрайней мере

x_{t + \frac{k}{2}}, . . ., x_{t + k - 1}

$x_{t+\frac{k}{2}},...,x_{t+k-1}$

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

\frac{k}{2}

$\frac{k}{2}$

РБ

Мне кажется, что ваш тривиальный алгоритм

не

, я что-то не так понял? И я думаю, что из-за этого у вас есть проблема с большим

, иначе логарифмический фактор ничего не значит в практических приложениях, также нет большой скрытой константы в этом алгоритме.

O ((n - k) \cdot k \cdot \log k)

$O((n-k)\cdot k \cdot \log k)$

O (n \log k)

$O(n \log k)$

k

$k$

Саид

@Saeed: в тривиальном алгоритме вы обрабатываете элементы один за другим; на шаге

вы добавляете

в дерево поиска и (если

) вы также удаляете

из дерева поиска. Это

шагов, каждый из которых занимает

времени.

i

$i$

x_{i}

$x_i$

i > k

$i > k$

x_{i - k}

$x_{i-k}$

n

$n$

O (\log k)

$O(\log k)$

Юкка Суомела

То есть вы имеете в виду сбалансированное дерево поиска, а не случайное дерево поиска?

Саид

@Saeed: Обратите внимание, что в моих тестах я даже не пытался найти медианы. Я только что сделал

вставок и

удалений в дереве поиска размера

, и эти операции гарантированно займут

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

, но на практике он будет смехотворно медленным, а также тратит много времени. памяти.

n

$n$

n

$n$

k

$k$

O (\log k)

$O(\log k)$

O (n \log n)

$O(n \log n)$

Юкка Суомела

Ответы:

Вот нижняя граница от сортировки. Учитывая, что входной набор длины должен быть отсортирован, создайте вход для вашей текущей задачи медианы, состоящей из копий числа, меньшего, чем минимум , затем самого , затем копий числа, большего, чем максимум , и установите . Ходовые медианы этого входа такие же , как в отсортированном порядке . $S$ $n$ $n-1$ $S$ $S$ $n-1$ $S$ $k=2n-1$ $S$

Таким образом, в сравнительной модели вычислений требуется время . Возможно, если ваши входные данные являются целыми числами и вы используете алгоритмы целочисленной сортировки, вы можете добиться большего. $\Omega(n\log n)$

Дэвид Эппштейн
источник

Этот ответ действительно заставляет меня задуматься, верно ли и обратное: получим ли мы эффективный алгоритм сортировки, получим ли мы эффективный алгоритм работы медианы? (Например, подразумевается ли в алгоритме эффективной целочисленной сортировки эффективный алгоритм выполнения медианы для целых чисел? Или алгоритм IO-эффективной сортировки обеспечивает алгоритм медианной обработки, эффективный в IO?)

Юкка Суомела

Еще раз, большое спасибо за ваш ответ, это действительно поставило меня на правильный путь и дало вдохновение для алгоритма медианного фильтра на основе сортировки! В конце концов, мне удалось найти статью 1991 года, в которой приводились те же аргументы, что и здесь, а Пэт Морин дал указатель на другую соответствующую статью 2005 года; см. ссылки [6] и [9] здесь .

Юкка Суомела

Изменить: Этот алгоритм теперь представлен здесь: http://arxiv.org/abs/1406.1717

Да, для решения этой проблемы достаточно выполнить следующие операции:

Сортировать векторов, каждый из которых элементов. $n/k$ $k$
Делать линейную обработку времени.

Очень грубо, идея заключается в следующем:

Рассмотрим два смежных блока ввода, и , оба с элементами; пусть элементы будут и в порядке появления во входном векторе . $a$ $b$ $k$ $a_1, a_2, ..., a_k$ $b_1, b_2, ..., b_k$ $x$
Сортируйте эти блоки и изучите ранг каждого элемента в блоке.
Дополните векторы и указателями предшественника / преемника, чтобы, следуя цепочкам указателей, мы могли проходить элементы в возрастающем порядке. Таким образом, мы построили двусвязные списки и . $a$ $b$ $a'$ $b'$
Один за другим, удалить все элементы из связанного списка , в обратном порядке появления . Всякий раз, когда мы удаляем элемент, помните, каким был его преемник и предшественник на момент удаления . $b'$ $b_k, b_{k-1}, ..., b_1$
Теперь сохраните «срединные указатели» и которые указывают на списки и соответственно. Initialise к средней точке , и Initialise к хвосту пустого списка . $p$ $q$ $a'$ $b'$ $p$ $a'$ $q$ $b'$
Для каждого : $i$
- Удаление из списка (это время, просто удалите из связанного списка). Сравните с элементом, на который указывает чтобы увидеть, удалили ли мы до или после . $a_i$ $a'$ $O(1)$ $a_i$ $p$ $p$
- Поместите обратно в список в его исходное положение (это раз, мы запомнили предшественника и преемника ). Сравните с элементом, на который указывает чтобы увидеть, добавили ли мы элемент до или после . $b_i$ $b'$ $O(1)$ $b_i$ $b_i$ $q$ $q$
- Обновите указатели и таким образом, чтобы медиана объединенного списка либо в либо в . (Это раз, просто следуйте связанным спискам один или два шага, чтобы все исправить. Мы будем отслеживать, сколько элементов находится до / после и в каждом списке, и мы будем поддерживать инвариант, что оба и указывают на элементы, которые находятся максимально близко к медиане.) $p$ $q$ $a' \cup b'$ $p$ $q$ $O(1)$ $p$ $q$ $p$ $q$

Связанные списки - это просто массивы -элементных индексов, поэтому они легковесны (за исключением того, что локальность доступа к памяти плохая). $k$

Вот пример реализации и тесты:

https://github.com/suomela/median-filter

Вот график времени работы (для ): $n \approx 2\cdot 10^6$

Синий = сортировка + постобработка, . $O(n \log k)$
Зеленый = поддерживать две кучи, , реализация с https://github.com/craffel/median-filter $O(n \log k)$
Красный = поддерживать два дерева поиска, . $O(n \log k)$
Черный = сохранить отсортированный вектор, . $O(n k)$
$\approx k/2$
Ось Y = время работы в секундах.
Данные = 32-разрядные целые и случайные 64-разрядные целые числа из различных распределений.

время работы

Юкка Суомела
источник

$m$ $O(n \log m + m \log n)$

$O(\log m)$ $O(\log n)$ $O(\log n)$ заряд происходит только один раз за медиану.

$O(n \log m + m \log k)$

Джеффри Ирвинг
источник

К сожалению, это не работает так, как написано, поскольку, если вы не удалите элементы, счетчики не будут отражать новое окно. Я не уверен, что это можно исправить, но я оставлю ответ, если есть способ.

Джеффри Ирвинг

O (n \log m)

$O(n \log m)$

примечание стороны: Вопрос не ясен, подчиненная структура данных не определена, мы просто знаем что-то очень расплывчатое. Как вы хотите улучшить то, что вы не знаете, что это такое? как вы хотите сравнить свой подход?

Саид

Я извиняюсь за незавершенную работу. Я задал конкретный вопрос, необходимый для исправления этого ответа здесь: cstheory.stackexchange.com/questions/21778/… . Если вы считаете, что это уместно, я могу удалить этот ответ, пока не будет решен дополнительный вопрос.

Джеффри Ирвинг,