Calculer la médiane d'un milliard de chiffres

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

Un milliard de dollars est en fait tout à fait une tâche ennuyeuse pour un ordinateur moderne. Nous parlons de 4 GO d'une valeur de 4 octets entiers ici ... 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

Alors, ceci termine sur ma machine en moins de deux minutes (1:43 0:10 sont pour générer des nombres aléatoires) à l'aide d'un seul cœur et c'est encore de faire le tri. Rien de compliqué, vraiment.

C'est sûrement un travail intéressant pour les grands ensembles de nombres. Je veux juste faire un point ici: un milliard, c'est peanuts. Alors réfléchissez à deux fois avant de vous commencer à jeter des solutions complexes étonnamment simples tâches 😉

La médiane de cette série de nombres

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

est de 67 ans.

La médiane de cette série de nombres

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

est de 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 a la recherche d' (élément(499,999,999) + élément(de 500 000 000)) /2 (si les chiffres ont été triés). Aussi en supposant que tous les 100 ordinateurs étaient tous égaux.

à l'aide de mon ordinateur portable et GigE...

Ce que j'ai trouvé était que mon portable pouvez trier les 10 000 000 de Int32 de 1,3 secondes. Ainsi, une estimation approximative serait que d'un milliard de nombre pourrait prendre 100 x 1,3 secondes(2 minutes 10 secondes) ;).

Une estimation d'un transfert de fichier d'un fichier de 40 mo sur un réseau Ethernet gigabit est .32 secondes. Cela signifie que le tri des résultats de tous les ordinateurs seront retournés dans environ 32 secondes(ordinateur 99 n'a pas son dossier jusqu'à 30 secondes après le début). À partir de là, il ne devrait pas prendre longtemps pour jeter le plus bas 499,999,998 numéros, ajouter les 2 et diviser par 2.

Bizarrement, je pense que si vous avez assez d'ordinateurs, vous êtes mieux de tri que l'aide O(n) médiane de trouver des algorithmes. (À moins que vos cœurs sont très, très lent, mais, je voudrais simplement utiliser l'un et l'utilisation d'un O(n) médiane de l'algorithme de recherche pour le simple fait de 1e9 nombres; si vous aviez 1e12, cependant, que peut-être moins pratique.)

De toute façon, supposons que nous avons plus le journal de n noyaux pour faire face à ce problème, et nous ne se soucient pas de la consommation d'énergie, juste avoir une réponse rapide. Nous allons plus loin suppose que c'est une machine SMP avec toutes les données déjà chargées dans la mémoire. (Du soleil 32-core sont des machines de ce type, par exemple).

Un thread côtelettes de la liste jusqu'à l'aveuglette dans l'égalité des petits morceaux de la taille et dit à l'autre M threads pour les trier. Les discussions avec diligence le faire, dans (n/M) log (n/M) temps. Ils retournent ensuite non seulement leurs médianes, mais, disons, leur 25e et 75e percentiles ainsi (pervers pire des cas, sont mieux si vous choisissez des chiffres légèrement différents). Maintenant, vous avez 4M plages de données. Vous puis trier ces plages et du travail vers le haut par le biais de la liste jusqu'à ce que vous trouver un nombre tel que, si vous vous débarrassez de chaque gamme dont la taille est inférieure ou contient le nombre, vous aurez jeté la moitié de vos données. C'est votre limite inférieure pour la médiane. Faire de même pour la limite supérieure. Cela prend quelque chose comme M log M temps, et tous les cœurs avoir à attendre, donc c'est vraiment gaspiller M^2 log M de temps potentiels. Maintenant que vous avez votre seul thread dire aux autres, de jeter toutes les données en dehors de la plage (vous devriez jeter environ la moitié à chaque passage) et répète que c'est un trivialement opération rapide, puisque les données sont déjà triées. Vous ne devriez pas avoir à répéter cette plus de log(n/M) fois avant qu'il est plus rapide de saisir les autres données et l'utilisation d'un standard O(n) médiane finder sur elle.

Total de la complexité est quelque chose comme O((n/M) log (n/M) + M^2 log M log (n/M)). Ainsi, c'est plus rapide que O(n) médiane de tri sur un seul cœur 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 un très mauvaise idée compte tenu de la façon inefficace, il est, mais il est plus rapide.

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

- Les statistiques d'ordre distribué de sélection de l'algorithme O(n)

Simplifier le problème à l'origine de problème de trouver le k-ième nombre dans un tableau non trié.

- Comptage de tri histogramme O(n)

Vous avez à assumer certaines propriétés sur la plage des numéros de la plage de place dans la mémoire?
- Externe, de fusion et tri - O(n log n) - décrit ci-dessus

En gros, vous trier les nombres sur la première passe, puis de trouver la médiane sur la deuxième.

- Si rien n'est connu sur la distribution du nombre d'autres
les algorithmes peuvent être produites.

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

Une méthode plus simple est d'avoir des chiffres pondérés.

• Diviser le grand jeu parmi des ordinateurs
• Trier chaque jeu
• itérer sur les petites, et de calculer le poids d'éléments répétés
• de fusion de chacun des 2 jeux en 1 (chacun est triée déjà) la mise à jour des poids
• garder la fusion des listes jusqu'à ce que vous obtenez un seul ensemble
• itérer à travers ce jeu de l'accumulation des poids jusqu'à ce que vous atteignez OneBillion/2

Ce pourrait être fait des nœuds à l'aide de données qui ne sont pas triées dans l'ensemble des nœuds (disons à partir des 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 d'api:

• stats(): retourne min, max et le comte
• comparer(median_guess): retourne le comte de valeur correspondante, comptent moins de valeur et de compter plus de valeur

Le nœud parent appels 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é de la manière suivante:

1. Traversent, le minimum et le maximum d'arrondi vers le bas - c'est la médiane de "deviner"
2. Si la de plus de plus les moins de compter, au minimum pour le deviner
3. Si la plus grande que la quantité est inférieure à la moins de compter, mettre le maximum de la deviner
4. Si le nombre est impair terminer lorsque minimales et maximales sont égales
5. Si count est encore terminer lorsque au maximum <= minimum + deviner.match_count
   Ce pourrait être fait des nœuds à l'aide de données non triées (disons à partir des 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 d'api:

• stats(): retourne min, max et le comte
• comparer(median_guess): retourne le comte de valeur correspondante, comptent moins de valeur et de compter plus de valeur

Le nœud parent appels 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é de la manière suivante:

1. Traversent, le minimum et le maximum d'arrondi vers le bas - c'est la médiane de "deviner"
2. Si la de plus de plus les moins de compter, au minimum pour le deviner
3. Si la plus grande que la quantité est inférieure à la moins de compter, mettre le maximum de la deviner
4. Si le nombre est impair terminer lorsque minimales et maximales sont égales
5. Si count est encore terminer lorsque au maximum <= minimum + deviner.match_count

Si les stats() et de les comparer() peuvent être pré-calculées avec un O(N/Mlogn/M) trier, puis un O(N/M) pré-calcul avec une mémoire complexité de O(N) pour le pré-calcul. Alors que vous pourriez ne compare() en temps constant, de sorte que la chose entière (y compris les pré-calcul) permettrait de s'exécuter en O(N/MlogN/M)+O(logN)

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

Nous allons d'abord travailler sur la façon de trouver une médiane de n nombres sur une seule machine:
Je suis fondamentalement à l'aide de stratégie de partitionnement.

Problème :la sélection(n,n/2) : Trouver à n/2, le nombre de moins.

Vous pick-dire moyen de l'élément de k et les données de la partition en 2 sous-tableaux. le 1er contient tous les éléments < k et 2ème contient tous les éléments >= k.

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

Dans d'autre cas, se débarrasser de ce 1er subarray et résoudre de sélection(2e subarray , n/2 - sizeof(1er subarray))

Le faire de manière récursive.

complexité temporelle est O(n) temps prévu.

Maintenant, si nous avons beaucoup de machines, à chaque itération, nous avons à traiter un tableau à split, nous distribuer le tableau dans diff machines. Chaque processus de la machine de leur partie de tableau et envoie le résumé d'un centre de contrôle de la machine c'est à dire la taille de 1er subarray et la taille de la 2e subarray. Le hub machines ajoute des notes de synthèse et de décider qui subarray (1ère ou 2ème) pour traiter d'autres et 2ème paramètre de sélection et l'envoie à chaque machine.
et ainsi de suite.

Cet algorithme peuvent être appliquées très soigneusement à l'aide de la carte de réduire?

Comment est-il?

Je voudrais faire comme ceci:

au début, tous les 100 de travail pour trouver le plus haut et le plus petit nombre; chaque ordinateur a sa part de la base de données/fichier qui elle demande;

quand le plus haut et le plus bas numéros sont disponibles, un ordinateur lit les données, et distribue chaque numéro, également, pour le reste de l'99; les numéros sont distribués par des intervalles égaux; (on peut prendre à partir de -100 m à 0, l'autre - de 0 à 100 millions de dollars, etc);

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

Ensuite, il est facile de trouver la médiane... Voir combien de chiffres a chaque ordinateur, ajoutez-les tous (la somme de la façon dont beaucoup de chiffres, il y a, ne sont pas les chiffres eux-mêmes), diviser par 2; calculer dans lequel l'ordinateur est le nombre, et à l'index;

🙂 voilla

P. S. Semble qu'il y a beaucoup de confusion ici; la MÉDIANE est le NOMBRE AU MILIEU D'UNE LISTE DE NUMÉROS de!

Si les chiffres ne sont pas distincts, et seulement appartiennent à une certaine gamme, c'est qu'ils sont répétés, alors une solution simple qui me vient à l'esprit est de distribuer les numéros de 99 machines aussi, et de garder la machine en tant que maître. Maintenant, chaque machine effectue une itération sur ses chiffres donnés, et stocke le nombre de chaque nombre dans une table de hachage ensemble. Chaque fois que le nombre répété dans l'ensemble des numéros attribués à l'ordinateur, il met à jour son compte dans la table de hachage ensemble.

Toutes les machines de retourner les hachage ensemble de l'appareil maître. Le maître de la machine combine le hachage des ensembles, en additionnant le nombre de la même clé dans une table de hachage ensemble. Par exemple machine#1 de hachage de l'ensemble avait une entrée d' ("1",7), et la machine#2 de hachage de l'ensemble avait une entrée d' ("1",9), de sorte que le maître de la machine lorsque le peignage de la valeur de hachage d'ensembles rend une entrée d' ("1", 16), et ainsi de suite.

Une fois que le hachage de jeux ont été fusionnés, puis il suffit de trier les clés, et vous pouvez maintenant trouver facilement l' (n/2)ème élément et le (n+2/2)ème élément, de la triés hachage ensemble.

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

Mon sou vaut la peine, après tout ce qui a déjà été évoqué par d'autres:

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

L'envoi de N nombres de 100 machines est également en O(N). Ainsi, afin de rendre l'utilisation de 100 machines intéressant, la communication doit être relativement rapide, ou N est si grande qu'une machine ne peut pas gérer tout en N/100, c'est faisable, ou nous voulons considérer le problème mathématique, sans vous soucier des datacommunication.

Supprimer des choses, bref, je vais donc supposer que, dans des limites raisonnables, nous pouvons envoyer ou de distribuer les numéros sans affecter l'efficacité de l'analyse.

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

1. Chaque machine reçoit N/100 du nombre, calcule sa propre médiane et envoie cette information au maître.
2. Le maître compile une liste triée de tous distincts les médianes et les envoie à chaque machine, la définition d'une séquence ordonnée de segments (sur chaque machine, le même), un pour chaque valeur médiane (une seule valeur seau) et un pour chaque intervalle entre les médianes. Bien sûr, il y a aussi le bas de gamme et haut de gamme de seaux pour les valeurs au-dessous de la plus basse à la médiane et au-dessus de la plus haut.
3. Chaque machine calcule le nombre de numéros de tomber dans chaque compartiment et communique les informations pour le maître.
4. Le maître détermine le seau contient la médiane, combien de valeurs plus faibles (au total) tombent en dessous de ce seau, et combien de ci-dessus.
5. Si le seau est une valeur unique seau (l'une des médianes) orelse sélectionnés seau ne contient que des 1 (N impair) ou 2 (N) les valeurs que nous aurons terminé. Sinon, nous répétez les étapes ci-dessus avec la suivante (évident) modifications:
6. Seulement les numéros à partir du seau sont (re)distribués par le maître de l'100 machines, et de plus
7. Nous n'allons pas calculer (sur chaque machine) de la médiane, mais le k-ième valeur, où l'on tient compte de la façon dont de nombreux numéros les plus élevés ont été écartés du total, et combien de numéros les plus bas. Conceptuellement, chaque machine a également sa part de la jetée haut/bas de numéros et en tienne compte lors du calcul de la nouvelle médian dans le jeu (conceptuellement) comprend (sa part) les rebuts de nombres.

Temps-la complexité:

1. Un peu de réflexion, vous convaincra que sur chaque étape le nombre total de valeurs à analyser est réduite par un facteur d'au moins deux (2 serait malade de cas; vous pouvez vous attendre de l'amélioration significative de réduction). De là, nous obtenons:
2. En supposant que la recherche de la médiane (ou k-ième valeur), qui est O(N), prend c*N temps où le préfacteur c ne varie pas trop violemment avec N de sorte que nous pouvons la considérer comme une constante pour le moment, nous allons obtenir notre résultat final en au plus 2*c*N/100 du temps. L'utilisation de 100 machines nous permet, par conséquent, un facteur d'accélération de 100/2 (au moins).
3. Comme l'a remarqué dans un premier temps: le temps de communiquer les chiffres entre les machines peuvent le rendre plus attrayant pour les tout simplement tout faire sur une seule machine. Cependant, SI nous allons de l'approche distribuée, le nombre total de numéros à être communiquée à toutes les étapes ne dépassera pas 2*N (N pour la première fois, <=N/2, la deuxième fois, <= la moitié de celle du troisième, et ainsi de suite).

Je suggère une méthode pour calculer la Médiane. 🙂 Si ces milliards de nombres dans un au hasard l'ordre, je pense que je peux le prendre 1/100 et 1/10 d'un milliard de nombre au hasard, de les trier avec machine à 100, puis choisissez la médiane d'entre eux. Ou laissez-la scission de milliards de chiffres dans 100 parties, de laisser chaque machine pick 1/10 de chaque partie au hasard, calculer la médiane d'entre eux. Après que nous avons 100 chiffres, et nous pouvons calculer la médiane de l'100 nombre plus facile. Juste une suggestion, je ne sais pas si c'est mathématiquement correct. Mais je pense que vous pouvez afficher le résultat d'un pas-si-bon-à-math manager.