stringtranslate.com

Red de ordenación

Una red de clasificación simple que consta de cuatro cables y cinco conectores.

En informática , las redes de comparación son dispositivos abstractos formados por una cantidad fija de "cables" que transportan valores y módulos comparadores que conectan pares de cables, intercambiando los valores de los cables si no están en el orden deseado. Estas redes suelen estar diseñadas para realizar la clasificación de una cantidad fija de valores, en cuyo caso se denominan redes de clasificación .

Las redes de ordenamiento difieren de las ordenaciones de comparación generales en que no son capaces de manejar entradas arbitrariamente grandes y en que su secuencia de comparaciones se establece de antemano, independientemente del resultado de las comparaciones anteriores. Para ordenar cantidades mayores de entradas, se deben construir nuevas redes de ordenamiento. Esta independencia de las secuencias de comparación es útil para la ejecución paralela y para la implementación en hardware . A pesar de la simplicidad de las redes de ordenamiento, su teoría es sorprendentemente profunda y compleja. Las redes de ordenamiento fueron estudiadas por primera vez alrededor de 1954 por Armstrong, Nelson y O'Connor, [1] quienes posteriormente patentaron la idea. [2]

Las redes de ordenamiento pueden implementarse tanto en hardware como en software . Donald Knuth describe cómo los comparadores para números enteros binarios pueden implementarse como dispositivos electrónicos simples de tres estados. [1] Batcher , en 1968, sugirió usarlos para construir redes de conmutación para hardware de computadoras, reemplazando tanto los buses como los conmutadores de barra cruzada más rápidos, pero más costosos . [3] Desde la década de 2000, las redes de ordenamiento (especialmente el mergesort bitónico ) son utilizadas por la comunidad GPGPU para construir algoritmos de ordenamiento para ejecutar en unidades de procesamiento gráfico . [4]

Introducción

Demostración de un comparador en una red de clasificación.

Una red de clasificación consta de dos tipos de elementos: comparadores y cables. Se piensa que los cables van de izquierda a derecha y llevan valores (uno por cable) que recorren la red al mismo tiempo. Cada comparador conecta dos cables. Cuando un par de valores, que viajan a través de un par de cables, se encuentran con un comparador, este intercambia los valores si y solo si el valor del cable superior es mayor o igual que el valor del cable inferior.

En una fórmula, si el cable superior lleva x y el cable inferior lleva y , entonces, después de llegar a un comparador, los cables llevan y , respectivamente, por lo que el par de valores está ordenado. [5] : 635  Una red de cables y comparadores que ordenará correctamente todas las entradas posibles en orden ascendente se denomina red de clasificación o concentrador de Kruskal. Al reflejar la red, también es posible ordenar todas las entradas en orden descendente.

A continuación se muestra el funcionamiento completo de una red de clasificación simple. Es evidente por qué esta red de clasificación clasificará correctamente las entradas; observe que los primeros cuatro comparadores "hundirán" el valor más grande en la parte inferior y "harán flotar" el valor más pequeño en la parte superior. El comparador final clasifica los dos cables del medio.

Profundidad y eficiencia

La eficiencia de una red de ordenamiento se puede medir por su tamaño total, es decir, el número de comparadores en la red, o por su profundidad , definida (informalmente) como el mayor número de comparadores que cualquier valor de entrada puede encontrar en su camino a través de la red. Si se observa que las redes de ordenamiento pueden realizar ciertas comparaciones en paralelo (representadas en la notación gráfica por comparadores que se encuentran en la misma línea vertical), y se supone que todas las comparaciones toman una unidad de tiempo, se puede ver que la profundidad de la red es igual al número de pasos de tiempo necesarios para ejecutarla. [5] : 636–637 

Redes de inserción y de burbujas

Podemos construir fácilmente una red de cualquier tamaño recursivamente utilizando los principios de inserción y selección. Suponiendo que tenemos una red de ordenamiento de tamaño n , podemos construir una red de tamaño n + 1 "insertando" un número adicional en la subred ya ordenada (utilizando el principio subyacente al ordenamiento por inserción ). También podemos lograr lo mismo "seleccionando" primero el valor más bajo de las entradas y luego ordenando los valores restantes recursivamente (utilizando el principio subyacente al ordenamiento por burbuja ).

Una red de clasificación construida de forma recursiva que primero lleva el valor más grande al fondo y luego clasifica los cables restantes. Basada en la clasificación de burbuja

La estructura de estas dos redes de clasificación es muy similar. Una construcción de las dos variantes diferentes, que combina comparadores que pueden ejecutarse simultáneamente, muestra que, de hecho, son idénticas. [1]

La red de inserción (o equivalentemente, red de burbujas) tiene una profundidad de 2 n - 3 , [1] donde n es el número de valores. Esto es mejor que el tiempo O ( n log n ) que necesitan las máquinas de acceso aleatorio , pero resulta que hay redes de clasificación mucho más eficientes con una profundidad de solo O (log 2 n ) , como se describe a continuación.

Principio cero-uno

Si bien es fácil probar la validez de algunas redes de ordenamiento (como el clasificador de inserción/burbuja), no siempre es tan fácil. Hay n ! permutaciones de números en una red de n hilos, y probarlas todas llevaría una cantidad significativa de tiempo, especialmente cuando n es grande. La cantidad de casos de prueba se puede reducir significativamente, a 2 n , utilizando el llamado principio cero-uno. Si bien sigue siendo exponencial, es menor que n ! para todos los n ≥ 4 , y la diferencia crece bastante rápido con el aumento de n .

El principio cero-uno establece que, si una red de ordenamiento puede ordenar correctamente todas las 2 n secuencias de ceros y unos, entonces también es válida para entradas ordenadas arbitrariamente. Esto no solo reduce drásticamente la cantidad de pruebas necesarias para determinar la validez de una red, sino que también es de gran utilidad para crear muchas construcciones de redes de ordenamiento.

El principio puede demostrarse observando primero el siguiente hecho sobre los comparadores: cuando se aplica una función f monótonamente creciente a las entradas, es decir, x e y se reemplazan por f ( x ) y f ( y ) , entonces el comparador produce min( f ( x ), f ( y )) = f (min( x , y )) y max( f ( x ), f ( y )) = f (max( x , y )) . Por inducción en la profundidad de la red, este resultado puede extenderse a un lema que establece que si la red transforma la secuencia a 1 , ..., a n en b 1 , ..., b n , transformará f ( a 1 ), ..., f ( a n ) en f ( b 1 ), ..., f ( b n ) . Supóngase que alguna entrada a 1 , ..., a n contiene dos elementos a i < a j , y la red los intercambia incorrectamente en la salida. Entonces también ordenará incorrectamente f ( a 1 ), ..., f ( a n ) para la función

Esta función es monótona, por lo que tenemos el principio cero-uno como contrapositivo . [5] : 640–641 

Construcción de redes de clasificación

Existen varios algoritmos para construir redes de ordenamiento de profundidad O (log 2 n ) (por lo tanto, tamaño O ( n log 2 n ) ) como Batcher odd–even mergesort , bitonic sort , Shell sort y Pairwise sorting network . Estas redes se utilizan a menudo en la práctica.

También es posible construir redes de profundidad O (log n ) (por lo tanto tamaño O ( n log n ) ) utilizando una construcción llamada red AKS , en honor a sus descubridores Ajtai , Komlós y Szemerédi . [6] Si bien es un descubrimiento teórico importante, la red AKS tiene una aplicación práctica muy limitada debido a la gran constante lineal oculta por la notación Big-O . [5] : 653  Estos se deben en parte a la construcción de un gráfico expansor .

Paterson describió una versión simplificada de la red AKS en 1990 y señaló que "las constantes obtenidas para el límite de profundidad todavía impiden que la construcción tenga valor práctico". [7]

Goodrich descubrió en 2014 una construcción más reciente denominada red de clasificación en zigzag de tamaño O ( n log n ). [8] Si bien su tamaño es mucho menor que el de las redes AKS, su profundidad O ( n log n ) la hace inadecuada para una implementación paralela.

Redes de ordenamiento óptimo

Para un número pequeño y fijo de entradas n , se pueden construir redes de ordenamiento óptimas , ya sea con una profundidad mínima (para una ejecución máxima en paralelo) o con un tamaño mínimo (número de comparadores). Estas redes se pueden utilizar para aumentar el rendimiento de redes de ordenamiento más grandes resultantes de las construcciones recursivas de, por ejemplo, Batcher, deteniendo la recursión de forma temprana e insertando redes óptimas como casos base. [9] La siguiente tabla resume los resultados de optimalidad para redes pequeñas para las que se conoce la profundidad óptima:

En el caso de redes más grandes, no se conocen ni la profundidad ni el tamaño óptimos. Los límites conocidos hasta el momento se proporcionan en la siguiente tabla:

Las primeras dieciséis redes de profundidad óptima se enumeran en El arte de la programación informática de Knuth [1] y así han sido desde la edición de 1973; sin embargo, mientras que la optimalidad de las primeras ocho fue establecida por Floyd y Knuth en la década de 1960, esta propiedad no se demostró para las últimas seis hasta 2014 [15] (los casos nueve y diez se decidieron en 1991 [9] ).

Para una a doce entradas, se conocen redes de ordenamiento mínimas (es decir, de tamaño óptimo), y para valores más altos, los límites inferiores de sus tamaños S ( n ) se pueden derivar inductivamente utilizando un lema debido a Van Voorhis [1] (p. 240): S ( n ) ≥ S ( n − 1) + ⌈log 2 n . Las primeras diez redes óptimas se conocen desde 1969, y las primeras ocho se conocen nuevamente como óptimas desde el trabajo de Floyd y Knuth, pero la optimalidad de los casos n = 9 y n = 10 tardó hasta 2014 en resolverse. [11] La optimalidad de las redes de ordenamiento más pequeñas conocidas para n = 11 y n = 12 se resolvió en 2020. [16] [1]

Se han realizado algunos trabajos de diseño de redes de clasificación óptimas utilizando algoritmos genéticos : D. Knuth menciona que la red de clasificación más pequeña conocida para n = 13 fue encontrada por Hugues Juillé en 1995 "simulando un proceso evolutivo de crianza genética" [1] (p. 226), y que las redes de clasificación de profundidad mínima para n = 9 y n = 11 fueron encontradas por Loren Schwiebert en 2001 "utilizando métodos genéticos" [1] (p. 229).

Complejidad de las pruebas de redes de ordenación

A menos que P=NP , el problema de probar si una red candidata es una red de clasificación probablemente seguirá siendo difícil para redes de gran tamaño, debido a que el problema es co-NP -completo. [17]

Referencias

  1. ^ abcdefghi Knuth, DE (1997). El arte de la programación informática, volumen 3: Ordenación y búsqueda (segunda edición). Addison–Wesley. págs. 219–247. ISBN 978-0-201-89685-5.Sección 5.3.4: Redes de clasificación.
  2. ^ US 3029413, O'Connor, Daniel G. y Nelson, Raymond J., "Sistema de clasificación con interruptor de clasificación de n líneas", publicado el 10 de abril de 1962 
  3. ^ Batcher, KE (1968). Redes de ordenamiento y sus aplicaciones. Proc. Conferencia conjunta de informática de primavera de la AFIPS. págs. 307–314.
  4. ^ Owens, JD; Houston, M.; Luebke, D.; Green, S.; Stone, JE; Phillips, JC (2008). "Computación con GPU". Actas del IEEE . 96 (5): 879–899. doi :10.1109/JPROC.2008.917757. S2CID  17091128.
  5. ^ abcd Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
  6. ^ Ajtai, M. ; Komlós, J. ; Szemerédi, E. (1983). Una red de ordenamiento O(n log n) . STOC '83. Actas del decimoquinto simposio anual de la ACM sobre teoría de la computación . págs. 1–9. doi :10.1145/800061.808726. ISBN 0-89791-099-0.
  7. ^ Paterson, MS (1990). "Redes de ordenamiento mejoradas con profundidad O (log N ) ". Algorithmica . 5 (1–4): 75–92. doi :10.1007/BF01840378. S2CID  2064561.
  8. ^ Goodrich, Michael (marzo de 2014). "Zig-zag sort". Actas del cuadragésimo sexto simposio anual de la ACM sobre teoría de la computación . págs. 684–693. arXiv : 1403.2777 . doi :10.1145/2591796.2591830. ISBN . 9781450327107.S2CID 947950  .
  9. ^ ab Parberry, Ian (1991). "Un límite inferior de profundidad óptimo asistido por computadora para redes de ordenamiento de nueve entradas" (PDF) . Teoría de sistemas matemáticos . 24 : 101–116. CiteSeerX 10.1.1.712.219 . doi :10.1007/bf02090393. S2CID  7077160. 
  10. ^ abc Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Redes de ordenación: hasta el final y de regreso . arXiv : 1507.01428 . Código Bibliográfico :2015arXiv150701428C.
  11. ^ ab Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). Veinticinco comparadores son óptimos al ordenar nueve entradas (y veintinueve para diez) . Proc. Int'l Conf. Tools with AI (ICTAI). págs. 186–193. arXiv : 1405.5754 . Código Bibliográfico :2014arXiv1405.5754C.
  12. ^ ab Obtenido por el lema de Van Voorhis y el valor S (11) = 35
  13. ^ Ehlers, Thorsten (febrero de 2017). "La fusión de secuencias casi ordenadas produce un clasificador de 24". Information Processing Letters . 118 : 17–20. doi :10.1016/j.ipl.2016.08.005.
  14. ^ ab Dobbelaere, Bert. "ClasificadorHunter". GitHub . Consultado el 2 de enero de 2022 .
  15. ^ Bundala, D.; Závodný, J. (2014). "Redes de ordenamiento óptimo". Teoría y aplicaciones de lenguajes y autómatas . Apuntes de clase en informática. Vol. 8370. págs. 236–247. arXiv : 1310.6271 . doi :10.1007/978-3-319-04921-2_19. ISBN . 978-3-319-04920-5.S2CID16860013  .​
  16. ^ Harder, Jannis (2020). "Una respuesta al problema de ordenamiento de Bose-Nelson para 11 y 12 canales". arXiv : 2012.04400 [cs.DS].
  17. ^ Parberry, Ian (1991). Sobre la complejidad computacional de la verificación de redes de ordenamiento óptimo . Proc. PARLE '91: Parallel Architectures and Languages ​​Europe, Volumen I: Parallel Architectures and Algorithms, Eindhoven, Países Bajos . Págs. 252–269.

Enlaces externos