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]
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.
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
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 ).
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.
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
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.
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).
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]
