K-отсортированная последовательность

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

Почти отсортированные последовательности особенно полезны, когда точный порядок элементов не имеет большого значения. Например Твиттер почти сортировать твиты с точностью до секунды, поскольку в большей точности нет необходимости. Фактически, учитывая невозможность точно синхронизировать все компьютеры, точная сортировка всех твитов по времени их публикации невозможна. Эта идея привела к созданию идентификаторов Snowflake .

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

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

Определение

Учитывая положительное число $k$, последовательность $[a_{1},\dots ,a_{n}]$ Говорят, что это $k$-сортировано, если для каждого $1\leq i$ и для каждого $i+k\leq j\leq n$, $a_{i}\leq a_{j}$. То есть последовательность необходимо упорядочивать только для пар элементов, расстояние которых не менее $k$.

Радиус ​ последовательности $\alpha$, обозначенный ${\text{ROUGH}}(\alpha )$ или ${\text{Par}}(\alpha )$ самый маленький $k$ такая, что последовательность $k$- отсортировано. Радиус является мерой предварительной сортировки .

Последовательность называется почти отсортированной или грубо отсортированной, если ее радиус мал по сравнению с ее длиной.

Эквивалентное определение

Последовательность $[a_{1},\dots ,a_{n}]$ является $k$-сортируется тогда и только тогда, когда каждый диапазон длины $2k+2$, $[a_{i},a_{i+1},\dots ,a_{i+2k+2}]$ является $k$- отсортировано.

Характеристики

Все последовательности длины $n$ являются $(n-1)$-сортированный, то есть $0\leq {\text{Par}}([a_{1},\dots ,a_{n}])<n$. Последовательность $0$-sorted тогда и только тогда, когда оно отсортировано. А $k$-сортированная последовательность автоматически $(k+1)$-отсортировано, но не обязательно $(k-1)$- отсортировано.

Связь с отсортированными последовательностями

Дана последовательность a $k$-сортированная последовательность $[a_{1},\dots ,a_{n}]$ и его отсортированная перестановка $[a_{\sigma _{1}},\dots ,a_{\sigma _{n}}]$, $|i-\sigma _{i}|$ самое большее $k$.

Алгоритмы

Решение о том, является ли последовательность $k$-сортированный

Решение о том, является ли последовательность $[a_{1},\dots ,a_{n}]$ является $k$-сортировка может выполняться в линейном времени и постоянном пространстве с помощью потокового алгоритма . Этого достаточно для каждого $1\leq i<n-k$, чтобы следить $\max(a_{j}\mid j\leq i)$ и проверить это $a_{i+k}\geq \max(a_{j}\mid j\leq i)$.

Вычисление радиуса последовательности

Вычисление радиуса последовательности можно вычислить в линейном времени и пространстве. Это следует из того, что его можно определить как $\max(i-j\mid \min(a_{k}\mid k\geq i)<\max(a_{k}\mid k\leq j))$.

Уменьшение радиуса последовательности вдвое

Учитывая $2k$-сортированная последовательность $\alpha =[a_{1},\dots ,a_{n}]$, можно вычислить $(k-1)$-сортированная перестановка $\alpha '$ из $\alpha$ в линейном времени и постоянном пространстве.

Во-первых, учитывая последовательность $\beta =[b_{1},\dots ,b_{2k}]$, допустим, что эта последовательность разбита, если $k$- вставлены меньшие элементы $[b_{1},\dots ,b_{k}]$ и $k$- находятся более крупные элементы $[b_{k+1},\dots ,b_{2k}]$. Назовем секционированием действие по изменению порядка последовательности. $\beta$ в разделенную перестановку. Это можно сделать за линейное время, сначала найдя медиану $b$ а затем перемещение элементов в первую или вторую половину в зависимости от того, меньше они или больше медианы.

Последовательность $\alpha '$ может быть получено путем разделения блоков элементов по позиции $[2k(i-1)+1,\dots ,2ki]$, затем разделив блоки элементов по позиции $[2k(i-1)+k+1,\dots ,2ki+k]$, а затем снова элементы в позиции $[2k(i-1)+1,\dots ,2ki]$ за каждый номер $i$ такие, что эти последовательности определены.

С использованием ${\frac {n}{2k}}$ процессоров, не имеющих общего доступа к памяти для чтения и записи, тот же алгоритм можно применить в $O(k)$ время, поскольку каждое разделение последовательности может происходить параллельно.

Объединение двух $k$-сортированные последовательности

Не путать с алгоритмом слияния k-way .

Объединение двух $k$-сортированные последовательности $\alpha ^{1}=[a_{1}^{1},\dots ,a_{n}^{1}]$ и $\alpha =[a_{1}^{2},\dots ,a_{m}^{2}]$ можно выполнить в линейном времени и постоянном пространстве.

Сначала с помощью предыдущего алгоритма обе последовательности следует преобразовать в $k/2$-сортированные последовательности.

Построим итеративно выходную последовательность $\omega$ удалив контент из обоих $\alpha ^{i}$ и добавив его в $\omega$.

Если оба $\alpha ^{i}$пусты, то достаточно вернуть $\omega$. В противном случае предположим, что $\alpha ^{1}$ пусто и нет $\alpha ^{2}$, достаточно удалить содержимое $\alpha ^{2}$ и добавьте его в $\omega$. Случай, когда $\alpha ^{2}$ пусто и нет $\alpha ^{1}$ подобен по симметрии.

Рассмотрим случай, когда ни $\alpha ^{i}$ пусто. Давайте позвоним $A^{1}=\max(a_{i}^{1}\mid 1\leq i\leq k/2)$ и $A^{2}=\max(a_{i}^{2}\mid 1\leq i\leq k/2)$, они величайшие из $k/2$-первыеэлементы каждого списка. Предположим, что $A^{1}<A^{2}$, другой случай аналогичен по симметрии. Удалять $a_{1}^{1},\dots ,a_{k/2}^{1}$ от $\alpha ^{1}$ и удалить $\{a_{j}^{2}\mid 1\leq j\leq k/2,a_{j}^{2}\leq A^{1}\}$ от $\alpha ^{2}$ и добавьте их в $\omega$.

Сортировка $k$-сортированная последовательность

А $k$-отсортированную последовательность можно отсортировать, применив приведенный выше алгоритм разделения пополам. $\log _{2}(k)$ раз. Это занимает $O(n\log k)$ время на последовательной машине или $O(k\log k)$ время использования $O(n)$ процессоры.

$k$-сортировка последовательности

Поскольку каждая последовательность $\alpha =[a_{1},\dots ,a_{n}]$ обязательно $n$-сортировано, достаточно применить алгоритм халвинга $\log _{2}\left({\frac {n}{k}}\right)$-раз. Таким образом, $k$- сортировка может быть выполнена в $O(n\log(n/k))$-время. Этот алгоритм является Par -оптимальным, то есть не существует последовательного алгоритма с лучшей сложностью в худшем случае.