La primera pregunta es difícil: encontrar el algoritmo de clasificación altamente paralelo más rápido, teóricamente, requiere una prueba matemática de que no hay una mejora asintótica posible.
La segunda pregunta es mucho más fácil: aunque existe una prueba de que no puede mejorar el resultado O (n log n) para un tipo de comparación, en el número de comparaciones, sí … puede distribuir esta carga de trabajo para mejorar el rendimiento.
Puede hacerlo sincronizando sus subprocesos para operar en diferentes partes de la misma memoria compartida, en épocas de cierta profundidad. Cada subproceso necesita solo una cantidad constante de memoria para el mantenimiento (saber qué índices comparar). La teoría aquí es la de una red de clasificación.
- ¿Qué se entiende por inversa modular de un número?
- ¿Qué matemáticas están involucradas en la base de datos?
- ¿Por qué 0.8 * 3 devuelve 2.4000000000000004 en lugar de 2.4?
- Bajo porcentaje (menos del 60%) en B.Tech Computer Science de una reputada universidad en India. ¿Cómo puedo obtener un trabajo de programación en empresas de primer nivel como Google, Facebook, Microsoft, etc.?
- ¿Es la informática teórica una subdisciplina de la lógica matemática? ¿Cuál es la diferencia entre los dos? ¿Dónde se cruzan?
Se sabe que varios enfoques proporcionan una profundidad (número de épocas) de “tiempo paralelo” (con hilos ilimitados) de [matemáticas] O ((log (n)) ^ 2) [/ matemáticas]. Por ejemplo, Batcher impar-incluso mergesort – Wikipedia y clasificador Bitonic – Wikipedia documentan dos de estos bien.
En la práctica, si no tiene los hilos (bueno, los núcleos), puede o no obtener una aceleración, con este tipo de enfoque. El número de comparaciones es [matemáticas] O (n (log (n)) ^ 2) [/ matemáticas]. En el peor de los casos, con 1 subproceso, esto aumenta el tiempo en un factor de log n.
