Estaba leyendo un poco sobre esto en línea y parece que depende mucho de las restricciones de su sistema y de la forma en que se formula el problema.
Por ejemplo, si tiene N números, ubicados en N máquinas, con cada máquina inicialmente con 1 número, y desea que la máquina k contenga el k número más pequeño para todas las k en [1..N]:
- Pregunte si una máquina puede, en cualquier momento, contener más de 1 número. (también conocido como preguntar sobre las restricciones de memoria de las máquinas) Si resulta que una máquina puede contener todos los números N, puede enviar todos los números a esa máquina, realizar una clasificación local y luego enviar a cada máquina su número correspondiente.
Entonces, sin embargo, puedes hacer otra pregunta. ¿Cuánto tiempo lleva transferir un número de una máquina a otra? Si este costo es alto, puede ignorar la solución anterior, incluso si hay máquinas en su sistema sin restricciones de memoria estrictas.
- ¿Qué es el código binario?
- ¿Existe un método o algoritmo matemático para expresar la suma de un número y un número multiplicado por un radical como la fórmula (a + b) ^ 3?
- ¿Qué algoritmo debo usar para codificar un solucionador de Sudoku usando la teoría de grafos?
- ¿Debería usar la función de clasificación () incorporada de C ++ para problemas en la programación competitiva, o debería implementar el algoritmo por mi cuenta?
- ¿Es posible elegir aleatoriamente un número de (0 a infinito), de modo que cada número tenga la misma probabilidad de ser elegido?
2. Si ninguna máquina puede contener más de 1 número a la vez, una solución directa es iterar a través de todos los pares (i, j) de máquinas y preguntar si el valor en la máquina i es mayor que el valor de la máquina j. Cuando la respuesta es sí, intercambie los dos valores. Continúe iterando mientras todavía haya al menos un par (i, j) que conduzca a un intercambio.
Este método de tipo burbuja puede extenderse al caso en que una máquina puede contener más de 1 número, pero no todos N, al mismo tiempo. Y, por supuesto, existen métodos más eficientes de clasificación rápida que existen.
Estas dos ‘soluciones’ más que nada ilustran que es difícil hablar de una solución general en sistemas distribuidos, ya que su solución terminará limitada por muchos factores: restricciones de memoria en las máquinas, latencia de red, ancho de banda, el formato de datos..
Aquí hay dos enlaces si desea leer más:
Página en disco.ethz.ch
Página en slu.edu
