algorithm distributed-computing

algorithm - Calcule la mediana de mil millones de números



distributed-computing (25)

  1. Divide the 1 billion numbers into 100 machines. Each machine will have 10^7 numbers.

  2. For each incoming number to a machine, store the number in a frequency map, number -> count. Also store the min number in each machine.

  3. Find median in each machine: starting from min number in each machine, sum the counts until median index is reached. The median in each machine, will be the approx. lesser and greater than 5*10^6 numbers.

  4. Find median of all medians, which will be lesser and greater than approx. 50*10^7 numbers, which is the median of 1 billion numbers.

Now some optimization of 2nd step: Instead of storing in a frequency map, store the counts in a variable bit array. For example: Lets say starting from min number in a machine, these are frequency counts:

[min number] - 8 count [min+1 number] - 7 count [min+2 number] - 5 count

The above can be stored in bit array as:

[min number] - 10000000 [min+1 number] - 1000000 [min+2 number] - 10000

Note that altogether it will cost about 10^7 bits for each machine, since each machine only handles 10^7 numbers. 10^7bits = 1.25*10^6 bytes, which is 1.25MB

So with the above approach each machine will need 1.25MB of space to compute local median. And median of medians can be computed from those 100 local medians, resulting in median of 1 billion numbers.

Si tiene mil millones de números y cien computadoras, ¿cuál es la mejor manera de localizar la mediana de estos números?

Una solución que tengo es:

  • Divida el conjunto por igual entre las computadoras.
  • Ordenarlos
  • Encuentra las medianas para cada conjunto.
  • Ordena los conjuntos en las medianas.
  • Fusiona dos conjuntos a la vez desde la mediana más baja a la más alta.

Si tenemos m1 < m2 < m3 ... luego Set2 Set1 y Set2 y en el conjunto resultante podemos descartar todos los números inferiores a la mediana de Set12 (fusionados). Entonces, en cualquier punto del tiempo, tenemos conjuntos de igual tamaño. Por cierto, esto no se puede hacer de forma paralela. ¿Algunas ideas?

Ah, mi cerebro acaba de poner en marcha, tengo una sugerencia sensata ahora. Probablemente sea demasiado tarde si esto hubiera sido una entrevista, pero no importa:

La máquina 1 se denominará "máquina de control" y, por razones de argumento, comienza con todos los datos y los envía en parcelas iguales a las otras 99 máquinas, de lo contrario, los datos se distribuyen uniformemente entre las máquinas, y envía 1/99 de sus datos a cada uno de los otros. Las particiones no tienen que ser iguales, solo cerca.

Cada otra máquina ordena sus datos, y lo hace de una manera que favorece la búsqueda de los valores más bajos primero. Entonces, por ejemplo, un quicksort, siempre clasificando la parte inferior de la partición primero [*]. Escribe sus datos de vuelta a la máquina de control en orden creciente tan pronto como puede (usando IO asincrónico para continuar ordenando, y probablemente con Nagle activado: experimentar un poco).

La máquina de control realiza una fusión de 99 vías en los datos a medida que llega, pero descarta los datos fusionados, solo manteniendo el recuento de la cantidad de valores que ha visto. Calcula la mediana como la media de la 1/2 billonésima y la mitad de los valores oneth.

Esto sufre del problema "más lento en el rebaño". El algoritmo no puede completarse hasta que cada valor menor que la mediana haya sido enviado por una máquina clasificadora. Hay una posibilidad razonable de que uno de esos valores sea bastante alto dentro de su paquete de datos. Una vez que se completa la partición inicial de los datos, el tiempo estimado de ejecución es la combinación del tiempo para ordenar 1/99 de los datos y enviarlos nuevamente a la computadora de control, y el tiempo para que el control lea 1/2 de los datos . La "combinación" está en algún punto entre el máximo y la suma de esos tiempos, probablemente cerca del máximo.

Mi instinto es que para enviar datos a través de una red es más rápido que ordenarlos (y mucho menos simplemente seleccionar la mediana), debe ser una red bastante rápida. Podría ser una mejor perspectiva si se puede suponer que la red es instantánea, por ejemplo, si tiene 100 núcleos con igual acceso a la RAM que contiene los datos.

Dado que es probable que la E / S de red sea el límite, es posible que haya algunos trucos que pueda jugar, al menos para que los datos vuelvan a la máquina de control. Por ejemplo, en lugar de enviar "1,2,3, .. 100", quizás una máquina clasificadora podría enviar un mensaje que significa "100 valores menores que 101". La máquina de control podría entonces realizar una fusión modificada, en la que encuentra el menor de todos esos valores de rango superior, luego le dice a todas las máquinas clasificadoras cuál era, para que puedan (a) decirle a la máquina de control cómo muchos valores para "contar" por debajo de ese valor, y (b) reanudar el envío de sus datos ordenados desde ese punto.

En términos más generales, es probable que exista un ingenioso juego de adivinación de desafío-respuesta que la máquina de control pueda jugar con las 99 máquinas clasificadoras.

Esto implica viajes de ida y vuelta entre las máquinas, lo que evita mi primera versión más simple. Realmente no sé cómo calcular a ciegas su rendimiento relativo, y dado que las concesiones son complejas, me imagino que hay soluciones mucho mejores que cualquier otra cosa en la que pueda pensar, suponiendo que esto sea un problema real.

[*] disponibilidad de pila disponible: tu elección de qué parte hacer primero está limitada si no tienes O (N) espacio extra. Pero si tiene suficiente espacio extra, puede escoger, y si no tiene suficiente espacio, al menos puede usar lo que necesita para cortar algunas esquinas, haciendo la parte pequeña primero para las primeras particiones.

Depende de tus datos. El peor de los casos es que se trata de números distribuidos uniformemente.

En este caso, puede encontrar la mediana en el tiempo O (N) como en este ejemplo:

Suponga que sus números son 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (el rango es 1-10) .

Creamos 3 cubos: 1-3, 4-7, 8-10. Tenga en cuenta que la parte superior e inferior tienen el mismo tamaño.

Llenamos los cubos con los números, contamos cuántos caen en cada uno, el máximo y el mínimo

  • bajo (5): 2,1,1,3,3, min 1, max 3
  • medio (10): 7,5,6,4,4,6,4,7,4,4, min 4, max 7
  • alto (5): 10, 10, 8, 9, 9, min 8, max 10

El promedio cae en el cubo del medio, ignoramos el resto

Creamos 3 cubos: 4, 5-6, 7. Bajo comenzará con un conteo de 5 y con un máximo de 3 y alto con un mínimo de 8 y un recuento de 5.

Para cada número, contamos cuántos caen en el cubo bajo y alto, el máximo y el mínimo, y mantienen el cubo medio.

  • viejo bajo (5)
  • bajo (5): 4, 4, 4, 4, 4, máximo 4
  • medio (3): 5,6,6
  • alto (2): 7, 7, min 7
  • viejo alto (5)

Ahora podemos calcular la mediana directamente: tenemos una situación como esta

old low low middle high old high x x x x x 4 4 4 4 4 4 5 6 6 7 7 x x x x x

entonces la mediana es 4.5.

Suponiendo que sepa un poco sobre la distribución, puede ajustar cómo definir los rangos para optimizar la velocidad. En cualquier caso, el rendimiento debería ir con O (N), porque 1 + 1/3 + 1/9 ... = 1.5

Se necesitan mín. Y máx. Debido a casos extremos (p. Ej., Si la mediana es el promedio entre el mínimo máximo de edad bajo y el siguiente elemento).

Todas estas operaciones se pueden paralelizar, puede dar 1/100 de los datos a cada computadora y calcular los 3 cubos en cada nodo, luego distribuir la cubeta que conserva. De nuevo, esto hace que use la red de manera eficiente porque cada número se pasa en promedio 1.5 veces (entonces O (N)). Incluso puede vencer eso si solo pasa los números mínimos entre los nodos (por ejemplo, si el nodo 1 tiene 100 números y el nodo 2 tiene 150 números, entonces el nodo 2 puede dar 25 números al nodo 1).

A menos que sepa más sobre la distribución, dudo que pueda hacer mejor que O (N) aquí, porque realmente necesita contar los elementos al menos una vez.

Divida los 10 ^ 9 números, 10 ^ 7 en cada computadora ~ 80MB en cada uno. Cada computadora ordena sus números. Luego, la computadora 1 se fusiona -ordena sus propios números con los de la computadora 2, la computadora 3 y 4, etc ... Luego la computadora 1 escribe la mitad de los números de nuevo en 2, 3 a 4, etc. Luego, 1 combinación ordena los números de las computadoras 1,2,3,4, los escribe de nuevo. Y así. Dependiendo del tamaño de la RAM en las computadoras, puede salirse con la suya si no escribe todos los números en las computadoras individuales en cada paso, puede acumular los números en la computadora 1 para varios pasos, pero usted hace los cálculos.

Oh, finalmente obtener la media de los valores 500000000th y 500000001st (pero compruebe que hay suficientes 00s allí, no los tengo).

EDITAR: @Roman - bueno, si no puedes creerlo, incluso si es cierto, no tiene sentido que revele la verdad o la falsedad de la proposición. Lo que quería decir es que la fuerza bruta a veces supera a los inteligentes en una carrera. Me tomó alrededor de 15 segundos diseñar un algoritmo que estoy seguro de que puedo implementar, que funcionará, y que será adaptable a una amplia gama de tamaños de entradas y números de computadoras, y ajustable a las características de las computadoras y arreglos de redes. Si te lleva a ti, oa alguien más, decir 15 minutos para diseñar un algoritmo más sofisticado, tengo una ventaja de 14m45 para codificar mi solución y comenzar a ejecutarla.

Pero admito abiertamente que esto es toda afirmación, no he medido nada.

Esto podría hacerse en los nodos utilizando datos que no están ordenados en los nodos (por ejemplo, desde los archivos de registro) de la siguiente manera.

Hay 1 nodo padre y 99 nodos secundarios. Los nodos secundarios tienen dos llamadas de API:

  • stats (): devuelve min, max y count
  • compare (median_guess): devuelve el valor de concordancia, cuenta menos que el valor y cuenta más que el valor

El nodo padre llama a stats () en todos los nodos secundarios, anotando el mínimo y el máximo de todos los nodos.

Ahora se puede realizar una búsqueda binaria de la siguiente manera:

  1. Biseque el redondeo mínimo y máximo hacia abajo: esta es la mediana ''conjetura''
  2. Si el mayor que el recuento es más que el conteo menor, establezca el mínimo para la conjetura
  3. Si el mayor que el recuento es menor que el conteo menor, establezca el máximo para la conjetura
  4. Si el recuento es impar finaliza cuando el mínimo y el máximo son iguales
  5. Si el recuento finaliza cuando el máximo es <= mínimo + guess.match_count Esto se puede hacer en los nodos que utilizan datos no ordenados (por ejemplo, desde los archivos de registro) de la siguiente manera.

Hay 1 nodo padre y 99 nodos secundarios. Los nodos secundarios tienen dos llamadas de API:

  • stats (): devuelve min, max y count
  • compare (median_guess): devuelve el valor de concordancia, cuenta menos que el valor y cuenta más que el valor

El nodo padre llama a stats () en todos los nodos secundarios, anotando el mínimo y el máximo de todos los nodos.

A binary search may now be conducted in the following way:

  1. Bisect the minimum and maximum rounding down - this is the median ''guess''
  2. If the greater than count is more than the less than count, set the minimum to the guess
  3. If the greater than count is less than the less than count, set the maximum to the guess
  4. If count is odd finish when minimum and maximum are equal
  5. If count is even finish when maximum <= minimum + guess.match_count

If the stats() and compare() could be pre-calculated with a O(N/Mlogn/M) sort, then a O(N/M) pre-calculation with a memory complexity of O(N) for the pre-calculation. Then you could do compare() in constant time, so the whole thing (including pre-calculation) would run in O(N/MlogN/M)+O(logN)

Let me know if I have made a mistake!

Esto podría sorprender a la gente, pero si los números son enteros lo suficientemente pequeños como para caber dentro de 32 bits (o más pequeños): ¡simplemente haz una clasificación de cubo! Solo necesita 16 GB de memoria RAM para cualquier cantidad de entradas y salidas de 32 bits en O (n), lo que debería superar a cualquier sistema distribuido por n razonable, por ejemplo, mil millones.

Una vez que tenga la lista ordenada, es trivial elegir la mediana. De hecho, no es necesario construir la lista ordenada, pero basta con mirar los cubos para hacerlo.

Una implementación simple se muestra a continuación. Solo funciona para enteros de 16 bits, pero la extensión a 32 bits debería ser fácil.

#include <stdio.h> #include <string.h> int main() { unsigned short buckets[65536]; int input, n=0, count=0, i; // calculate buckets memset(buckets, 0, sizeof(buckets)); while (scanf("%d", &input) != EOF) { buckets[input & 0xffff]++; n++; } // find median while (count <= n/2) { count += buckets[i++]; } printf("median: %d/n", i-1); return 0; }

Usar un archivo de texto con mil millones (10 9 ) números y ejecutar con el time como tal

time ./median < billion

produce un tiempo de ejecución en mi máquina 1m49.293s. La mayor parte del tiempo de ejecución es probablemente también disco IO.

Esto se puede hacer más rápido que el algoritmo votado (n log n)

- Algoritmo de selección distribuida de estadísticas de pedido - O (n)
Simplifique el problema con el problema original de encontrar el número k en una matriz no ordenada.
- Cuenta de ordenación del histograma O (n)
Debe asumir algunas propiedades sobre el rango de los números: ¿puede el rango encajar en la memoria? - Tipo de fusión externa - O (n log n) - descrito anteriormente
Básicamente clasifica los números en la primera pasada, luego encuentra la mediana en la segunda.
- Si se sabe algo sobre la distribución de los números, se pueden producir otros algoritmos.

Para más detalles e implementación ver:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

La estimación de las estadísticas de orden, como la mediana y el percentil 99, se puede distribuir de manera eficiente con algoritmos como t-digest o Q-digest .

Usando cualquiera de los algoritmos, cada nodo produce un resumen, que representa la distribución de los valores almacenados localmente. Los compendios se recopilan en un solo nodo, se fusionan (de hecho, se suman las distribuciones) y se puede buscar la mediana o cualquier otro percentil.

Este enfoque es utilizado por elasticsearch y, presumiblemente, BigQuery (siguiendo la descripción de la función QUANTILES).

La mediana para este conjunto de números

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89, 97

es 67.

La mediana para este conjunto de números

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89

es 40.

Suponiendo que la pregunta fuera aproximadamente 1,000,000,000 enteros (x) donde 0> = x <= 2,147,483,647 y que el OP estaba buscando (elemento (499,999,999) + elemento (500,000,000)) / 2 (si los números fueron ordenados). También asumiendo que las 100 computadoras eran todas iguales.

usando mi computadora portátil y GigE ...

Lo que encontré fue que mi computadora portátil puede ordenar 10.000,000 Int32 en 1.3 segundos. Así que una estimación aproximada sería que un número de mil millones tomaría 100 x 1.3 segundos (2 minutos y 10 segundos);).

Una estimación de una transferencia de archivos unidireccional de un archivo de 40MB en un gigabit Ethernet es .32 segundos. Esto significa que los resultados ordenados de todas las computadoras se devolverán en aproximadamente 32 segundos (la computadora 99 no obtuvo su archivo hasta 30 segundos después del inicio). A partir de ahí no debería tomar mucho tiempo para descartar los números más bajos 499,999,998, agregar los siguientes 2 y dividir por 2.

Lo haría así:

in the beginning all 100 work to find the highest and the lowest number; each of the computer has his part of the database/file which it queries;

when the highest and lowest numbers are found, one computer reads the data, and distributes each number, evenly, to the rest of the 99; the numbers are distributed by equal intervals; (one may take from -100 million to 0, another - from 0 to 100 million, etc);

While receiving numbers, each of the 99 of the computers already sorts them;

Then, it''s easy to find the median... See how many numbers has each computer, add all of them (the sum of how many numbers there are, not the numbers themselves), divide by 2; calculate in which computer is the number, and at which index;

:) voilla

PS Seems there''s a lot of confusion here; the MEDIAN - is the NUMBER IN THE MIDDLE OF A SORTED LIST OF NUMBERS!

Mil millones es en realidad una tarea bastante aburrida para una computadora moderna. Estamos hablando de 4 GB de enteros de 4 bytes aquí ... 4 GB ... esa es la memoria RAM de algunos teléfonos inteligentes.

public class Median { public static void main(String[] args) { long start = System.currentTimeMillis(); int[] numbers = new int[1_000_000_000]; System.out.println("created array after " + (System.currentTimeMillis() - start) + " ms"); Random rand = new Random(); for (int i = 0; i < numbers.length; i++) { numbers[i] = rand.nextInt(); } System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms"); Arrays.sort(numbers); System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms"); if (numbers.length % 2 == 1) { System.out.println("median = " + numbers[numbers.length / 2 - 1]); } else { int m1 = numbers[numbers.length / 2 - 1]; int m2 = numbers[numbers.length / 2]; double m = ((long) m1 + m2) / 2.0; System.out.println("median = " + new DecimalFormat("#.#").format(m)); } }

Salida en mi máquina:

created array after 518 ms initialized array after 10177 ms sorted array after 102936 ms median = 19196

Así que esto se completa en mi máquina en menos de dos minutos (1:43 de los cuales 0:10 son para generar números aleatorios) usando un solo núcleo e incluso está haciendo una clasificación completa. Nada elegante realmente.

Esta seguramente es una tarea interesante para grupos más grandes de números. Solo quiero hacer un punto aquí: mil millones son cacahuetes. Así que piénselo dos veces antes de comenzar a lanzar soluciones complejas en tareas sorprendentemente simples;)

Odio ser el contrario aquí, pero no creo que se requiera la clasificación, y creo que cualquier algoritmo que implique clasificar un billón / 100 números va a ser lento. Consideremos un algoritmo en una computadora.

1) Seleccione 1000 valores al azar de los mil millones, y úselos para tener una idea de la distribución de los números, especialmente un rango.

2) En lugar de ordenar los valores, distribúyalos en categorías según la distribución que acaba de calcular. Se elige la cantidad de cubetas para que la computadora pueda manejarlas de manera eficiente, pero de lo contrario debería ser tan grande como sea conveniente. Los rangos del cubo deben ser de modo que aproximadamente el mismo número de valores entre en cada segmento (esto no es crítico para el algoritmo, pero ayuda a la eficiencia. Es posible que sean adecuados 100.000 cubos). Tenga en cuenta la cantidad de valores en cada segmento. Este es un proceso O (n).

3) Averigua en qué rango del cubo se encuentra la mediana. Esto se puede hacer simplemente examinando los números totales en cada segmento.

4) Encuentra la mediana real examinando los valores en ese cubo. Aquí puede usar un orden si lo desea, ya que solo está ordenando quizás 10,000 números. Si la cantidad de valores en ese depósito es grande, entonces puede usar este algoritmo nuevamente hasta que tenga un número lo suficientemente pequeño como para ordenarlo.

Este enfoque se paraleliza trivialmente al dividir los valores entre las computadoras. Cada computadora informa los totales en cada cubo a una computadora de "control" que realiza el paso 3. Para el paso 4, cada computadora envía los valores (ordenados) en el contenedor relevante a la computadora de control (también puede hacer esos dos algoritmos en paralelo, pero probablemente no valga la pena).

El proceso total es O (n), ya que los pasos 3 y 4 son triviales, siempre que la cantidad de cubos sea lo suficientemente grande.

Por extraño que parezca, creo que si tienes suficientes computadoras, es mejor ordenarlas que usar O(n) algoritmos de búsqueda de mediana. (A menos que sus núcleos sean muy, muy lentos, solo usaría uno y usaría un algoritmo de búsqueda de mediana de O(n) para meramente 1e9 números; si tuviera 1e12, eso podría ser menos práctico).

De todos modos, supongamos que tenemos más que log n cores para tratar este problema, y ​​no nos importa el consumo de energía, solo obtener la respuesta rápidamente. Supongamos además que se trata de una máquina SMP con todos los datos ya cargados en la memoria. (Las máquinas de 32 núcleos de Sun son de este tipo, por ejemplo).

Un hilo corta la lista ciegamente en trozos de igual tamaño y le dice a los otros hilos M que los clasifiquen. Esos hilos lo hacen diligentemente, en (n/M) log (n/M) tiempo. Luego devuelven no solo sus medianas, sino también sus percentiles 25 y 75 (los peores casos perversos son mejores si eliges números ligeramente diferentes). Ahora tiene rangos de 4M de datos. Luego ordena estos rangos y trabaja hacia arriba en la lista hasta que encuentre un número tal que, si arroja cada rango que es más pequeño que o contiene el número, habrá arrojado la mitad de sus datos. Ese es tu límite inferior para la mediana. Haz lo mismo para el límite superior. Esto lleva algo así como M log M time, y todos los núcleos tienen que esperar, por lo que realmente está desperdiciando M^2 log M tiempo potencial. Ahora tiene su único hilo y le dice a los demás que arrojen todos los datos fuera del rango (debe tirar aproximadamente la mitad en cada pasada) y repita: esta es una operación trivialmente rápida ya que los datos ya están ordenados. No debería tener que repetir esto más que log(n/M) veces antes de que sea más rápido simplemente tomar los datos restantes y usar un buscador mediano estándar de O(n) .

Entonces, la complejidad total es algo así como O((n/M) log (n/M) + M^2 log M log (n/M)) . Por lo tanto, esto es más rápido que la ordenación mediana O(n) en un núcleo si M >> log(n/M) y M^3 log M < n , que es cierto para el escenario que ha descrito.

Creo que esta es una muy mala idea dado lo ineficiente que es, pero es más rápido.

Una computadora es más que suficiente para resolver el problema.

Pero supongamos que hay 100 computadoras. Lo único complejo que debes hacer es ordenar la lista. Dividirlo en 100 partes, enviar una parte a cada computadora, dejar que se clasifiquen allí y fusionar las partes después de eso.

Luego tome el número del medio de la lista ordenada (es decir, con un índice de 5 000 000 000).

An easier method is to have weighted numbers.

  • Split the large set among computers
  • Sort each set
  • iterate through the small-set, and calculate weights to repeated elements
  • merge each 2 sets into 1 (each is sorted already) updating weights
  • keep merging sets until you get only one set
  • iterate through this set accumulating weights until you reach OneBillion/2

How about this:- each node can take 1Billion/100 numbers. At each node the elements can be sorted and median can be found. Find the median of medians. we can, by aggregating the counts of numbers less than median-of-median on all nodes find out x%:y% split which the median-of-medians makes. Now ask all nodes to delete elements less than the median of medians( taking example of 30%:70% split).30% numbers are deleted. 70% of 1Billion is 700million. Now all nodes which deleted less than 3million nodes can send those extra nodes back to a main computer. The main computer redistributes in such a way that now all nodes will have almost equal number of nodes(7million). Now that the problem is reduced to 700million numbers.... goes on until we have a smaller set which can be computed on one comp.

I suggest a method to calculate approximately the Median. :) If these one billion numbers are in a randomly order, I think I can pick 1/100 or 1/10 of one billion number randomly, sort them with 100 machine, then pick the median of them. Or let''s split billion numbers in 100 parts, let each machine pick 1/10 of each part randomly, calculate the median of them. After that we have 100 numbers and we can calculate the median of the 100 number easier. Just a suggestion, I''m not sure if it''s mathematically correct. But I think you can show the result to a not-so-good-at-math manager.

I think Steve Jessop''s answer will be the fastest.

If the network data transfer size is the bottleneck, here is another approach.

Divide the numbers into 100 computers (10 MB each). Loop until we have one element in each list Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median. Send the medians to a central computer and find the median of medians. Then send the median back to each computer. For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part. When we have one number in each list, send them to the central computer and find and return the median.

If the numbers are not distinct, and only belong to a certain range, that is they are repeated, then a simple solution that comes to my mind is to distribute the numbers among 99 machines equally, and keep one machine as the master. Now every machine iterates over its given numbers, and stores the count of each number in a hash set. Each time the number gets repeated in the set of numbers allotted to that particular computer, it updates its count in the hash set.

All the machines then return their hash set to the master machine. The master machine combines the hash sets, summing the count of the same key found in a hash set. For example machine#1''s hash set had an entry of ("1",7), and machine#2''s hash set had an entry of ("1",9), so the master machine when combing the hash sets makes an entry of ("1", 16), and so on.

Once the hash sets have been merged, then just sort the keys, and now you can easily find the (n/2)th item and the (n+2/2)th item, from the sorted hash set.

This method won''t be beneficial if the billion numbers are distinct.

Let''s first work out how to find a median of n numbers on a single machine: I am basically using partitioning strategy.

Problem :selection(n,n/2) : Find n/2 th number from least number.

You pick say middle element k and partition data into 2 sub arrays. the 1st contains all elements < k and 2nd contains all elements >= k.

if sizeof(1st sub-array) >= n/2, you know that this sub-array contains the median. You can then throw-off the 2nd sub-array. Solve this problem selection(sizeof 1st sub-array,n/2) .

In else case, throw off this 1st subarray and solve selection(2nd subarray , n/2 - sizeof(1st subarray))

Do it recursively.

time complexity is O(n) expected time.

Now if we have many machines, in each iteration, we have to process an array to split, we distribute the array into diff machines. Each machine processes their chunk of array and sends back the summary to hub controlling machine ie size of 1st subarray and size of 2nd subarray. The hub machines adds up summaries and decide which subarray (1st or 2nd) to process further and 2nd parameter of selection and sends it back to each machine. y así.

This algorithm can be implemented very neatly using map reduce?

How does it look?

My penny worth, after all that has already been brought up by others:

Finding the median on a single machine is O(N): https://en.wikipedia.org/wiki/Selection_algorithm .

Sending N numbers to 100 machines is also O(N). So, in order to make using 100 machines interesting, either the communication must be relatively fast, or N is so large that a single machine cannot handle it while N/100 is doable, or we just want to consider the mathematical problem without bothering about datacommunication.

To cut things short I''ll assume therefore that, within reasonable limits, we can send/distribute the numbers without affecting the efficiency analysis.

Consider then the following approach, where one machine is assigned to be the "master" for some general processing. This will be comparatively fast, so the "master" also participates in the common tasks that each machine performs.

  1. Each machine receives N/100 of the numbers, computes its own median and sends that information to the master.
  2. The master compiles a sorted list of all distinct medians and sends that back to each machine, defining an ordered sequence of buckets (on each machine the same), one for each median value (a single-value bucket) and one for each interval between adjacent medians. Of course there are also the lower-end and higher-end buckets for values below the lowest median and above the hightest.
  3. Each machine computes how many numbers fall in each bucket and communicates that information back to the master.
  4. The master determines which bucket contains the median, how many lower values (in total) fall below that bucket, and how many above.
  5. If the selected bucket is a single-value bucket (one of the medians) orelse the selected bucket contains only 1 (N odd) or 2 (N even) values we''re done. Otherwise we repeat the steps above with the following (obvious) modifications:
  6. Only the numbers from the selected bucket are (re)distributed from the master to the 100 machines, and moreover
  7. We''re not going to compute (on each machine) the median, but the k-th value, where we take into account how many higher numbers have been discarded from the total, and how many lower numbers. Conceptually each machine has also its share of the discarded low/high numbers and takes that into account when computing the new median in the set that (conceptually) includes (its share of) the discarded numbers.

Time-complexity:

  1. A little thinking will convince you that on each step the total number of values to analyse is reduced by a factor at least two (2 would be a rather sick case; you may expect a significantly better reduction). From this we get:
  2. Assuming that finding the median (or k-th value), which is O(N), takes c*N time where the prefactor c does not vary too wildly with N so that we can take it as a constant for the moment, we''ll get our final result in at most 2*c*N/100 time. Using 100 machines gives us, therefore, a speedup factor of 100/2 (at least).
  3. As remarked initially: the time involved in communicating the numbers between the machines may make it more attractive to simply do everything on one machine. However, IF we go for the distributed approach, the total count of numbers to be communicated in all steps together will not exceed 2*N (N for the first time, <=N/2 the second time, <= half of that the third, and so on).

Steve Jessop''s answer is wrong:

consider the following four groups:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

The median is 21, which is contained in the second group.

La mediana de los cuatro grupos es 6, 24, 30, 36, la mediana total es 27.

Entonces, después del primer ciclo, los cuatro grupos se convertirán en:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

El 21 ya se descartó erróneamente.

Este algoritmo solo admite el caso cuando hay dos grupos.

Well, suppose you know that the number of distinct integers is (say) 4 billion, then you can bucket them into 64k buckets and get a distributed count for each bucket from each machine in the cluster(100 computers). Combine all these counts. Now, find the bucket which has the median, and this time only ask for buckets for the 64k elements that would lie in your target bucket. This requires O(1) (specifically 2) queries over your "cluster". :RE

You can use the tournament tree method for finding the median. We can create a tree with 1000 leave nodes such that each leaf node is an array. We then conduct n/2 tournaments between the different arrays.The value on the root after the n/2 tournaments is the result.

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/

sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"