Un algoritmo extremadamente simple para esto (dado que asume que los datos en cada nodo están ordenados) es hacer una fusión n-way. Suponga que tiene una máquina cliente o puede elegir una de las máquinas para ser coordinador. Luego, si tiene un iterador sobre la lista ordenada de cada máquina, puede mantener una cola de prioridad mínima (montón) de cada uno de estos iteradores con el valor actual del iterador. En cada paso, haga estallar la parte superior del montón, extraiga el valor del iterador y escriba este número en la máquina que actualmente recibe escrituras (comenzando con 0, luego pasando a 1, 2, y así sucesivamente cuando complete el la cuota de números de la máquina actual para mantener), luego vuelva a insertar el iterador en el montón, ahora con la nueva clave del nuevo valor actual de ese iterador. Este proceso (suponiendo que sus lecturas de sus máquinas estén correctamente agrupadas y todas) requiere un paso sobre los datos con lecturas O (n) y requiere operaciones de CPU O (nlogm) donde m es el número de máquinas.
También notará que esto le brinda la capacidad de producir una secuencia ordenada de los conjuntos de datos combinados, no solo escribir los números en orden ordenado, por lo que si todo lo que desea es la capacidad de obtener los números en orden ordenado, no Ni siquiera necesito volver a escribirlos.
- ¿Cuál es la forma más eficiente de ordenar un millón de enteros de 32 bits?
- ¿Hay alguna diferencia en la asignación de memoria entre la estructura y la matriz multidimensional?
- ¿Dónde puedo encontrar un entrenador de programación personal que me enseñe programación y algoritmos?
- Cómo construir un algoritmo para operar
- ¿Cómo funciona un algoritmo de bogosort cuántico?
