Calculer la médiane d’un milliard de nombres

Si vous avez un milliard de numéros et cent ordinateurs, quelle est la meilleure façon de localiser la médiane de ces chiffres?

Une des solutions que j’ai est:

  • Diviser le jeu également entre les ordinateurs.
  • Trier les
  • Trouvez les médianes pour chaque série.
  • Trier les ensembles sur les médianes.
  • Fusionner deux ensembles à la fois de la plus basse à la plus haute médiane.

Si nous avons m1 < m2 < m3 ... puis d’abord fusionner Set2 et Set2 et dans l’ensemble résultant, nous pouvons éliminer tous les nombres inférieurs à la médiane de Set12 (fusionné). Donc, à tout moment, nous avons des ensembles de taille égale. Au fait, cela ne peut pas être fait de manière parallèle. Des idées?

Ah, mon cerveau vient de démarrer, j’ai maintenant une suggestion judicieuse. Probablement trop tard si cela avait été une interview, mais tant pis:

La machine 1 doit être appelée “machine de contrôle” et, pour des raisons d’argument, elle commence par toutes les données et l’envoie à parts égales aux 99 autres machines, sinon les données commencent à être réparties de manière égale entre les machines. envoie 1/99 de ses données à chacun des autres. Les partitions ne doivent pas nécessairement être égales, il suffit de les fermer.

Chaque autre machine sortinge ses données et le fait de manière à favoriser la recherche des valeurs les plus basses en premier. Donc, par exemple, un sorting rapide, en sortingant toujours la partie inférieure de la partition en premier [*]. Il réécrit ses données sur la machine de contrôle dans l’ordre croissant dès que possible (en utilisant des E / S asynchrones pour continuer le sorting, et probablement avec Nagle on: expérimente un peu).

La machine de contrôle effectue une fusion à 99 dans les données à son arrivée, mais élimine les données fusionnées, en ne tenant compte que du nombre de valeurs vues. Il calcule la médiane comme la moyenne des valeurs au 1/2 milliardième et au 1/2 milliard et plus.

Cela souffre du problème “le plus lent dans le troupeau”. L’algorithme ne peut pas être complet tant que chaque valeur inférieure à la médiane n’a pas été envoyée par une machine de sorting. Il y a une chance raisonnable qu’une telle valeur soit assez élevée dans sa plot de données. Ainsi, une fois que le partitionnement initial des données est terminé, le temps d’exécution estimé est la combinaison du temps nécessaire pour sortinger 1 / 99ème des données et le renvoyer à l’ordinateur de contrôle, et le temps nécessaire au contrôle pour lire les données en 1/2 . La “combinaison” est quelque part entre le maximum et la sum de ces temps, probablement proche du maximum.

Mon instinct est que pour pouvoir envoyer des données sur un réseau plus rapidement que le sortinger (et pas seulement sélectionner la médiane), il faut que le réseau soit rapide. Peut-être une meilleure perspective si le réseau peut être présumé instantané, par exemple si vous avez 100 cœurs avec un access égal à la RAM contenant les données.

Étant donné que les E / S réseau sont susceptibles d’être liées, il est possible que vous puissiez jouer à certaines astuces, au moins pour les données renvoyées à la machine de contrôle. Par exemple, au lieu d’envoyer “1,2,3, .. 100”, une machine de sorting pourrait peut-être envoyer un message signifiant “100 valeurs inférieures à 101”. La machine de contrôle peut alors effectuer une fusion modifiée, dans laquelle elle trouve la plus petite de toutes ces valeurs haut de gamme, puis indique à toutes les machines de sorting ce qu’elle était afin qu’elles puissent (a) indiquer à la machine de contrôle comment beaucoup de valeurs à “compter” en dessous de cette valeur, et (b) reprendre l’envoi de leurs données sortingées à partir de ce point.

Plus généralement, la machine de contrôle peut jouer avec les 99 machines de sorting.

Cela implique des allers-retours entre les machines, ce que ma première version simplifiée évite. Je ne sais pas vraiment comment estimer en aveugle leur performance relative, et comme les compromis sont complexes, j’imagine qu’il existe de bien meilleures solutions que tout ce que je pense, en supposant que cela pose un réel problème.

[*] stack disponible le permet – votre choix de la partie à faire en premier est limité si vous n’avez pas d’espace supplémentaire O (N). Mais si vous avez suffisamment d’espace supplémentaire, vous pouvez faire votre choix, et si vous n’avez pas assez d’espace, vous pouvez au moins utiliser ce que vous avez à faire pour couper des coins, en faisant d’abord la petite partie pour les premières partitions.

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

Je déteste être le contre-homme ici, mais je ne pense pas que le sorting soit nécessaire, et je pense que tout algorithme impliquant le sorting d’un milliard / 100 nombres va être lent. Considérons un algorithme sur un ordinateur.

1) Sélectionnez 1 000 valeurs au hasard dans le milliard et utilisez-les pour avoir une idée de la dissortingbution des nombres, en particulier une plage.

2) Au lieu de sortinger les valeurs, atsortingbuez-les aux compartiments en fonction de la dissortingbution que vous venez de calculer. Le nombre de compartiments est choisi de manière à ce que l’ordinateur puisse les traiter efficacement, mais devrait être aussi grand que possible. Les plages de compartiments doivent correspondre à un nombre approximativement égal de valeurs dans chaque compartiment (cela n’est pas essentiel pour l’algorithme, mais cela aide à l’efficacité. 100 000 seaux peuvent être appropriés). Notez le nombre de valeurs dans chaque compartiment. Ceci est un processus O (n).

3) Découvrez quelle catégorie de seau correspond aux mensonges médians. Cela peut être fait en examinant simplement les nombres totaux dans chaque seau.

4) Trouvez la médiane réelle en examinant les valeurs dans ce seau. Vous pouvez utiliser un sorting ici si vous le souhaitez, puisque vous ne sortingez peut-être que 10 000 numéros. Si le nombre de valeurs dans ce compartiment est élevé, vous pouvez utiliser cet algorithme à nouveau jusqu’à ce que vous ayez un nombre suffisant pour le sortinger.

Cette approche est sortingviale en divisant les valeurs entre les ordinateurs. Chaque ordinateur rapporte les totaux dans chaque compartiment à un ordinateur «de contrôle» qui effectue l’étape 3. Pour l’étape 4, chaque ordinateur envoie les valeurs (sortingées) dans le compartiment correspondant à l’ordinateur de contrôle (vous pouvez faire ces deux algorithmes en parallèle également, mais ça ne vaut probablement pas la peine).

Le processus total est O (n), car les deux étapes 3 et 4 sont sortingviales, à condition que le nombre de compartiments soit suffisamment grand.

L’ estimation des statistiques d’ordre telles que la médiane et le 99ème percentile peut être efficacement dissortingbuée avec des algorithmes tels que t-digest ou Q-digest .

En utilisant l’un ou l’autre algorithme, chaque nœud produit un résumé, qui représente la dissortingbution des valeurs stockées localement. Les résumés sont collectés sur un seul nœud, fusionnés (additionnant effectivement les dissortingbutions) et la médiane ou tout autre percentile peut alors être recherchée.

Cette approche est utilisée par elasticsearch et, vraisemblablement, par BigQuery (en suivant la description de la fonction QUANTILES).

Un milliard est en fait une tâche ennuyeuse pour un ordinateur moderne. Nous parlons ici d’une valeur de 4 Go d’entiers de 4 octets ici … 4 Go … c’est la RAM de certains smartphones.

 public class Median { public static void main(Ssortingng[] 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)); } } 

Sortie sur ma machine:

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

Donc, cela se termine sur ma machine en moins de deux minutes (dont 1/10 pour générer des nombres aléatoires) en utilisant un seul cœur et cela fait même un sorting complet. Rien d'extraordinaire.

Ceci est sûrement une tâche intéressante pour des ensembles de nombres plus importants. Je veux juste faire une remarque ici: un milliard de cacahuètes. Alors réfléchissez-y à deux fois avant de lancer des solutions complexes à des tâches étonnamment simples;)

La médiane pour cet ensemble de nombres

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

est 67.

La médiane pour cet ensemble de nombres

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

est 40.

En supposant que la question était d’environ 1 000 000 000 entiers (x) où 0> = x <= 2 147 483 647 et que l'OP recherchait (élément (499 999 999) + élément (500 000 000)) / 2 (si les nombres étaient triés). En supposant également que tous les 100 ordinateurs étaient tous égaux.

en utilisant mon ordinateur portable et GigE …

Ce que j’ai trouvé, c’est que mon ordinateur portable peut sortinger 10 000 000 d’Int32 en 1,3 seconde. Donc, une estimation approximative serait qu’un sorting de milliards de chiffres prendrait 100 x 1,3 secondes (2 minutes 10 secondes);).

Une estimation d’un transfert de fichier unidirectionnel d’un fichier de 40 Mo sur un gigabit Ethernet est de 0,32 seconde. Cela signifie que les résultats sortingés de tous les ordinateurs seront renvoyés dans environ 32 secondes (l’ordinateur 99 n’a pas reçu son fichier avant 30 secondes après le début). À partir de là, il ne faut pas longtemps pour se débarrasser des 499 999 998 numéros les plus bas, append les 2 suivants et diviser par 2.

Curieusement, je pense que si vous avez suffisamment d’ordinateurs, il est préférable de sortinger que d’utiliser les algorithmes de recherche de médiane O(n) . (Sauf si vos cœurs sont très, très lents, cependant, j’en utiliserais un et utiliserais un algorithme de recherche de médiane O(n) pour seulement 1e9 chiffres, mais si vous aviez 1e12, cela pourrait être moins pratique.)

Quoi qu’il en soit, supposons que nous ayons plus que des cœurs de log n pour faire face à ce problème, et nous ne nous soucions pas de la consommation d’énergie, simplement pour obtenir la réponse rapidement. Supposons que ce soit une machine SMP avec toutes les données déjà chargées en mémoire. (Les machines à 32 cœurs de Sun sont de ce type, par exemple.)

Un thread coupe la liste à l’aveuglette en morceaux de taille égale et demande aux autres threads M de les sortinger. Ces threads le font avec diligence, en (n/M) log (n/M) temps. Ils renvoient alors non seulement leurs médianes, mais aussi leurs 25e et 75e centiles (les pervers pires sont meilleurs si vous choisissez des nombres légèrement différents). Vous disposez maintenant de 4 millions de plages de données. Vous sortingez ensuite ces plages et parcourez la liste vers le haut jusqu’à ce que vous trouviez un nombre tel que, si vous rejetez toutes les plages plus petites ou contiennent le nombre, vous aurez rejeté la moitié de vos données. C’est votre limite inférieure pour la médiane. Faites la même chose pour la limite supérieure. Cela prend quelque chose comme le temps de M log M , et tous les cœurs doivent attendre, donc cela gaspille vraiment le temps potentiel de M^2 log M Maintenant, votre thread unique dit aux autres de lancer toutes les données en dehors de la plage (vous devriez jeter environ la moitié de chaque passe) et répéter – ceci est une opération sortingvialement rapide puisque les données sont déjà sortingées. Vous ne devriez pas avoir à répéter cela plus que le temps de log(n/M) avant qu’il soit plus rapide de saisir simplement les données restantes et d’utiliser un outil de recherche de médiane O(n) standard.

Ainsi, la complexité totale est quelque chose comme O((n/M) log (n/M) + M^2 log M log (n/M)) . Ainsi, ceci est plus rapide que le sorting médian O(n) sur un kernel si M >> log(n/M) et M^3 log M < n , ce qui est vrai pour le scénario que vous avez décrit.

Je pense que c'est une très mauvaise idée étant donné son inefficacité, mais c'est plus rapide.

Cela pourrait surprendre les gens, mais si les nombres sont des nombres entiers suffisamment petits pour tenir dans 32 bits (ou plus petits), il suffit de faire un sorting par seau! N’a besoin que de 16 Go de RAM pour un nombre d’ints de 32 bits et s’exécute dans O (n), ce qui devrait surpasser tout système dissortingbué pour un n raisonnable, par exemple un milliard.

Une fois que vous avez la liste sortingée, il est sortingvial de choisir la médiane. En fait, vous n’avez pas besoin de construire la liste sortingée, mais vous ne devriez regarder que les compartiments.

Une implémentation simple est illustrée ci-dessous. Ne fonctionne que pour les entiers 16 bits, mais l’extension à 32 bits devrait être facile.

 #include  #include  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; } 

Utiliser un fichier texte avec un milliard (10 9 ) de chiffres et s'exécuter avec le time comme ça

 time ./median < billion 

donne un temps de fonctionnement sur ma machine 1m49.293s. La plupart du temps d'exécution est probablement le disque IO.

Un ordinateur suffit largement pour résoudre le problème.

Mais supposons qu’il y a 100 ordinateurs. La seule chose complexe à faire est de sortinger la liste. Divisez-le en 100 parties, envoyez une partie à chaque ordinateur, laissez-les y être sortingées et fusionnez les pièces par la suite.

Ensuite, prenez le numéro au milieu de la liste sortingée (c.-à-d. Avec l’index 5 000 000 000).

Cela dépend de vos données. Le pire scénario est que les numéros sont uniformément dissortingbués.

Dans ce cas, vous pouvez trouver la médiane en temps O (N) comme dans cet exemple:

Supposons que vos chiffres sont les 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (intervalle 1-10) .

Nous créons 3 seaux: 1-3, 4-7, 8-10. Notez que haut et bas ont la même taille.

Nous remplissons les seaux avec les nombres, comptons combien tombent dans chacun, le max et le min

  • faible (5): 2,1,1,3,3, min 1, max 3
  • milieu (10): 7,5,6,4,4,6,4,7,4,4, min 4, max 7
  • haute (5): 10, 10, 8, 9, 9, min 8, max 10

La moyenne tombe dans le seau du milieu, nous négligeons le rest

Nous créons 3 seaux: 4, 5-6, 7. Low commencera avec un compte de 5 et avec un maximum de 3 et un maximum avec un min de 8 et un compte de 5.

Pour chaque nombre, nous comptons combien de personnes tombent dans le seau bas et haut, le max et le min et gardent le seau du milieu.

  • vieux bas (5)
  • faible (5): 4, 4, 4, 4, 4, max 4
  • milieu (3): 5,6,6
  • haut (2): 7, 7, min 7
  • vieux haut (5)

Maintenant, nous pouvons calculer directement la médiane: nous avons une situation comme celle-ci

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

la médiane est donc de 4,5.

En supposant que vous en savez un peu sur la dissortingbution, vous pouvez affiner la définition des plages pour optimiser la vitesse. Dans tous les cas, la performance devrait aller avec O (N), car 1 + 1/3 + 1/9 … = 1,5

Vous avez besoin de min et de max en raison des cas de bord (par exemple, si la médiane est la moyenne entre le maximum de l’ancien bas et l’élément suivant).

Toutes ces opérations peuvent être parallélisées, vous pouvez donner 1/100 des données à chaque ordinateur et calculer les 3 compartiments dans chaque nœud, puis dissortingbuer le compartiment que vous conservez. Cela vous permet également d’utiliser le réseau efficacement car chaque nombre est passé en moyenne 1,5 fois (donc O (N)). Vous pouvez même le battre si vous ne transmettez que le nombre minimal entre les nœuds (par exemple, si le nœud 1 a 100 numéros et le nœud 2 150, alors le nœud 2 peut donner 25 numéros au nœud 1).

À moins d’en savoir plus sur la dissortingbution, je doute que vous puissiez faire mieux que O (N) ici, car vous devez en fait compter les éléments au moins une fois.

Répartissez les 10 ^ 9 numéros, 10 ^ 7 sur chaque ordinateur ~ 80 Mo sur chacun. Chaque ordinateur sortinge ses numéros. Ensuite, l’ordinateur 1 fusionne – sortinge ses propres numéros avec ceux de l’ordinateur 2, de l’ordinateur 3 et 4, etc. Ensuite, l’ordinateur 1 écrit la moitié des nombres à 2, 3 à 4, etc. 1,2,3,4 les réécrit. Etc. En fonction de la taille de la mémoire vive des ordinateurs, vous risquez de ne pas réécrire tous les numéros sur les ordinateurs individuels à chaque étape. Vous pourrez peut-être accumuler les nombres sur l’ordinateur 1 pendant plusieurs étapes, mais vous faites les calculs.

Oh, enfin, obtenez la moyenne des valeurs 500000000 et 500000001st (mais vérifiez qu’il y en a assez, je n’ai pas).

EDIT: @Roman – eh bien, si vous ne pouvez pas y croire même si c’est vrai, alors il est inutile de révéler la vérité ou le mensonge de la proposition. Ce que je voulais dire, c’est que la force brute bat parfois fort dans une course. Il m’a fallu environ 15 secondes pour concevoir un algorithme que je suis sûr de pouvoir mettre en œuvre, qui fonctionnera et qui pourra être adapté à un large éventail d’entrées et de nombres d’ordinateurs, et ajustable aux caractéristiques des ordinateurs et des ordinateurs. arrangements de réseautage. Si cela vous prend, ou à quelqu’un d’autre, disons 15 minutes pour concevoir un algorithme plus sophistiqué, j’ai un avantage de 14 minutes pour coder ma solution et la lancer.

Mais j’admets librement que c’est une affirmation, je n’ai rien mesuré.

Cela peut être fait plus rapidement que l’algorithme voté (n log n)

– Algorithme de sélection répartie des statistiques d’ordre – O (n)
Simplifier le problème au problème initial de trouver le kième nombre dans un tableau non sortingé.
– Histogramme de sorting de comptage O (n)
Vous devez assumer certaines propriétés concernant la plage des nombres – la plage peut-elle tenir dans la mémoire? – Tri de fusion externe – O (n log n) – décrit ci-dessus
En gros, vous sortingez les nombres sur la première passe, puis vous trouvez la médiane sur la seconde.
– Si quelque chose est connue sur la dissortingbution des nombres, d’autres algorithmes peuvent être produits.

Pour plus de détails et d’implémentation, voir:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

Cela pourrait être fait sur les nœuds utilisant des données qui ne sont pas sortingées entre les nœuds (disons à partir de fichiers journaux) de la manière suivante.

Il y a 1 nœud parent et 99 nœuds enfants. Les nœuds enfants ont deux appels API:

  • stats (): retourne min, max et count
  • compare (median_guess): retourne la valeur correspondante, compte moins que la valeur et compte plus que la valeur

Le nœud parent appelle stats () sur tous les nœuds enfants, en notant le minimum et le maximum de tous les nœuds.

Une recherche binary peut maintenant être effectuée de la manière suivante:

  1. Bisect le minimum et le maximum arrondis à la baisse – c’est la médiane
  2. Si le plus grand que le compte est plus que le moins que le nombre, définissez le minimum à la conjecture
  3. Si le plus grand que le compte est inférieur au moins que le nombre, définissez le maximum à la conjecture
  4. Si count est impair, quand minimum et maximum sont égaux
  5. Si count est pair, terminez-le lorsque maximum <= minimum + guess.match_count Cela peut être fait sur les nœuds utilisant des données non triées (disons à partir de fichiers journaux) de la manière suivante.

Il y a 1 nœud parent et 99 nœuds enfants. Les nœuds enfants ont deux appels API:

  • stats (): retourne min, max et count
  • compare (median_guess): retourne la valeur correspondante, compte moins que la valeur et compte plus que la valeur

Le nœud parent appelle stats () sur tous les nœuds enfants, en notant le minimum et le maximum de tous les nœuds.

Une recherche binary peut maintenant être effectuée de la manière suivante:

  1. Bisect le minimum et le maximum arrondis à la baisse – c’est la médiane
  2. Si le plus grand que le compte est plus que le moins que le nombre, définissez le minimum à la conjecture
  3. Si le plus grand que le compte est inférieur au moins que le nombre, définissez le maximum à la conjecture
  4. Si count est impair, quand minimum et maximum sont égaux
  5. Si count est pair, terminez au maximum <= minimum + guess.match_count

Si les stats () et compare () peuvent être pré-calculées avec un sorting O (N / Mlogn / M), alors un pré-calcul O (N / M) avec une complexité de mémoire de O (N) pour le pré-calcul calcul. Ensuite, vous pouvez faire une comparaison () dans un temps constant, de sorte que le tout (y compris le pré-calcul) s’exécuterait dans O (N / MlogN / M) + O (logN)

Faites moi savoir si j’ai fait une erreur!

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

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 dissortingbute 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. etc.

This algorithm can be implemented very neatly using map reduce?

How does it look?

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. 

Je le ferais comme ça:

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 dissortingbutes each number, evenly, to the rest of the 99; the numbers are dissortingbuted 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!

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/

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

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 dissortingbuted 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”. :RÉ

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/dissortingbute 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 comstacks 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)dissortingbuted 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 parsing 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 dissortingbuted 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).
  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.

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.

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.

The median of the four groups are 6, 24, 30, 36, The total median is 27.

So after the first loop, the four groups will become:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

The 21 is already wrongly discarded.

This algorithm only support the case when there are two groups.