Funnelsort

Funnelsort es un algoritmo de ordenación basado en comparaciones . Es similar a mergesort , pero es un algoritmo independiente de la caché , diseñado para entornos donde el número de elementos a ordenar es demasiado grande para caber en la caché donde se realizan las operaciones. Fue introducido por Matteo Frigo, Charles Leiserson , Harald Prokop y Sridhar Ramachandran en 1999 en el contexto del modelo independiente de la caché . ^[¹^]^[²^]

Propiedades matemáticas

En el modelo de memoria externa , el número de transferencias de memoria que necesita para realizar una especie de $N$ elementos en una máquina con caché de tamaño $Z$ y líneas de caché de longitud $L$ es $O\left({\tfrac {N}{L}}\log _{Z}N\right)$ , bajo el supuesto de caché alto que $Z=\Omega (L^{2})$ Se ha demostrado que este número de transferencias de memoria es asintóticamente óptimo para los algoritmos de ordenación por comparación. Funnelsort también alcanza la complejidad de tiempo de ejecución asintóticamente óptima de $\Theta (N\log N)$ .

Algoritmo

Descripción general básica

Funnelsort opera en una matriz contigua de $N$ elementos. Para ordenar los elementos, realiza lo siguiente:

Dividir la entrada en $N^{1/3}$ matrices de tamaño $N^{2/3}$ y ordenar los arreglos recursivamente.
Fusionar el $N^{1/3}$ secuencias ordenadas usando una $N^{1/3}$ -fusión. (Este proceso se describirá con más detalle).

El algoritmo Funnelsort es similar al Merge Sort en que ordena recursivamente varios subconjuntos, tras lo cual un paso de fusión los combina en un único arreglo ordenado. La fusión se realiza mediante un dispositivo llamado k-merger, que se describe en la sección siguiente.

k -fusiones

Una k -merge toma $k$ secuencias ordenadas. Tras una invocación de un k-merger, produce la primera $k^{3}$ elementos de la secuencia ordenada obtenida al fusionar las k secuencias de entrada.

En el nivel superior, Funnelsort utiliza un $N^{1/3}$ -fusión en $N^{1/3}$ secuencias de longitud $N^{2/3}$ y realiza esta fusión una sola vez.

La k -merger se construye recursivamente a partir de ${\sqrt {k}}$ -fusiones. Consiste en ${\sqrt {k}}$ aporte ${\sqrt {k}}$ -fusiones $I_{1},I_{2},\ldots ,I_{\sqrt {k}}$ y una única salida ${\sqrt {k}}$ -fusión $O$ . Las k entradas se separan en ${\sqrt {k}}$ conjuntos de ${\sqrt {k}}$ entradas cada uno. Cada uno de estos conjuntos es una entrada para uno de los fusionadores de entrada. La salida de cada fusionador de entrada está conectada a un búfer, una cola FIFO que puede contener $2k^{3/2}$ elementos. Los buffers se implementan como colas circulares . Las salidas de los ${\sqrt {k}}$ Los búferes están conectados a las entradas del combinador de salida. $O$ . Finalmente, la salida de $O$ es el resultado de toda la fusión k.

En esta construcción, cualquier fusión de entrada solo produce $k^{3/2}$ elementos a la vez, pero el búfer al que envía tiene el doble de espacio. Esto se hace para que un fusionador de entrada se pueda llamar solo cuando su búfer no tenga suficientes elementos, pero que cuando se llama, envíe muchos elementos a la vez (a saber, $k^{3/2}$ de ellos).

Un k -merger funciona recursivamente de la siguiente manera. Para generar $k^{3}$ elementos, invoca recursivamente su fusión de salida $k^{3/2}$ veces. Sin embargo, antes de que haga una llamada a $O$ , comprueba todos sus búferes, llenando cada uno de ellos que estén a menos de la mitad de su capacidad. Para llenar el i-ésimo búfer, invoca recursivamente la fusión de entrada correspondiente. $I_{i}$ una vez. Si esto no se puede hacer (debido a que la fusión se queda sin entradas), este paso se omite. Dado que esta llamada produce $k^{3/2}$ elementos, el búfer contiene al menos $k^{3/2}$ elementos. Al final de todas estas operaciones, el k -merger ha producido el primero $k^{3}$ de sus elementos de entrada, en orden ordenado.

Análisis

La mayor parte del análisis de este algoritmo gira en torno al análisis del espacio y la complejidad de los fallos de caché del algoritmo k-merger.

El primer límite importante es que una k-merger se puede ajustar en $O(k^{2})$ espacio. Para ver esto, dejamos $S(k)$ denota el espacio necesario para una k-fusión. Para ajustar el $k^{1/2}$ búferes de tamaño $2k^{3/2}$ acepta $O(k^{2})$ espacio. Para que quepa el ${\sqrt {k}}+1$ Los búferes más pequeños tardan $({\sqrt {k}}+1)S({\sqrt {k}})$ espacio. Por lo tanto, el espacio satisface la recurrencia. $S(k)=({\sqrt {k}}+1)S({\sqrt {k}})+O(k^{2})$ Esta recurrencia tiene solución. $S(k)=O(k^{2})$ .

De ello se deduce que existe una constante positiva. $\alpha$ de tal manera que un problema de tamaño como máximo $\alpha {\sqrt {Z}}$ Cabe completamente en la caché, lo que significa que no se producen fallos de caché adicionales.

Alquiler $Q_{M}(k)$ denotemos el número de fallos de caché incurridos por una llamada a un k-merger, se puede demostrar que $Q_{M}(k)=O((k^{3}\log _ {Z}k)/L).$ Esto se hace mediante un argumento de inducción. $k\leq \alpha {\sqrt {Z}}$ como caso base. Para k más grande, podemos acotar el número de veces que ${\sqrt {k}}$ -merger es llamado. El fusionador de salida es llamado exactamente $k^{3/2}$ veces. El número total de llamadas en fusiones de entrada es como máximo $k^{3/2}+2{\sqrt {k}}$ Esto da un límite total de $2k^{3/2}+2{\sqrt {k}}$ llamadas recursivas. Además, el algoritmo comprueba cada búfer para ver si necesita ser llenado. Esto se hace en ${\sqrt {k}}$ almacena en búfer cada paso para $k^{3/2}$ pasos, que conducen a un máximo de $k^{2}$ Fallos de caché para todas las comprobaciones.

Esto conduce a la recurrencia $Q_{M}(k)\leq (2k^{3/2}+2{\sqrt {k}})Q_{M}({\sqrt {k}})+k^{2}$ , que puede demostrarse que tiene la solución dada anteriormente.

Finalmente, el total de fallos de caché $Q(N)$ para todo el tipo se puede analizar. Satisface la recurrencia $Q(N)=N^{1/3}Q(N^{2/3})+Q_{M}(N^{1/3}).$ Se puede demostrar que esto tiene solución. $Q(N)=O((N/L)\log _{Z}N).$

Clasificación por embudo perezosa

Lazy funnelsort es una modificación del funnelsort, introducido por Gerth Stølting Brodal y Rolf Fagerberg en 2002. ^{[ 3 ]} La modificación consiste en que, al invocar una fusión, no es necesario llenar todos sus búferes. En cambio, llena un búfer de forma diferida solo cuando está vacío. Esta modificación tiene el mismo tiempo de ejecución asintótico y transferencias de memoria que el funnelsort original, pero tiene aplicaciones en algoritmos que no dependen de la caché para problemas de geometría computacional en un método conocido como barrido de distribución.

Véase también

Referencias

↑ M. Frigo, CE Leiserson, H. Prokop y S. Ramachandran. Algoritmos ajenos a la caché. En Actas del 40.º Simposio IEEE sobre Fundamentos de la Informática (FOCS 99), págs. 285-297. 1999. Resumen extendido en IEEE , en Citeseer .
↑ Harald Prokop. Algoritmos que ignoran la caché . Tesis de maestría, MIT. 1999.
↑ Brodal, Gerth Stølting ; Fagerberg, Rolf (25 de junio de 2002). "Cache Oblivious Distribution Sweeping". Autómatas, lenguajes y programación . Lecture Notes in Computer Science . Vol. 2380. Springer . págs. 426–438 . CiteSeerX 10.1.1.117.6837 . doi : 10.1007/3-540-45465-9_37 . ISBN 978-3-540-43864-9.Véase también el informe técnico más extenso .

[1] M. Frigo, CE Leiserson, H. Prokop y S. Ramachandran. Algoritmos ajenos a la caché. En Actas del 40.º Simposio IEEE sobre Fundamentos de la Informática (FOCS 99), págs. 285-297. 1999. Resumen extendido en IEEE , en Citeseer .

[2] Harald Prokop. Algoritmos que ignoran la caché . Tesis de maestría, MIT. 1999.

[3] Brodal, Gerth Stølting ; Fagerberg, Rolf (25 de junio de 2002). "Cache Oblivious Distribution Sweeping". Autómatas, lenguajes y programación . Lecture Notes in Computer Science . Vol. 2380. Springer . págs. 426–438 . CiteSeerX 10.1.1.117.6837 . doi : 10.1007/3-540-45465-9_37 . ISBN 978-3-540-43864-9.Véase también el informe técnico más extenso .

[

[

[ 3 ]