Calculez la médiane d'un milliard de nombres

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

Une solution que j'ai est:

• Répartissez l'ensemble de manière égale entre les ordinateurs.
• Triez-les.
• Trouvez les médianes pour chaque ensemble.
• Triez les ensembles sur les médianes.
• Fusionner deux ensembles à la fois de la médiane la plus basse à la plus élevée.

Si nous avons m1 < m2 < m3 ...alors d'abord fusionné Set1et Set2et dans l'ensemble résultant, nous pouvons rejeter tous les nombres inférieurs à la médiane de Set12(fusionné). Donc, à tout moment, nous avons des ensembles de taille égale. En passant, cela ne peut pas être fait de manière parallèle. Des idées?

Ah, mon cerveau vient de démarrer, j'ai une suggestion sensée maintenant. Probablement trop tard s'il s'agissait d'une interview, mais tant pis:

La machine 1 sera appelée la "machine de contrôle", et pour des raisons d'argumentation soit elle commence avec toutes les données, et les envoie en paquets égaux aux 99 autres machines, soit les données commencent uniformément réparties entre les machines, et il envoie 1/99 de ses données à chacun des autres. Les partitions n'ont pas besoin d'être égales, fermez simplement.

Chaque autre machine trie ses données et le fait d'une manière qui favorise la recherche des valeurs les plus basses en premier. Par exemple, un tri rapide, en triant toujours la partie inférieure de la partition en premier [*]. Il réécrit ses données sur la machine de contrôle dans un ordre croissant dès qu'il le peut (en utilisant des E / S asynchrones pour continuer le tri, et probablement avec Nagle activé: expérimentez un peu).

La machine de contrôle effectue une fusion à 99 voies sur les données à leur arrivée, mais rejette les données fusionnées, en gardant simplement le compte du nombre de valeurs vues. Il calcule la médiane comme la moyenne des 1/2 milliardième et 1/2 milliard plus unième valeurs.

Cela souffre du problème du «plus lent du troupeau». L'algorithme ne peut pas se terminer tant que chaque valeur inférieure à la médiane n'a pas été envoyée par une machine de tri. Il y a une chance raisonnable qu'une telle valeur soit assez élevée dans sa parcelle de données. Ainsi, une fois le partitionnement initial des données terminé, le temps de fonctionnement estimé est la combinaison du temps nécessaire pour trier 1 / 99ème des données et les renvoyer à l'ordinateur de contrôle, et le temps nécessaire au contrôle pour lire la moitié des données. . La "combinaison" se situe quelque part entre le maximum et la somme de ces temps, probablement proche du maximum.

Mon instinct est que pour envoyer des données sur un réseau plus rapide que de les trier (sans parler de la sélection de la médiane), il doit s'agir d'un réseau très 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 accès égal à la RAM contenant les données.

Étant donné que les E / S réseau sont susceptibles d'être la limite, il peut y avoir quelques astuces que vous pouvez jouer, au moins pour les données revenant à la machine de contrôle. Par exemple, au lieu d'envoyer "1,2,3, .. 100", une machine de tri pourrait peut-être envoyer un message signifiant "100 valeurs inférieures à 101". La machine de contrôle pourrait alors effectuer une fusion modifiée, dans laquelle elle trouve la moindre de toutes ces valeurs haut de gamme, puis dit à toutes les machines de tri ce que c'était, afin qu'elles puissent (a) dire à la machine de contrôle comment plusieurs valeurs à «compter» en dessous de cette valeur, et (b) reprendre l'envoi de leurs données triées à partir de ce point.

Plus généralement, il existe probablement un jeu de devinettes astucieux défi-réponse auquel la machine de contrôle peut jouer avec les 99 machines de tri.

Cela implique des allers-retours entre les machines, ce que ma première version plus simple évite. Je ne sais pas vraiment comment estimer à l'aveugle leur performance relative, et comme les compromis sont complexes, j'imagine qu'il existe de bien meilleures solutions que tout ce que je penserai à moi-même, en supposant que ce soit un problème réel.

[*] pile 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 pour couper certains 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 contrariant ici, mais je ne pense pas que le tri soit nécessaire, et je pense que tout algorithme impliquant le tri d'un milliard / 100 nombres sera lent. Considérons un algorithme sur un ordinateur.

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

2) Au lieu de trier les valeurs, attribuez-les à des compartiments en fonction de la distribution que vous venez de calculer. Le nombre de seaux est choisi de manière à ce que l'ordinateur puisse les gérer efficacement, mais devrait autrement être aussi grand que pratique. Les plages de compartiments doivent être telles qu'un nombre à peu près égal de valeurs entre dans chaque compartiment (ce n'est pas critique pour l'algorithme, mais cela améliore l'efficacité. 100 000 compartiments peuvent être appropriés). Notez le nombre de valeurs dans chaque compartiment. Il s'agit d'un processus O (n).

3) Découvrez dans quelle plage de seaux se situe la médiane. Cela peut être fait en examinant simplement les nombres totaux dans chaque compartiment.

4) Trouvez la médiane réelle en examinant les valeurs de ce compartiment. Vous pouvez utiliser un tri ici si vous le souhaitez, car vous ne triez que 10 000 numéros. Si le nombre de valeurs dans ce compartiment est important, vous pouvez utiliser à nouveau cet algorithme jusqu'à ce que vous ayez un nombre suffisamment petit pour trier.

Cette approche parallélise trivialement en divisant les valeurs entre les ordinateurs. Chaque ordinateur rapporte les totaux de chaque compartiment à un ordinateur de `` contrôle '' qui effectue l'étape 3. Pour l'étape 4, chaque ordinateur envoie les valeurs (triées) dans le compartiment concerné à l'ordinateur de contrôle (vous pouvez également faire ces deux algorithmes en parallèle, mais ça n'en vaut probablement pas la peine).

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

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

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));
        }
}

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 (1:43 dont 0:10 pour générer des nombres aléatoires) en utilisant un seul cœur et il fait même un tri complet. Rien d'extraordinaire vraiment.

C'est certainement une tâche intéressante pour des ensembles de nombres plus importants. Je veux juste faire une remarque ici: un milliard, c'est des arachides. Alors réfléchissez à deux fois avant de commencer à lancer des solutions complexes à des tâches étonnamment simples;)

L' estimation des statistiques d'ordre telles que la médiane et le 99e centile peut être efficacement distribuée avec des algorithmes tels que t-digest ou Q-digest .

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

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

La médiane de cet ensemble de nombres

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

est 67.

La médiane de 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 d'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 ont été triés). En supposant également que 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 trier 10 000 000 Int32 en 1,3 seconde. Donc, une estimation approximative serait qu'un tri d'un milliard de nombres 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 triés de tous les ordinateurs seront renvoyés dans environ 32 secondes (l'ordinateur 99 n'a reçu son fichier que 30 secondes après le démarrage). À partir de là, il ne devrait pas falloir longtemps pour supprimer les 499 999 998 nombres les plus bas, ajouter les 2 suivants et diviser par 2.

Cela peut surprendre les gens, mais si les nombres sont des nombres entiers suffisamment petits pour tenir à l'intérieur de 32 bits (ou moins) - Faites simplement un tri par seau! N'a besoin que de 16 Go de RAM pour un nombre quelconque d'entiers 32 bits et s'exécute en O (n), ce qui devrait surpasser tous les systèmes distribués pour un n raisonnable, par exemple un milliard.

Une fois que vous avez la liste triée, il est trivial de choisir la médiane. En fait, vous n'avez pas besoin de construire la liste triée, mais il suffit de regarder les buckets.

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

Utiliser un fichier texte avec un milliard (10 ⁹ ) nombres et fonctionner avec timecomme ça

time ./median < billion

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

Curieusement, je pense que si vous avez suffisamment d'ordinateurs, vous feriez mieux de trier que d'utiliser O(n)des algorithmes de recherche de médiane. (À moins que vos cœurs ne soient très, très lents, j'en utiliserais simplement un et utiliserais un O(n)algorithme de recherche de médiane pour seulement 1e9 nombres; si vous aviez 1e12, cependant, cela pourrait être moins pratique.)

Quoi qu'il en soit, supposons que nous ayons plus de cœurs log n pour résoudre ce problème, et que nous ne nous soucions pas de la consommation d'énergie, nous obtenons simplement la réponse rapidement. Supposons en outre qu'il s'agit d'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 aveuglément en morceaux de taille égale et dit aux autres threads M de les trier. Ces fils le font avec diligence, à (n/M) log (n/M)temps. Ils renvoient ensuite non seulement leurs médianes, mais, disons, leurs 25e et 75e centiles également (les pires cas pervers sont meilleurs si vous choisissez des nombres légèrement différents). Vous disposez désormais de 4 millions de plages de données. Vous triez ensuite ces plages et travaillez vers le haut dans la liste jusqu'à ce que vous trouviez un nombre tel que, si vous supprimez chaque plage qui est plus petite ou contient le nombre, vous aurez jeté la moitié de vos données. C'est votre limite inférieure pour la médiane. Faites de même pour la limite supérieure. Cela prend quelque chose comme du M log Mtemps, et tous les cœurs doivent attendre, donc c'est vraiment gaspillageM^2 log Mtemps potentiel. Maintenant, votre thread unique dit aux autres de jeter toutes les données en dehors de la plage (vous devriez en jeter environ la moitié à chaque passage) et de répéter - c'est une opération trivialement rapide car les données sont déjà triées. Vous ne devriez pas avoir à répéter cela plus de log(n/M)fois avant qu'il ne soit plus rapide de simplement saisir les données restantes et d'utiliser un O(n)chercheur de médiane standard dessus.

Donc, la complexité totale est quelque chose comme O((n/M) log (n/M) + M^2 log M log (n/M)). Ainsi, c'est plus rapide que le O(n)tri médian sur un noyau 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 compte tenu de son inefficacité, mais c'est plus rapide.

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

- Algorithme de sélection distribuée des statistiques d'ordre - O (n)
Simplifie le problème au problème d'origine de trouver le kème nombre dans un tableau non trié.
- Comptage de l'histogramme de tri O (n)
Vous devez supposer certaines propriétés concernant la plage des nombres - la plage peut-elle tenir dans la mémoire? - Tri par fusion externe - O (n log n) - décrit ci-dessus
Vous triez essentiellement les nombres sur le premier passage, puis trouvez la médiane sur le second.
- Si l'on sait quelque chose sur la distribution des nombres, d'autres algorithmes peuvent être produits.

Pour plus de détails et la mise en œuvre, voir:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

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

Mais supposons qu'il y ait 100 ordinateurs. La seule chose complexe à faire est de trier la liste. Divisez-le en 100 parties, envoyez une partie à chaque ordinateur, laissez-les y être triées et fusionnez les parties après cela.

Ensuite, prenez le numéro du milieu de la liste triée (c'est-à-dire avec un index 5 000 000 000).

Cela dépend de vos données. Le pire des cas est qu'il s'agit de nombres uniformément distribués.

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

Supposons que vos nombres soient 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (la plage est 1-10) .

Nous créons 3 seaux: 1-3, 4-7, 8-10. Notez que le haut et le 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
• haut (5): 10, 10, 8, 9, 9, min 8, max 10

La moyenne tombe dans le seau du milieu, on ne tient pas compte du reste

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

Pour chaque nombre, nous comptons combien tombent dans le seau bas et haut, le max et le min, et gardons 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 la médiane directement: nous avons une situation comme celle-ci

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

donc la médiane est de 4,5.

En supposant que vous en savez un peu plus sur la distribution, vous pouvez affiner comment définir les plages pour optimiser la vitesse. Dans tous les cas, la performance doit aller avec O (N), car 1 + 1/3 + 1/9 ... = 1,5

Vous avez besoin de min et max à cause des cas extrêmes (par exemple, si la médiane est la moyenne entre le max de l'ancien bas et de 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 buckets dans chaque nœud, puis distribuer le bucket que vous conservez. Cela vous permet à nouveau d'utiliser le réseau efficacement car chaque numéro est passé en moyenne 1,5 fois (donc O (N)). Vous pouvez même battre cela si vous ne passez que les nombres minimaux entre les nœuds (par exemple, si le nœud 1 a 100 numéros et le nœud 2 a 150 numéros, alors le nœud 2 peut donner 25 numéros au nœud 1).

Sauf si vous en savez plus sur la distribution, je doute que vous puissiez faire mieux que O (N) ici, car vous devez en fait compter les éléments au moins une fois.

Une méthode plus simple consiste à avoir des nombres pondérés.

• Diviser le grand ensemble entre les ordinateurs
• Trier chaque ensemble
• parcourir le petit ensemble et calculer les poids des éléments répétés
• fusionner chaque 2 ensembles en 1 (chacun est déjà trié) en mettant à jour les poids
• continuez à fusionner des ensembles jusqu'à ce que vous n'obteniez qu'un seul ensemble
• Parcourez cet ensemble en accumulant des poids jusqu'à atteindre OneBillion / 2

Divisez les nombres 10 ^ 9, 10 ^ 7 sur chaque ordinateur ~ 80 Mo sur chacun. Chaque ordinateur trie ses numéros. Ensuite, l'ordinateur 1 fusionne-trie ses propres nombres avec ceux de l'ordinateur 2, de l'ordinateur 3 et 4, etc ... Puis l'ordinateur 1 écrit la moitié des nombres en 2, 3 à 4, etc. Puis 1 fusion trie les nombres d'ordinateurs 1,2,3,4, les écrit en retour. Etc. En fonction de la taille de la RAM sur les ordinateurs, vous pouvez vous en sortir en ne réécrivant pas tous les nombres sur les ordinateurs individuels à chaque étape, vous pourrez peut-être accumuler les nombres sur l'ordinateur 1 pendant plusieurs étapes, mais vous faites le calcul.

Oh, obtenez enfin la moyenne des valeurs 500000000th et 500000001st (mais vérifiez qu'il y a suffisamment de 00 là-dedans, je ne l'ai pas fait).

EDIT: @Roman - eh bien, si vous ne pouvez pas le croire même si c'est vrai, 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 l'intelligence 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 sera adaptable à une large gamme de tailles d'entrées et de nombres d'ordinateurs, et adaptable aux caractéristiques des ordinateurs et 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 min 45 s pour coder ma solution et la démarrer.

Mais j'admets volontiers que tout cela est une affirmation, je n'ai rien mesuré.

Cela pourrait être fait sur des nœuds en utilisant des données qui ne sont pas triées entre les nœuds (par exemple à 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 (): renvoie min, max et count
• compare (median_guess): renvoie la valeur de correspondance du nombre, le nombre inférieur à la valeur et le nombre supérieur à 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 binaire peut maintenant être effectuée de la manière suivante:

1. Bisectez les arrondis minimum et maximum vers le bas - il s'agit de la `` supposition '' médiane
2. Si le nombre supérieur à est supérieur au nombre inférieur à, définissez le minimum sur l'estimation
3. Si le nombre supérieur à est inférieur au nombre inférieur à, définissez le maximum sur la valeur
4. Si le nombre est impair, terminer lorsque le minimum et le maximum sont égaux
5. Si le nombre est même fini lorsque maximum <= minimum + guess.match_count Cela pourrait être fait sur les nœuds utilisant des données non triées (par exemple à 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 (): renvoie min, max et count
• compare (median_guess): renvoie la valeur de correspondance du nombre, le nombre inférieur à la valeur et le nombre supérieur à 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 binaire peut maintenant être effectuée de la manière suivante:

1. Bisectez les arrondis minimum et maximum vers le bas - il s'agit de la `` supposition '' médiane
2. Si le nombre supérieur à est supérieur au nombre inférieur à, définissez le minimum sur l'estimation
3. Si le nombre supérieur à est inférieur au nombre inférieur à, définissez le maximum sur la valeur
4. Si le nombre est impair, terminer lorsque le minimum et le maximum sont égaux
5. Si le nombre est pair, lorsque maximum <= minimum + guess.match_count

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

Faites-moi savoir si j'ai fait une erreur!

Que diriez-vous de ceci: - chaque nœud peut prendre 1 milliard / 100 numéros. À chaque nœud, les éléments peuvent être triés et la médiane peut être trouvée. Trouvez la médiane des médianes. nous pouvons, en agrégeant les nombres de nombres inférieurs à la médiane de la médiane sur tous les nœuds, trouver la division x%: y% que fait la médiane des médianes. Maintenant, demandez à tous les nœuds de supprimer les éléments inférieurs à la médiane des médianes (en prenant un exemple de 30%: 70% de fractionnement). 70% de 1 milliard équivaut à 700 millions. Désormais, tous les nœuds qui ont supprimé moins de 3 millions de nœuds peuvent renvoyer ces nœuds supplémentaires à un ordinateur principal. L'ordinateur principal se redistribue de telle manière que désormais tous les nœuds auront un nombre presque égal de nœuds (7 millions). Maintenant que le problème est réduit à 700 millions de nombres ... continue jusqu'à ce que nous ayons un ensemble plus petit qui peut être calculé sur un ordinateur.

Voyons d'abord comment trouver une médiane de n nombres sur une seule machine: j'utilise essentiellement une stratégie de partitionnement.

Problème: sélection (n, n / 2): Trouver le n / 2 ème nombre du plus petit nombre.

Vous choisissez par exemple l'élément central k et partitionnez les données en 2 sous-tableaux. le 1er contient tous les éléments <k et le 2ème contient tous les éléments> = k.

si sizeof (1er sous-tableau)> = n / 2, vous savez que ce sous-tableau contient la médiane. Vous pouvez ensuite jeter le 2ème sous-tableau. Résolvez ce problème de sélection (taille du 1er sous-tableau, n / 2) .

Dans le cas contraire, supprimez ce 1er sous-tableau et résolvez la sélection (2e sous-tableau, n / 2 - sizeof (1er sous-tableau))

Faites-le de manière récursive.

la complexité temporelle est le temps attendu O (n).

Maintenant, si nous avons beaucoup de machines, à chaque itération, nous devons traiter un tableau à diviser, nous distribuons le tableau en machines de diff. Chaque machine traite son morceau de tableau et renvoie le résumé à la machine de contrôle du concentrateur, c'est-à-dire la taille du premier sous-tableau et la taille du deuxième sous-tableau. Les machines à moyeu additionnent les résumés et décident quel sous-tableau (1er ou 2ème) traiter plus loin et 2ème paramètre de sélection et le renvoie à chaque machine. etc.

Cet algorithme peut être mis en œuvre très proprement à l'aide de la réduction de carte?

De quoi ça a l'air?

Je pense que la réponse de Steve Jessop sera la plus rapide.

Si la taille du transfert de données réseau est le goulot d'étranglement, voici une autre approche.

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

au début, tous les 100 travaillent pour trouver le nombre le plus élevé et le plus petit; chacun des ordinateurs a sa part de la base de données / du fichier qu'il interroge;

lorsque les nombres les plus élevés et les plus bas sont trouvés, un ordinateur lit les données et distribue chaque nombre, également, au reste des 99; les nombres sont distribués par intervalles égaux; (l'un peut prendre de -100 millions à 0, un autre - de 0 à 100 millions, etc.);

Lors de la réception des numéros, chacun des 99 ordinateurs les trie déjà;

Ensuite, il est facile de trouver la médiane ... Voyez combien de nombres a chaque ordinateur, ajoutez-les tous (la somme de combien de nombres il y a, pas les nombres eux-mêmes), divisez par 2; calculer dans quel ordinateur se trouve le nombre et à quel index;

:) voilla

PS On dirait qu'il y a beaucoup de confusion ici; le MEDIAN - est le NOMBRE AU MILIEU D'UNE LISTE DE NOMBRES TRIÉE!

Vous pouvez utiliser la méthode de l'arborescence des tournois pour trouver la médiane. Nous pouvons créer un arbre avec 1000 nœuds de sortie de sorte que chaque nœud de feuille soit un tableau. Nous menons ensuite n / 2 tournois entre les différents tableaux. La valeur à la racine après les n / 2 tournois est le résultat.

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

Si les nombres ne sont pas distincts et n'appartiennent qu'à une certaine gamme, c'est-à-dire qu'ils sont répétés, alors une solution simple qui me vient à l'esprit est de répartir les nombres entre 99 machines de manière égale et de garder une machine comme maître. Maintenant, chaque machine itère sur ses nombres donnés et stocke le nombre de chaque nombre dans un ensemble de hachage. Chaque fois que le nombre est répété dans l'ensemble de nombres attribués à cet ordinateur particulier, il met à jour son décompte dans l'ensemble de hachage.

Toutes les machines renvoient ensuite leur jeu de hachage à la machine maître. La machine maître combine les ensembles de hachage, additionnant le nombre de la même clé trouvée dans un ensemble de hachage. Par exemple, le jeu de hachage de la machine n ° 1 avait une entrée de ("1", 7) et le jeu de hachage de la machine n ° 2 avait une entrée de ("1", 9). ("1", 16), et ainsi de suite.

Une fois que les ensembles de hachage ont été fusionnés, triez simplement les clés, et maintenant vous pouvez facilement trouver le (n / 2) ème élément et le (n + 2/2) ème élément, à partir du jeu de hachage trié.

Cette méthode ne sera pas bénéfique si les milliards de nombres sont distincts.

Eh bien, supposons que vous sachiez que le nombre d'entiers distincts est (disons) de 4 milliards, alors vous pouvez les regrouper dans 64k buckets et obtenir un décompte distribué pour chaque bucket de chaque machine du cluster (100 ordinateurs). Combinez tous ces facteurs. Maintenant, recherchez le compartiment qui a la médiane, et cette fois ne demandez que des compartiments pour les 64 000 éléments qui se trouveraient dans votre compartiment cible. Cela nécessite des requêtes O (1) (spécifiquement 2) sur votre "cluster". :RÉ

Mon centime, après tout ce qui a déjà été soulevé par d'autres:

Trouver la médiane sur une seule machine est O (N): https://en.wikipedia.org/wiki/Selection_algorithm .

L'envoi de numéros N à 100 machines est également O (N). Donc, pour rendre l'utilisation de 100 machines intéressante, soit la communication doit être relativement rapide, soit N est si grand qu'une seule machine ne peut pas le gérer alors que N / 100 est faisable, soit nous voulons simplement considérer le problème mathématique sans nous soucier de communication de données.

Pour couper court, je suppose donc que, dans des limites raisonnables, nous pouvons envoyer / distribuer les chiffres sans affecter l'analyse d'efficacité.

Considérons alors l'approche suivante, où une machine est assignée pour être le "maître" pour un traitement général. Ce sera relativement rapide, de sorte que le «maître» participe également aux tâches courantes que chaque machine effectue.

1. Chaque machine reçoit N / 100 des nombres, calcule sa propre médiane et envoie cette information au maître.
2. Le maître compile une liste triée de toutes les médianes distinctes et la renvoie à chaque machine, définissant une séquence ordonnée de compartiments (sur chaque machine de la même manière), un pour chaque valeur médiane (un compartiment à valeur unique) et un pour chaque intervalle entre médianes adjacentes. Bien sûr, il existe également les compartiments inférieur et supérieur pour les valeurs inférieures à la médiane la plus basse et supérieures à la plus élevée.
3. Chaque machine calcule le nombre de nombres compris dans chaque compartiment et communique ces informations au maître.
4. Le maître détermine quel compartiment contient la médiane, combien de valeurs inférieures (au total) tombent en dessous de ce compartiment et combien au-dessus.
5. Si le compartiment sélectionné est un compartiment à valeur unique (l'une des médianes) ou si le compartiment sélectionné ne contient que 1 (N impair) ou 2 (N pair) valeurs, nous avons terminé. Sinon, nous répétons les étapes ci-dessus avec les modifications (évidentes) suivantes:
6. Seuls les numéros du bucket sélectionné sont (re) distribués du maître aux 100 machines, et de plus
7. Nous n'allons pas calculer (sur chaque machine) la médiane, mais la valeur k-ème, où nous prenons en compte le nombre de nombres plus élevés qui ont été écartés du total et le nombre de nombres inférieurs. Conceptuellement, chaque machine a également sa part des nombres faibles / élevés rejetés et en tient compte lors du calcul de la nouvelle médiane dans l'ensemble qui (conceptuellement) comprend (sa part) des nombres rejetés.

Complexité temporelle:

1. Un peu de réflexion vous convaincra qu'à chaque étape, le nombre total de valeurs à analyser est réduit d'un facteur au moins deux (2 serait un cas plutôt malade; vous pouvez vous attendre à une réduction nettement meilleure). De cela, nous obtenons:
2. En supposant que trouver la médiane (ou k-ème valeur), qui est O (N), prend c * N temps où le préfacteur c ne varie pas trop fortement avec N pour que nous puissions le prendre comme constante pour le moment, nous Nous obtiendrons notre résultat final dans au plus 2 * c * N / 100 fois. L'utilisation de 100 machines nous donne donc un facteur d'accélération de 100/2 (au moins).
3. Comme remarqué initialement: le temps nécessaire pour communiquer les numéros entre les machines peut rendre plus attrayant de simplement tout faire sur une seule machine. Cependant, SI nous optons pour l'approche distribuée, le nombre total de nombres à communiquer dans toutes les étapes ne dépassera pas 2 * N (N pour la première fois, <= N / 2 la deuxième fois, <= la moitié de celui troisième, et ainsi de suite).

1. Divisez le milliard de nombres en 100 machines. Chaque machine aura 10 ^ 7 numéros.

2. Pour chaque numéro entrant sur une machine, enregistrez le numéro dans une carte de fréquences, nombre -> compte. Enregistrez également le nombre minimum dans chaque machine.

3. Trouvez la médiane dans chaque machine: à partir du nombre minimum de chaque machine, additionnez les comptages jusqu'à ce que l'indice médian soit atteint. La médiane dans chaque machine, sera le env. inférieur et supérieur à 5 * 10 ^ 6 nombres.

4. Trouvez la médiane de toutes les médianes, qui sera inférieure et supérieure à env. 50 * 10 ^ 7 nombres, qui est la médiane de 1 milliard de nombres.

Maintenant une certaine optimisation de la 2ème étape: au lieu de stocker dans une carte de fréquence, stockez les comptes dans un tableau de bits variable. Par exemple: disons à partir du nombre minimum dans une machine, ce sont des comptages de fréquence:

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

Ce qui précède peut être stocké dans un tableau de bits comme:

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

Notez qu'au total, cela coûtera environ 10 ^ 7 bits pour chaque machine, puisque chaque machine ne gère que 10 ^ 7 nombres. 10 ^ 7bits = 1,25 * 10 ^ 6 octets, soit 1,25 Mo

Ainsi, avec l'approche ci-dessus, chaque machine aura besoin de 1,25 Mo d'espace pour calculer la médiane locale. Et la médiane des médianes peut être calculée à partir de ces 100 médianes locales, ce qui donne une médiane de 1 milliard de nombres.

Je suggère une méthode pour calculer approximativement la médiane. :) Si ces un milliard de nombres sont dans un ordre aléatoire, je pense que je peux choisir au hasard 1/100 ou 1/10 d'un milliard de nombres, les trier avec 100 machines, puis choisir la médiane d'entre eux. Ou divisons un milliard de nombres en 100 parties, laissez chaque machine choisir au hasard 1/10 de chaque partie, calculez la médiane d'entre eux. Après cela, nous avons 100 nombres et nous pouvons calculer la médiane du nombre 100 plus facilement. Juste une suggestion, je ne sais pas si c'est mathématiquement correct. Mais je pense que vous pouvez montrer le résultat à un gestionnaire pas très doué en mathématiques.

La réponse de Steve Jessop est fausse:

prendre en compte les quatre groupes suivants:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

La médiane est de 21, qui fait partie du deuxième groupe.

La médiane des quatre groupes est 6, 24, 30, 36, la médiane totale est de 27.

Ainsi, après la première boucle, les quatre groupes deviendront:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

Le 21 est déjà jeté à tort.

Cet algorithme ne prend en charge le cas que lorsqu'il y a deux groupes.