Clasificación paralela de algoritmos concurrentes

La mayoría de los algoritmos de clasificación se ejecutan en serie. Cuando hay muchos elementos de clasificación, el uso de un algoritmo de clasificación paralelo puede utilizar eficazmente la CPU y mejorar la eficiencia informática. Sin embargo, cambiar el algoritmo en serie a un algoritmo paralelo aumentará considerablemente la eficiencia. Complejidad del algoritmo original.

1. Correlación de datos separada: clasificación de intercambio par-impar

Clasificación de burbujas: si los datos son pequeños, se intercambiarán gradualmente hacia el frente. Para números grandes, se hundirán. y cambie al final de la matriz.

Durante cada iteración del proceso de intercambio, debido a conflictos de datos entre los dos elementos intercambiados cada vez, para cada elemento, se puede intercambiar con el elemento anterior o el siguiente, por lo que es difícil directamente cambiar a un algoritmo paralelo. Si puede desentrañar la correlación de estos datos, podrá utilizar algoritmos paralelos más fácilmente. La clasificación del intercambio de paridad se basa en esta idea.

Para la clasificación de intercambios pares e impares, divide el proceso de clasificación en dos etapas, intercambio impar e intercambio par. Un intercambio impar siempre compara índices impares y sus elementos sucesores adyacentes, mientras que un intercambio par siempre compara índices pares y sus elementos sucesores adyacentes. Y el intercambio impar y el intercambio par aparecerán en pares, para garantizar que la comparación y el intercambio involucren a todos los elementos de la matriz. Dentro de cada fase, todas las comparaciones e intercambios no dependen de datos y cada comparación e intercambio se puede realizar de forma independiente.

La bandera se usa para registrar el intercambio de datos que ocurrió durante el lanzamiento de la iteración actual, y el inicio se usa para indicar un intercambio par o impar. El inicio inicial = 0 significa un intercambio uniforme y el estado inicial se cambia al final de cada iteración. Si se produjo un intercambio de datos durante el último intercambio de comparación, o si actualmente hay un intercambio impar en curso, el ciclo no se detendrá hasta que no se produzcan más intercambios y haya un intercambio par en curso.

2. Ordenación por inserción mejorada: Ordenación en colina

Idea de ordenación por inserción: una matriz sin clasificar se puede dividir en dos partes, la primera mitad está ordenada y la segunda mitad no está ordenada, cuando ordenar, simplemente seleccione un elemento en la parte no ordenada e insértelo en la matriz previamente ordenada. Con el tiempo, las partes sin clasificar se vuelven cada vez menos hasta que la clasificación se completa en 0.

La ordenación por inserción es difícil de paralelizar porque la última inserción de datos depende de la última secuencia ordenada y no se pueden paralelizar varios pasos.

La clasificación Hill divide la matriz completa en varios subarreglos de acuerdo con el intervalo h. Los subarreglos se intercalan entre sí y cada subarreglo se clasifica por separado durante cada clasificación. Cada vez que se realiza la clasificación, siempre se intercambian dos elementos separados por h. Una vez completado cada grupo de clasificación, el valor de h se puede disminuir y se realiza la siguiente ronda de clasificación hasta h = 1, lo que equivale a una clasificación por inserción.

Ventajas de la clasificación Hill: incluso si un elemento más pequeño está al final de la matriz, dado que cada movimiento de elemento se realiza en un intervalo h, el elemento al final de la matriz se puede reemplazar al máximo con un número muy pequeño de intercambios Cerca de la posición final del elemento.

Transformado en clasificación Hill paralela:

--Referencia "Programación práctica de alta concurrencia de Java"