Calcular la mediana de mil millones de números

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:

• Divide el conjunto por igual entre las computadoras.
• Clasifícalos.
• Encuentra las medianas para cada conjunto.
• Ordenar los conjuntos en las medianas.
• Combina dos conjuntos a la vez desde la mediana más baja a la más alta.

Si tenemos m1 < m2 < m3 ...primero fusionar Set1y Set2y en el conjunto resultante, podemos descartar todos los números más bajos que la mediana de Set12(fusionados). Entonces, en cualquier momento tenemos conjuntos de igual tamaño. Por cierto, esto no se puede hacer de manera paralela. ¿Algunas ideas?

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

La máquina 1 se denominará "máquina de control" y, por el bien del argumento, comienza con todos los datos y los envía en parcelas iguales a las otras 99 máquinas, o bien los datos comienzan distribuidos de manera uniforme 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 cercanas.

Cada otra máquina clasifica sus datos, y lo hace de una manera que favorece encontrar primero los valores más bajos. Entonces, por ejemplo, una selección rápida, siempre ordenando primero la parte inferior de la partición [*]. Escribe sus datos de nuevo en la máquina de control en orden creciente tan pronto como sea posible (usando E / S asíncronas para continuar ordenando, y probablemente con Nagle encendido: experimente un poco).

La máquina de control realiza una fusión de 99 vías en los datos a medida que llegan, pero descarta los datos combinados, simplemente manteniendo el recuento del número de valores que ha visto. Calcula la mediana como la media de los valores de 1/2 billonésima y 1/2 billón más uno.

Esto sufre del problema "más lento en el rebaño". El algoritmo no puede completarse hasta que una máquina de clasificación haya enviado cada valor inferior a la mediana. Existe una posibilidad razonable de que uno de esos valores sea bastante alto dentro de su paquete de datos. Entonces, una vez que se completa la partición inicial de los datos, el tiempo de ejecución estimado es la combinación del tiempo para clasificar 1/99 de los datos y enviarlos de regreso a la computadora de control, y el tiempo para que el control lea la mitad de los datos . La "combinación" está en algún lugar 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 sea más rápido que ordenarlos (y mucho menos solo seleccionar la mediana) debe ser una red bastante rápida. Podría ser una mejor perspectiva si se presume 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 la red sea el límite, puede haber algunos trucos que puede jugar, al menos para los datos que regresan a la máquina de control. Por ejemplo, en lugar de enviar "1,2,3, .. 100", quizás una máquina de clasificación podría enviar un mensaje que signifique "100 valores inferiores a 101". Luego, la máquina de control podría realizar una fusión modificada, en la que encuentra el menor de todos esos valores superiores de rango, luego le dice a todas las máquinas de clasificación qué 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 haya un juego de adivinanzas de desafío-respuesta inteligente que la máquina de control puede jugar con las 99 máquinas de clasificación.

Sin embargo, 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 estimar a ciegas su rendimiento relativo, y dado que las compensaciones son complejas, imagino que existen soluciones mucho mejores que cualquier cosa que piense de mí, suponiendo que esto sea un problema real.

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

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

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

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

2) En lugar de ordenar los valores, asígnelos a cubos según la distribución que acaba de calcular. El número de cubos se elige para que la computadora pueda manejarlos de manera eficiente, pero de lo contrario debe ser tan grande como sea conveniente. Los rangos del depósito deben ser de manera que haya un número aproximadamente igual de valores en cada depósito (esto no es crítico para el algoritmo, pero ayuda a la eficiencia. 100.000 depósitos podrían ser apropiados). Tenga en cuenta el número de valores en cada segmento. Este es un proceso O (n).

3) Averigüe qué rango de cubos se encuentra la mediana. Esto se puede hacer simplemente examinando los números totales en cada cubo.

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

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

El proceso total es O (n), ya que ambos pasos 3 y 4 son triviales, siempre que el número de cubos sea lo suficientemente grande.

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 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

Entonces 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 realmente lujoso.

Esta es seguramente una tarea interesante para conjuntos de números más grandes. 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;)

La estimación de estadísticas de orden como mediana y percentil 99 puede distribuirse eficientemente 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 resúmenes se recopilan en un solo nodo, se fusionan (sumando efectivamente las distribuciones), y la mediana o cualquier otro percentil se puede buscar.

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

La mediana de este conjunto de números.

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

es 67.

La mediana de este conjunto de números.

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

es 40.

Suponiendo que la pregunta era sobre 1,000,000,000 de 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 se ordenaron). También suponiendo que las 100 computadoras fueran todas iguales.

usando mi laptop y GigE ...

Lo que encontré fue que mi computadora portátil puede ordenar 10,000,000 Int32 en 1.3 segundos. Entonces, una estimación aproximada sería que una clasificación de mil millones de números 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 40 MB en un gigabit Ethernet es de 0,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 descartar los números 499,999,998 más bajos, agregar los siguientes 2 y dividir por 2.

Esto puede sorprender a las personas, pero si los números son enteros lo suficientemente pequeños como para caber dentro de 32 bits (o más pequeños), ¡solo haga una clasificación de cubeta! Solo necesita 16 GB de RAM para cualquier cantidad de entradas de 32 bits y se ejecuta en O (n), lo que debería superar a cualquier sistema distribuido por un precio razonable, por ejemplo, mil millones.

Una vez que tenga la lista ordenada, es trivial elegir la mediana. De hecho, no es necesario que construyas la lista ordenada, solo debes mirar los cubos.

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 ⁹ ) números y ejecutarlo de la timemisma manera

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 de disco IO.

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

De todos modos, supongamos que tenemos más que log n núcleos para tratar este problema, y ​​no nos importa el consumo de energía, solo obtenemos la respuesta rápidamente. Supongamos además que esta es 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 a ciegas en pedazos de igual tamaño y le dice a los otros hilos M que los ordenen. Esos hilos lo hacen diligentemente, a (n/M) log (n/M)tiempo. Luego, no solo devuelven sus medianas, sino también, por ejemplo, sus percentiles 25 y 75 (los peores casos perversos son mejores si elige números ligeramente diferentes). Ahora tiene 4 millones de rangos de datos. Luego clasifica estos rangos y trabaja hacia arriba a través de la lista hasta que encuentre un número tal que, si arroja cada rango que sea más pequeño o contenga el número, habrá arrojado la mitad de sus datos. Ese es tu límite inferior para la mediana. Haga lo mismo para el límite superior. Esto lleva algo de M log Mtiempo, y todos los núcleos tienen que esperar, por lo que realmente está desperdiciandoM^2 log Mtiempo potencial Ahora tiene un hilo único que 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 de una log(n/M)vez antes de que sea más rápido simplemente tomar los datos restantes y usar un O(n)buscador medio estándar en ellos.

Entonces, la complejidad total es algo así O((n/M) log (n/M) + M^2 log M log (n/M)). Por lo tanto, esto es más rápido que la O(n)clasificación mediana en un núcleo si M >> log(n/M)y M^3 log M < n, lo cual 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.

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

- Algoritmo de selección distribuida de estadísticas de pedidos - O (n)
Simplifique el problema al problema original de encontrar el késimo número en una matriz no ordenada.
- Contando el histograma de clasificación O (n)
Debe asumir algunas propiedades sobre el rango de los números: ¿puede el rango caber en la memoria? - Clasificación de combinación externa - O (n log n) - descrito anteriormente
Básicamente clasifica los números en el primer pase, luego encuentra la mediana en el segundo.
- Si se sabe algo sobre la distribución de los números, se pueden generar otros algoritmos.

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

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

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

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

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:

Supongamos 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 (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

La media cae en el cubo medio, ignoramos el resto

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

Para cada número contamos cuántos caen en el cubo bajo y alto, el máximo y el mínimo, y mantenemos 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 conozca un poco sobre la distribución, puede ajustar cómo definir los rangos para optimizar la velocidad. En cualquier caso, el rendimiento debe ir con O (N), porque 1 + 1/3 + 1/9 ... = 1.5

Necesita min y max debido a los casos límite (p. Ej., Si la mediana es el promedio entre el máximo del mínimo anterior y el siguiente elemento).

Todas estas operaciones se pueden paralelizar, puede dar 1/100 de los datos a cada computadora y calcular los 3 depósitos en cada nodo, luego distribuir el depósito que mantiene. 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 superar 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 hacerlo mejor que O (N) aquí, porque realmente necesita contar los elementos al menos una vez.

Un método más fácil es tener números ponderados.

• Divida el conjunto grande entre computadoras
• Ordenar cada conjunto
• iterar a través del conjunto pequeño y calcular pesos para elementos repetidos
• fusionar cada 2 conjuntos en 1 (cada uno ya está ordenado) actualizando pesos
• siga fusionando conjuntos hasta que obtenga solo un conjunto
• iterar a través de este conjunto acumulando pesos hasta llegar a OneBillion / 2

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 combina sus propios números con los de la computadora 2, computadora 3 y 4, etc. Luego la computadora 1 escribe la mitad de los números de nuevo a 2, 3 a 4, etc. Luego, la combinación 1 ordena los números de las computadoras 1,2,3,4, los escribe de nuevo. Y así. Dependiendo del tamaño de la memoria RAM en las computadoras, puede salirse con la suya al no volver a escribir todos los números en las computadoras individuales en cada paso, es posible que pueda acumular los números en la computadora 1 para varios pasos, pero hace los cálculos.

Oh, finalmente obtenga la media de los valores 500000000 y 500000001 (pero verifique que haya suficientes 00s, no los tengo).

EDITAR: @Roman: bueno, si no puedes creer que sea cierto, entonces no tiene sentido que revele la verdad o la falsedad de la propuesta. Lo que quise decir era que la fuerza bruta a veces es inteligente en una carrera. Me llevó unos 15 segundos diseñar un algoritmo que estoy seguro de poder implementar, que funcione y que se adapte a una amplia gama de tamaños de entradas y números de computadoras, y que se pueda ajustar a las características de las computadoras y arreglos de redes. Si le toma a usted, o a cualquier otra persona, 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 libremente que todo esto es una afirmación, no he medido nada.

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

Hay 1 nodo primario y 99 nodos secundarios. Los nodos secundarios tienen dos llamadas api:

• stats (): devuelve min, max y count
• compare (median_guess): devuelve el valor de recuento coincidente, cuenta menos que el valor y cuenta mayor que el valor

El nodo primario llama a stats () en todos los nodos secundarios, señalando el mínimo y el máximo de todos los nodos.

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

1. Divida en dos el redondeo mínimo y máximo: esta es la 'conjetura' mediana
2. Si mayor que conteo es mayor que menor que conteo, establezca el mínimo en la suposición
3. Si el conteo mayor que es menor que el conteo menor, establezca el máximo en la suposición
4. Si el recuento es impar, finalice cuando el mínimo y el máximo sean iguales
5. Si el recuento incluso finaliza cuando el máximo <= mínimo + guesss.match_count Esto podría hacerse en los nodos que usan datos sin clasificar (digamos de los archivos de registro) de la siguiente manera.

Hay 1 nodo primario y 99 nodos secundarios. Los nodos secundarios tienen dos llamadas api:

• stats (): devuelve min, max y count
• compare (median_guess): devuelve el valor de recuento coincidente, cuenta menos que el valor y cuenta mayor que el valor

El nodo primario llama a stats () en todos los nodos secundarios, señalando el mínimo y el máximo de todos los nodos.

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

1. Divida en dos el redondeo mínimo y máximo: esta es la 'conjetura' mediana
2. Si mayor que conteo es mayor que menor que conteo, establezca el mínimo en la suposición
3. Si el conteo mayor que es menor que el conteo menor, establezca el máximo en la suposición
4. Si el recuento es impar, finalice cuando el mínimo y el máximo sean iguales
5. Si el recuento incluso finaliza cuando máximo <= mínimo + guesss.match_count

Si las estadísticas () y compare () podrían calcularse previamente con una clasificación O (N / Mlogn / M), entonces un cálculo previo O (N / M) con una complejidad de memoria de O (N) para cálculo. Entonces podría hacer compare () en tiempo constante, por lo que todo (incluido el cálculo previo) se ejecutaría en O (N / MlogN / M) + O (logN)

¡Avísame si me he equivocado!

Qué tal esto: - cada nodo puede tomar 1 billón / 100 números. En cada nodo, los elementos se pueden ordenar y se puede encontrar la mediana. Encuentra la mediana de las medianas. Podemos, agregando los recuentos de números menores que la mediana de la mediana en todos los nodos, encontramos la división x%: y% que hace la mediana de las medianas. Ahora pida a todos los nodos que eliminen elementos inferiores a la mediana de las medianas (por ejemplo, 30%: división del 70%). Se eliminan los números del 30%. 70% de 1Billion es 700million. Ahora todos los nodos que eliminaron menos de 3 millones de nodos pueden enviar esos nodos adicionales de regreso a una computadora principal. La computadora principal se redistribuye de tal manera que ahora todos los nodos tendrán un número casi igual de nodos (7 millones). Ahora que el problema se reduce a 700 millones de números ... continúa hasta que tengamos un conjunto más pequeño que se pueda calcular en una comp.

Primero veamos cómo encontrar una mediana de n números en una sola máquina: básicamente estoy usando una estrategia de partición.

Problema: selección (n, n / 2): Encuentre n / 2º número del menor número.

Elige el elemento medio k y los datos de partición en 2 submatrices. el primero contiene todos los elementos <k y el segundo contiene todos los elementos> = k.

if sizeof (1st sub-array)> = n / 2, sabe que esta sub-matriz contiene la mediana. Luego puede deshacerse de la segunda sub-matriz. Resuelva esta selección de problema (tamaño de la 1ª submatriz, n / 2) .

En otro caso, deseche esta primera subcadena y resuelva la selección (segunda subcadena, n / 2 - sizeof (primera subcampo))

Hazlo recursivamente.

la complejidad del tiempo es O (n) tiempo esperado.

Ahora, si tenemos muchas máquinas, en cada iteración, tenemos que procesar una matriz para dividirla, distribuimos la matriz en máquinas diff. Cada máquina procesa su porción de matriz y envía el resumen a la máquina de control central, es decir, el tamaño de la primera subcadena y el tamaño de la segunda subcadena. Las máquinas concentradoras suman resúmenes y deciden qué subarreglos (1 ° o 2 °) procesar más y segundo parámetro de selección y lo envían de vuelta a cada máquina. y así.

Este algoritmo se puede implementar de manera muy clara usando map reduce?

¿Cómo se ve?

Creo que la respuesta de Steve Jessop será la más rápida.

Si el tamaño de la transferencia de datos de la red es el cuello de botella, aquí hay otro enfoque.

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.

Lo haría así:

al principio, los 100 trabajan para encontrar el número más alto y el más bajo; cada computadora tiene su parte de la base de datos / archivo que consulta;

cuando se encuentran los números más altos y más bajos, una computadora lee los datos y distribuye cada número, de manera uniforme, al resto de los 99; los números se distribuyen por intervalos iguales; (uno puede tomar de -100 millones a 0, otro - de 0 a 100 millones, etc.);

Mientras recibe los números, cada una de las 99 computadoras ya los ordena;

Entonces, es fácil encontrar la mediana ... Vea cuántos números tiene cada computadora, sume todos (la suma de cuántos números hay, no los números mismos), divida por 2; calcular en qué computadora está el número y en qué índice;

:) voilla

PD Parece que hay mucha confusión aquí; la MEDIANA - ¡es el NÚMERO EN MEDIO DE UNA LISTA CLASIFICADA DE NÚMEROS!

Puedes usar el método del árbol de torneo para encontrar la mediana. Podemos crear un árbol con 1000 nodos de licencia de modo que cada nodo de hoja sea una matriz. Luego realizamos n / 2 torneos entre las diferentes matrices. El valor en la raíz después de los torneos n / 2 es el resultado.

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

Si los números no son distintos, y solo pertenecen a un cierto rango, es decir, se repiten, entonces una solución simple que se me ocurre es distribuir los números entre 99 máquinas por igual y mantener una máquina como maestra. Ahora cada máquina itera sobre sus números dados y almacena el recuento de cada número en un conjunto hash. Cada vez que el número se repite en el conjunto de números asignados a esa computadora en particular, actualiza su cuenta en el conjunto de hash.

Todas las máquinas devuelven su hash set a la máquina maestra. La máquina maestra combina los conjuntos de hash, sumando el recuento de la misma clave encontrada en un conjunto de hash. Por ejemplo, el conjunto de hash de la máquina n. ° 1 tenía una entrada de ("1", 7), y el conjunto de hash de la máquina n. ° 2 tenía una entrada de ("1", 9), por lo que la máquina maestra al peinar los conjuntos de hash realiza una entrada de ("1", 16), y así sucesivamente.

Una vez que los conjuntos de hash se hayan fusionado, simplemente ordene las claves, y ahora puede encontrar fácilmente el elemento (n / 2) th y el elemento (n + 2/2) th, del conjunto de hash ordenado.

Este método no será beneficioso si los mil millones de números son distintos.

Bueno, suponga que sabe que el número de enteros distintos es (digamos) 4 mil millones, luego puede agruparlos en 64k cubos y obtener un recuento distribuido para cada cubo de cada máquina en el clúster (100 computadoras). Combina todos estos recuentos. Ahora, encuentra el cubo que tiene la mediana, y esta vez solo pide cubos para los elementos de 64k que estarían en tu cubo objetivo. Esto requiere consultas O (1) (específicamente 2) sobre su "clúster". :RE

Mi centavo vale, después de todo lo que otros ya han mencionado:

Encontrar la mediana en una sola máquina es O (N): https://en.wikipedia.org/wiki/Selection_algorithm .

Enviar números N a 100 máquinas también es O (N). Entonces, para hacer que el uso de 100 máquinas sea interesante, o la comunicación debe ser relativamente rápida, o N es tan grande que una sola máquina no puede manejarlo mientras N / 100 es factible, o simplemente queremos considerar el problema matemático sin preocuparnos por comunicación de datos.

Para acortar las cosas, supondré, por lo tanto, que dentro de límites razonables, podemos enviar / distribuir los números sin afectar el análisis de eficiencia.

Considere entonces el siguiente enfoque, donde se asigna una máquina para ser el "maestro" para algún procesamiento general. Esto será comparativamente rápido, por lo que el "maestro" también participa en las tareas comunes que realiza cada máquina.

1. Cada máquina recibe N / 100 de los números, calcula su propia mediana y envía esa información al maestro.
2. El maestro compila una lista ordenada de todas las medianas distintas y la envía de vuelta a cada máquina, definiendo una secuencia ordenada de cubos (en cada máquina igual), una para cada valor medio (un cubo de valor único) y otra para cada intervalo entre medianas adyacentes. Por supuesto, también están los segmentos de extremo inferior y superior para valores por debajo de la mediana más baja y por encima de la más alta.
3. Cada máquina calcula cuántos números caen en cada cubo y comunica esa información al maestro.
4. El maestro determina qué cubo contiene la mediana, cuántos valores más bajos (en total) están por debajo de ese cubo y cuántos más arriba.
5. Si el depósito seleccionado es un depósito de un solo valor (una de las medianas) o bien, el depósito seleccionado contiene solo 1 (N impar) o 2 (N pares) valores que hemos terminado. De lo contrario, repetimos los pasos anteriores con las siguientes modificaciones (obvias):
6. Solo los números del grupo seleccionado se (re) distribuyen desde el maestro a las 100 máquinas, y además
7. No vamos a calcular (en cada máquina) la mediana, sino el valor k-ésimo, donde tenemos en cuenta cuántos números más altos se han descartado del total y cuántos números más bajos. Conceptualmente, cada máquina también tiene su parte de los números bajos / altos descartados y lo tiene en cuenta al calcular la nueva mediana en el conjunto que (conceptualmente) incluye (su parte de) los números descartados.

Complejidad de tiempo:

1. Un poco de pensamiento lo convencerá de que en cada paso el número total de valores a analizar se reduce en un factor de al menos dos (2 sería un caso bastante enfermo; puede esperar una reducción significativamente mejor). De esto obtenemos:
2. Suponiendo que encontrar la mediana (o el valor k-ésimo), que es O (N), toma c * N tiempo en el que el prefactor c no varía demasiado con N para que podamos tomarlo como una constante por el momento, Obtendremos nuestro resultado final en un máximo de 2 * c * N / 100 veces. El uso de 100 máquinas nos da, por lo tanto, un factor de aceleración de 100/2 (al menos).
3. Como se señaló inicialmente: el tiempo necesario para comunicar los números entre las máquinas puede hacer que sea más atractivo simplemente hacer todo en una máquina. Sin embargo, SI vamos por el enfoque distribuido, el recuento total de números que se comunicarán en todos los pasos juntos no excederá de 2 * N (N por primera vez, <= N / 2 la segunda vez, <= la mitad de eso tercero, y así sucesivamente).

1. Divide los mil millones de números en 100 máquinas. Cada máquina tendrá 10 ^ 7 números.

2. Para cada número entrante en una máquina, almacene el número en un mapa de frecuencia, número -> conteo. También almacene el número mínimo en cada máquina.

3. Encuentre la mediana en cada máquina: a partir del número mínimo en cada máquina, sume los recuentos hasta alcanzar el índice de mediana. La mediana en cada máquina será la aprox. menores y mayores que 5 * 10 ^ 6 números.

4. Encuentre la mediana de todas las medianas, que será menor y mayor que aprox. 50 * 10 ^ 7 números, que es la mediana de mil millones de números.

Ahora alguna optimización del segundo paso: en lugar de almacenar en un mapa de frecuencia, almacene los recuentos en una matriz de bits variable. Por ejemplo: Digamos que a partir del número mínimo en una máquina, estos son conteos de frecuencia:

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

Lo anterior se puede almacenar en una matriz de bits como:

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

Tenga en cuenta que en total costará aproximadamente 10 ^ 7 bits para cada máquina, ya que cada máquina solo maneja 10 ^ 7 números. 10 ^ 7bits = 1.25 * 10 ^ 6 bytes, que es 1.25MB

Entonces, con el enfoque anterior, cada máquina necesitará 1.25 MB de espacio para calcular la mediana local. Y la mediana de las medianas se puede calcular a partir de esas 100 medianas locales, lo que resulta en una mediana de mil millones de números.

Sugiero un método para calcular aproximadamente la mediana. :) Si estos mil millones de números están en un orden aleatorio, creo que puedo elegir 1/100 o 1/10 de mil millones de números al azar, ordenarlos con 100 máquinas y luego elegir la mediana de ellos. O dividamos mil millones de números en 100 partes, dejemos que cada máquina elija 1/10 de cada parte al azar, calcule la mediana de ellas. Después de eso tenemos 100 números y podemos calcular la mediana del número 100 más fácilmente. Solo una sugerencia, no estoy seguro de si es matemáticamente correcto. Pero creo que puede mostrar el resultado a un gerente no tan bueno en matemáticas.

La respuesta de Steve Jessop es incorrecta:

considere los siguientes cuatro grupos:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

La mediana es 21, que está contenida en el segundo grupo.

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 está descartado por error.

Este algoritmo solo admite el caso cuando hay dos grupos.