Secuencia ordenada en K

En informática , una secuencia casi ordenada , también conocida como secuencia aproximadamente ordenada o secuencia as-sorted , es una secuencia que está casi ordenada. Por casi ordenada se entiende que ningún elemento de la secuencia está muy lejos de donde estaría si la secuencia estuviera perfectamente ordenada. Aún es posible que ningún elemento de la secuencia esté en el lugar donde debería estar si la secuencia estuviera perfectamente ordenada. ${\displaystyle k}$

Las secuencias casi ordenadas son particularmente útiles cuando el orden exacto de los elementos tiene poca importancia. Por ejemplo, Twitter ^[1] ordena los tweets casi al segundo, ya que no hay necesidad de mayor precisión. En realidad, dada la imposibilidad de sincronizar exactamente todos los ordenadores, es imposible ordenar exactamente todos los tweets según el momento en el que se publican. Esta idea llevó a la creación de los Snowflake IDs .

${\displaystyle k}$-sorting es la operación de reordenar los elementos de una secuencia para que quede -sorted. -sorting es generalmente más eficiente que sorting. De manera similar, ordenar una secuencia es más fácil si se sabe que la secuencia está -sorted. Por lo tanto, si un programa solo necesita considerar secuencias -sorted como entrada o salida, considerar secuencias -sorted puede ahorrar tiempo. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

El radio de una secuencia es una medida de preclasificación, es decir, su valor indica cuánto deben moverse los elementos de la lista para obtener un valor totalmente ordenado. En el ejemplo anterior de tweets que están ordenados hasta el segundo, el radio está limitado por la cantidad de tweets en un segundo.

Definición

Dado un número positivo , se dice que una secuencia está ordenada si para cada y para cada , . Es decir, la secuencia tiene que estar ordenada solo para pares de elementos cuya distancia sea al menos . ${\displaystyle k}$ ${\displaystyle [a_{1},\dots ,a_{n}]}$ ${\displaystyle k}$ ${\displaystyle 1\leq i}$ ${\displaystyle i+k\leq j\leq n}$ ${\displaystyle a_{i}\leq a_{j}}$ ${\displaystyle k}$

El radio de la secuencia , denotado ^[2] o ^[3], es el más pequeño de modo que la secuencia esté ordenada. El radio es una medida de preclasificación. ${\displaystyle \alpha }$ ${\displaystyle {\text{ROUGH}}(\alpha )}$ ${\displaystyle {\text{Par}}(\alpha )}$ ${\displaystyle k}$ ${\displaystyle k}$

Se dice que una secuencia está casi ordenada o aproximadamente ordenada si su radio es pequeño en comparación con su longitud.

Definición equivalente

Una secuencia está -ordenada si y solo si cada rango de longitud , está -ordenado. ${\displaystyle [a_{1},\dots ,a_{n}]}$ ${\displaystyle k}$ ${\displaystyle 2k+2}$ ${\displaystyle [a_{i},a_{i+1},\dots ,a_{i+2k+2}]}$ ${\displaystyle k}$

Propiedades

Todas las secuencias de longitud están ordenadas, es decir, . Una secuencia está ordenada si y solo si está ordenada. Una secuencia ordenada está ordenada automáticamente, pero no necesariamente ordenada. ${\displaystyle n}$ ${\displaystyle (n-1)}$ ${\displaystyle 0\leq {\text{Par}}([a_{1},\dots ,a_{n}])<n}$ ${\displaystyle 0}$ ${\displaystyle k}$ ${\displaystyle (k+1)}$ ${\displaystyle (k-1)}$

Relación con secuencias ordenadas

Dada una secuencia a -secuencia ordenada y su permutación ordenada , es como máximo . ${\displaystyle k}$ ${\displaystyle [a_{1},\dots ,a_{n}]}$ ${\displaystyle [a_{\sigma _{1}},\dots ,a_{\sigma _{n}}]}$ ${\displaystyle |i-\sigma _{i}|}$ ${\displaystyle k}$

Algoritmos

Decidir si una secuencia es a {\estilo de visualización k} -ordenado

La decisión sobre si una secuencia está ordenada se puede realizar en tiempo lineal y espacio constante mediante un algoritmo de streaming . Es suficiente, para cada , llevar un registro de y comprobar que . ${\displaystyle [a_{1},\dots ,a_{n}]}$ ${\displaystyle k}$ ${\displaystyle 1\leq i<n-k}$ ${\displaystyle \max(a_{j}\mid j\leq i)}$ ${\displaystyle a_{i+k}\geq \max(a_{j}\mid j\leq i)}$

Calcular el radio de una secuencia

El cálculo del radio de una sucesión se puede realizar en tiempo y espacio lineales. Esto se desprende del hecho de que se puede definir como . ${\displaystyle \max(i-j\mid \min(a_{k}\mid k\geq i)<\max(a_{k}\mid k\leq j))}$

Reducir a la mitad el radio de una secuencia

Dada una secuencia ordenada , es posible calcular una permutación ordenada de en tiempo lineal y espacio constante. ${\displaystyle 2k}$ ${\displaystyle \alpha =[a_{1},\dots ,a_{n}]}$ ${\displaystyle (k-1)}$ ${\displaystyle \alpha '}$ ${\displaystyle \alpha }$

En primer lugar, dada una secuencia , digamos que esta secuencia está particionada si los elementos -más pequeños están en y los elementos -más grandes están en . Llamemos partición a la acción de reordenar la secuencia en una permutación particionada. Esto se puede hacer en tiempo lineal encontrando primero la mediana de y luego moviendo los elementos a la primera o segunda mitad dependiendo de si son más pequeños o más grandes que la mediana. ${\displaystyle \beta =[b_{1},\dots ,b_{2k}]}$ ${\displaystyle k}$ ${\displaystyle [b_{1},\dots ,b_{k}]}$ ${\displaystyle k}$ ${\displaystyle [b_{k+1},\dots ,b_{2k}]}$ ${\displaystyle \beta }$ ${\displaystyle b}$

La secuencia se puede obtener dividiendo los bloques de elementos en la posición , luego dividiendo los bloques de elementos en la posición , y luego nuevamente los elementos en la posición para cada número de manera que dichas secuencias estén definidas. ${\displaystyle \alpha '}$ ${\displaystyle [2k(i-1)+1,\dots ,2ki]}$ ${\displaystyle [2k(i-1)+k+1,\dots ,2ki+k]}$ ${\displaystyle [2k(i-1)+1,\dots ,2ki]}$ ${\displaystyle i}$

Utilizando procesadores, sin acceso compartido de lectura ni escritura a la memoria, se puede aplicar el mismo algoritmo en el tiempo, ya que cada partición de una secuencia puede ocurrir en paralelo. ${\displaystyle {\frac {n}{2k}}}$ ${\displaystyle O(k)}$

Fusionando dos k {\displaystyle k} -secuencias ordenadas

La fusión de dos secuencias ordenadas se puede realizar en tiempo lineal y en espacio constante. ${\displaystyle k}$ ${\displaystyle \alpha ^{1}=[a_{1}^{1},\dots ,a_{n}^{1}]}$ ${\displaystyle \alpha =[a_{1}^{2},\dots ,a_{m}^{2}]}$

En primer lugar, utilizando el algoritmo anterior, ambas secuencias deben transformarse en secuencias ordenadas. ${\displaystyle k/2}$

Construyamos iterativamente una secuencia de salida eliminando contenido de ambos y agregándolo en . ${\displaystyle \omega }$ ${\displaystyle \alpha ^{i}}$ ${\displaystyle \omega }$

Si ambos están vacíos, basta con devolver . En caso contrario, supongamos que está vacío y no , basta con quitar el contenido de y anexarlo a . El caso en el que está vacío y no es similar por simetría. ${\displaystyle \alpha ^{i}}$ ${\displaystyle \omega }$ ${\displaystyle \alpha ^{1}}$ ${\displaystyle \alpha ^{2}}$ ${\displaystyle \alpha ^{2}}$ ${\displaystyle \omega }$ ${\displaystyle \alpha ^{2}}$ ${\displaystyle \alpha ^{1}}$

Consideremos el caso en el que ninguno está vacío. Llamemos a y , que son los mayores de los primeros elementos de cada lista. Supongamos que , el otro caso es similar por simetría. Elimínelos de y elimínelos de y añádalos a . ${\displaystyle \alpha ^{i}}$ ${\displaystyle A^{1}=\max(a_{i}^{1}\mid 1\leq i\leq k/2)}$ ${\displaystyle A^{2}=\max(a_{i}^{2}\mid 1\leq i\leq k/2)}$ ${\displaystyle k/2}$ ${\displaystyle A^{1}<A^{2}}$ ${\displaystyle a_{1}^{1},\dots ,a_{k/2}^{1}}$ ${\displaystyle \alpha ^{1}}$ ${\displaystyle \{a_{j}^{2}\mid 1\leq j\leq k/2,a_{j}^{2}\leq A^{1}\}}$ ${\displaystyle \alpha ^{2}}$ ${\displaystyle \omega }$

Ordenando una k {\displaystyle k} -secuencia ordenada

Una secuencia ordenada se puede ordenar aplicando el algoritmo de división por la mitad indicado anteriormente . Esto lleva tiempo en una máquina secuencial o en procesadores. ${\displaystyle k}$ ${\displaystyle \log _{2}(k)}$ ${\displaystyle O(n\log k)}$ ${\displaystyle O(k\log k)}$ ${\displaystyle O(n)}$

k {\displaystyle k} -ordenar una secuencia

Como cada secuencia está necesariamente ordenada, basta con aplicar el algoritmo de reducción a la mitad varias veces. De este modo, la ordenación se puede realizar en tiempo. Este algoritmo es paróptimo, es decir, no existe ningún algoritmo secuencial con una mejor complejidad en el peor de los casos. ${\displaystyle \alpha =[a_{1},\dots ,a_{n}]}$ ${\displaystyle n}$ ${\displaystyle \log _{2}\left({\frac {n}{k}}\right)}$ ${\displaystyle k}$ ${\displaystyle O(n\log(n/k))}$

Referencias

1. @rk. "Anunciando Snowflake". Blog de Twitter . Consultado el 26 de abril de 2021 .
2. Altman, Tom; Igarashi, Yoshihide (25 de agosto de 1989). "Ordenación aproximada: enfoque secuencial y paralelo". Revista de procesamiento de la información . 12 (2): 154–158.
3. Estivill-Castro, Vladimir; Wood, Derick (octubre de 1989). "Una nueva medida de preclasificación". Información y computación . 83 (1): 111–119. doi : 10.1016/0890-5401(89)90050-3 .