Calculer la médiane d'un milliard de chiffres
Si vous avez un milliard de chiffres et de, une centaine d'ordinateurs, quelle est la meilleure façon de localiser la médiane de ces nombres?
Une solution que j'ai est:
- Diviser l'ensemble de manière égale entre les ordinateurs.
- Les trier.
- Trouver les médianes de chaque ensemble.
- Trier les jeux sur les médianes.
- De fusionner deux ensembles à la fois à partir de la plus faible à la plus forte moyenne.
Si nous avons m1 < m2 < m3 ...
puis la première fusion Set1
et Set2
et dans l'ensemble, nous pouvons jeter tous les nombres inférieurs à la médiane de Set12
(fusionné). Donc, à tout point de temps, nous avons l'égalité de taille fixe. En passant, cela ne peut pas être fait en parallèle. Des idées?
- sont les milliards de nombres triés?
- Boker: en fait, le problème se compose de deux sous-problèmes: 1) trier la liste et 2) obtenir de l'élément d'indice 5'000'000'000. J'ai peine à croire que les chiffres sont triés.
- Est-ce devoirs, une question d'entrevue, ou juste de la curiosité?
- C'est une question d'entrevue trouvé sur un site
- le problème n'a pas besoin composé de deux sous-problèmes que vous décrivez, par exemple quickselect. Mais quickselect n'est pas paralléliser, au moins pas de façon triviale. Et bien sûr, vous avez raison, si les numéros sont pré-triés, c'est une jolie question inutile.
- Je ne pense pas qu'un pays de langue anglaise utilise le long milliards de dollars en anglais pour toutes fins officielles. Par exemple, ici au royaume-UNI, nous avons cessé de l'utiliser en 1974. Je considère l'utilisation de "milliards de dollars", au sens d'un million de millions, dans la langue anglaise pour être un pervers de la question de tour, pas un "vrai milliards de dollars" à tous. Des cours de français, ce serait une question totalement différente, mais la question n'est pas en français.
- J'ai d'autre part imediatly visualiser un milliard de dollars comme étant un "million" comme vous l'avez dit. Je suis européen, donc je suppose que c'est logique
- Oui, si j'étais à parler le français (dont je n'ai pas fait depuis très longtemps, et de mal, même à l'époque), ou de toute autre langue Européenne je ne doute pas faire l'inverse erreur tout le temps, en disant: "milliards de dollars" pour "milliard". Donc sur la deuxième pensées, il n'est pas forcément un truc à utiliser des "milliards de dollars" pour les "millions" en anglais, c'est peut-être difficile à éviter l'erreur de traduction. Ma réaction serait plus adapté dirigé vers les locuteurs de l'anglais tente de revenir à l'époque où nous avons utilisé la "bonne" des milliards et des Britannia a statué sur les vagues 😉
- Vous n'avez pas besoin de les trier! en.wikipedia.org/wiki/...
- Belle question! Pouvez-vous partager le site où vous avez trouvé la question?
- 1 milliard de dollars de chiffres n'est qu'à quelques gigaoctets de données, vous n'avez pas besoin de plusieurs Ordinateurs ni des algorithmes complexes pour résoudre cette tâche. Ne pas compliquer.
- questions obligatoires: 1) où les nombres sont stockés? 2) définir le "meilleur moyen"
- Ca me rappelle un Google les questions de l'entrevue...
- cs.stackexchange.com/questions/1914/...
- si vous voulez juste pour "localiser" il, de l'utilisation de l'échantillonnage et un ordinateur...
- ce type de numéros, cela fait une différence si ces juste des entiers, ou un écorchement numéros .. etc.
- Avez-vous considéré l'utilisation de GPU computing? Les gpu sont exceptionnellement bons à faire ce que vous voulez.
- Plusieurs machines peuvent communiquer avec un temps de latence faible par rapport à l'échéance prévue, ce qui semble pleurer pour un sur la ligne de l'algorithme: distribuer les données (un sujet à méditer dans son propre droit: imaginez l'entrée "ordonna presque"), des échanges d'après les estimations actuelles (par sous-ensemble/machine), la médiane de chaque maintenant et puis (serait probablement aller pour une séquence de Fibonacci pour l'enfer de celui-ci), il suffit de compter les valeurs aberrantes au risque de devoir recommencer (avec plus de connaissances sur la distribution de la valeur).
- Je ne pense pas que c'est vrai. Ce problème a incroyablement faible densité de calcul. Les gpu sont bien à l'opposé de la nature de la tâche.
- Si c'était "continental" des milliards (10^12), alors il serait maladroit de les stocker (en supposant que int32 chiffres, ce serait un 4 TO fichier juste pour les chiffres). De toute façon, étant dans le domaine des questions théoriques, cette question devrait être "Comment trouver la médiane d'un ridicule quantité d'articles?(sans tenir compte des détails de bas niveau)"
- vous êtes de droite. J'ai oublié le calcul médian eu une forte dépendance de données. Mon mauvais.
Vous devez vous connecter pour publier un commentaire.
Ah, mon cerveau vient de s'activèrent, j'ai une suggestion sensée maintenant. Probablement trop tard, si cela avait été une entrevue, mais jamais l'esprit:
De la Machine 1 est appelé le "contrôle de la machine", et pour la clarté de l'exposé, soit il commence avec toutes les données, et l'envoie dans l'égalité des colis pour les 99 autres machines, ou, sinon, les données commencent à être réparties entre les machines, et il envoie 1/99 de ses données à chacun des autres. Les partitions n'ont pas à être égaux, il suffit de fermer.
Chaque autre machine trie les données, et le fait d'une manière qui favorise trouver les valeurs plus faibles en premier. Ainsi, par exemple un tri rapide, toujours de tri de la partie inférieure de la partition de la première[*]. Il écrit ses données vers la machine de contrôle dans l'ordre croissant dès qu'il le peut (à l'aide asynchrone IO, de manière à continuer le tri, et probablement avec Nagle sur: expérimenter un peu).
Le contrôle de la machine effectue un 99-voie de fusion sur les données qu'elle arrive, mais supprime les données fusionnées, en gardant juste de compter le nombre de valeurs qu'il a vu. Il calcule la médiane, la moyenne de la 1/2 milliardième et 1/2 milliard de plus oneth valeurs.
Cette souffre de la "plus lente dans le troupeau" problème. L'algorithme ne peut pas complète jusqu'à ce que chaque valeur inférieure à la médiane a été envoyé par une machine de tri. Il y a une chance raisonnable que l'une de ces valeurs sera assez élevé au sein de sa parcelle de données. Donc, une fois le partitionnement des données est terminée, durée estimée est la combinaison du temps de tri 1/99e des données et de l'envoyer à l'ordinateur de contrôle, et le temps pour le contrôle de lire 1/2 les données. La "combinaison" est quelque part entre le maximum et la somme de ces moments, sans doute proche du max.
Mon instinct me dit que pour l'envoi de données sur un réseau pour être plus rapide que le tri (laissez simplement en sélectionnant la médiane), il doit être sacrément rapide du réseau. Peut-être un meilleur prospect si le réseau peut être supposé instantané, par exemple, si vous avez 100 cores avec l'égalité d'accès à la RAM contenant les données.
Depuis le réseau I/O est susceptible d'être la limite, il pourrait y avoir quelques trucs que vous pouvez jouer, au moins pour les données de revenir à la machine de contrôle. Par exemple, au lieu de les envoyer "1,2,3,.. 100", peut-être une machine de tri pourrait envoyer un message signifiant "100 valeurs de moins de 101". Le contrôle de la machine pourrait alors effectuer une modification de la fusion, dans lequel il trouve le moins de tous ceux qui sont haut-de-gamme de valeurs, puis il dit à toutes les machines de tri de ce qu'il était, afin qu'ils puissent (a) indiquer le contrôle de la machine combien de valeurs "compter" en dessous de cette valeur, et (b) la reprise de l'envoi de leurs données triées à partir de ce point.
Plus généralement, il y a probablement un savant défi-réponse de la devinette que le contrôle de la machine peut jouer avec les 99 machines de tri.
Cela implique des allers-retours entre les machines, bien que, qui ma plus simple première version évite. Je ne sais pas vraiment comment l'aveugle-estimation de leurs performances relatives, et, puisque les échanges sont complexes, j'imagine qu'il ya beaucoup de meilleures solutions que rien de ce que je vais penser à moi-même, en supposant que c'est toujours un réel problème.
[*] disponible pile le permet - le choix de la partie à faire en premier est limité si vous n'avez pas de O(N) de l'espace supplémentaire. 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 à couper quelques virages, en faisant la petite partie de la première pour la première quelques partitions.
parallel
time
de commande appliquée à l'ensemble du pipeline, il a fallureal=36m24s
("horloge murale temps"),user=113m15s
(parallèle"le temps", tous les cœurs ajouté). La plus longue de commande, loin devant les autres, étaitsort
, même si elle filetée pour mes quatre cores à 100%. La consommation de RAM est très acceptable.Je déteste être le contrarian ici, mais je ne crois pas que le tri est obligatoire, et je pense que n'importe quel algorithme impliquant le tri d'un milliard de dollars/100 numéros est lente. Considérons un algorithme sur un ordinateur.
1) Sélectionnez 1000 valeurs au hasard à partir de l'milliards de dollars, et les utiliser pour obtenir une idée de la répartition des nombres, en particulier une gamme.
2) au Lieu de trier les valeurs, de les affecter à des seaux basé sur la distribution que vous venez de calculer. Le nombre de compartiments est choisi de sorte que l'ordinateur peut traiter de manière efficace, mais qui ne devrait pas être aussi grande que la pratique. Le seau plages devraient être environ le même nombre de valeurs d'aller dans chaque seau (ce n'est pas critique pour l'algorithme, mais il permet d'efficacité. De 100 000 seaux pourrait être approprié). Remarque le nombre de valeurs dans chaque seau. C'est un O(n) processus.
3) de Trouver lequel seau de plage de la médiane se situe. Cela peut être fait simplement en examinant le nombre total de personnes dans chaque seau.
4) Trouver le médian en examinant les valeurs dans ce seau. Vous pouvez utiliser une sorte ici si vous le voulez, puisque vous êtes seulement de tri peut-être 10 000 numéros. Si le nombre de valeurs dans ce seau est grand, alors vous pouvez utiliser cet algorithme de nouveau jusqu'à ce que vous avez un assez petit nombre de trier.
Cette approche parallelizes trivialement en divisant les valeurs entre les ordinateurs. Chaque ordinateur rapports les totaux de chaque compartiment à un "contrôle" de l'ordinateur qui ne l'étape 3. Pour l'étape 4 de chaque ordinateur envoie le (tri) des valeurs dans le seau pour le contrôle de l'ordinateur (vous pouvez faire ces deux algorithmes en parallèle aussi, mais il n'est probablement pas la peine).
Le processus total est O(n), puisqu'à la fois les étapes 3 et 4 sont triviales, à condition que le nombre de compartiments est assez grand.
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.
Sortie sur ma machine:
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 😉
(numbers[numbers.length / 2]+numbers[numbers.length / 2+1])/2
sinumbers.length
est encore etnumbers[numbers.length / 2]
seulement sinumbers.length
est impair.La estimation de statistiques d'ordre comme la médiane et le 99e percentile peuvent être distribuées de manière efficace avec des algorithmes comme t-digest ou Q-digest.
Soit à l'aide de l'algorithme, chaque nœud génère un résumé, qui représente la distribution des valeurs stockées localement. Les recueils sont collectées à un seul nœud, fusionné (en fait, en additionnant les distributions), et la médiane ou de tout autre percentile peut ensuite être recherché.
Cette approche est utilisée par elasticsearch et, sans doute, BigQuery (en fonction de la description de la fonction QUANTILE).
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.
a*(1e7)log(1e7) = 1.3sec
=>a = 1.6e-9sec
=>a*(1e9)log(1e9) ~ 167sec
, de sorte que votre estimation n'était pas éteint.Cela pourrait en surprendre plus d'un, mais si les nombres sont des entiers assez petit pour s'adapter à l'intérieur de 32 bits (ou plus) - il suffit de faire un seau de tri! A seulement besoin de 16GO de ram pour un nombre de 32 bits ints et s'exécute en O(n), ce qui devrait surpasser tout les systèmes distribués raisonnables de n, par exemple, un milliard de dollars.
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 seulement en regardant les seaux doivent le faire.
Une mise en œuvre simple est illustré ci-dessous. Ne fonctionne que pour des entiers de 16 bits, mais l'extension à 32 bits devrait être facile.
À l'aide d'un fichier texte avec un milliard de dollars (109) le nombre et la course avec
time
commedonne un temps de fonctionnement de ma machine 1m49.293s. La plupart du temps d'exécution est probablement d'e /s disque aswell.
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'unO(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 commeM log M
temps, et tous les cœurs avoir à attendre, donc c'est vraiment gaspillerM^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 delog(n/M)
fois avant qu'il est plus rapide de saisir les autres données et l'utilisation d'un standardO(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 queO(n)
médiane de tri sur un seul cœur siM >> log(n/M)
etM^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.
M
sont les variables qui peuvent évoluer de manière arbitraire, de sorte que l'on comprend à la fois. En particulier, j'ai postulé queM
>log n
, ce qui signifie que si vous vous souciez qu'il estn log n
au lieu de simplementn
, vous avez des soins à ce sujetM
aussi.Un ordinateur est plus que suffisant pour résoudre le problème.
Mais supposons qu'il ya 100 ordinateurs. La seule chose complexe que vous devez faire est de trier la liste. Diviser pour 100 parties, en envoyer une partie à chaque ordinateur, qu'ils soient triés là, et de fusionner les parties après que.
Alors prenez le nombre à partir du milieu de la liste triée (c'est à dire avec un indice de 5 000 000 000).
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
Cela dépend de vos données. Le pire scénario est que c'est distribuée de manière uniforme numéros.
Dans ce cas, vous pouvez trouver la médiane en O(N) le temps comme dans cet exemple:
Supposons que vos numéros sont 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (la plage va de 1 à 10).
Nous créer 3 seaux: 1 à 3, 4 à 7, 8 à 10. Notez que le haut et le bas ont taille égale.
Nous remplir les seaux avec les chiffres, compter combien tombent dans chaque, le max et le min
La moyenne tombe au milieu d'un seau, nous négligeons le reste
Nous créer 3 seaux: 4, 5-6, 7. Bas va commencer avec un nombre de 5 et avec un max de 3 et de haute avec un minimum de 8 et un nombre de 5.
Pour chaque numéro, nous comptons combien tombent dans le bas et le haut du seau, le max et le min, et de garder le milieu seau.
Maintenant, nous pouvons calculer la médiane directement: nous avons une situation comme celle-ci
donc la médiane est de 4,5.
En supposant que vous savez un peu plus sur la distribution, vous pouvez affiner la façon de définir les plages, pour optimiser la vitesse. Dans tous les cas, la performance devrait aller avec O(N), parce que 1 + 1/3 + 1/9... = 1.5
Vous avez besoin de min et de max, car des cas limites (par exemple, si la médiane est la moyenne entre le max de vieux bas et l'élément suivant).
L'ensemble de ces opérations peut être parallélisée, vous pouvez donner à 1/100 de données à chaque ordinateur et de calculer les 3 compartiments dans chaque nœud, puis de distribuer le seau que vous gardez. Cela montre que vous utilisez le réseau de manière efficace parce que chaque numéro est passé en moyenne 1,5 fois (donc O(N)). Vous pouvez gagner même si vous ne vous passe 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, puis le nœud 2 peut donner les numéros 25 à nœud 1).
À moins que vous en savez plus sur la distribution, je doute que vous pouvez faire mieux que O(N) ici, parce que vous avez réellement besoin de compter les éléments au moins une fois.
O(n log n)
dans ce cas. Est-il judicieux ? En passant, j'aime bien ton idéeo(n)+o(n/3)+o(n/9)+...
qui est encoreo(n)
et paso(n log n)
.o(n)
dans ce cas, avec la naïveté de partitionnement.Une méthode plus simple est d'avoir des chiffres pondérés.
Split 10^9, 10^7 pour chaque ordinateur ~ 80 MO sur chaque. Chaque ordinateur sortes de ses effectifs. Puis l'ordinateur 1 fusion-trie ses propres chiffres avec ceux de l'ordinateur 2, ordinateur 3 et 4, etc ... Puis de l'ordinateur 1 écrit de la moitié des chiffres de 2, de 3 à 4, etc. Puis 1 fusion trie les numéros à partir d'ordinateurs 1,2,3,4, écrit en arrière. Et ainsi de suite. En fonction de la taille de la RAM sur les ordinateurs, peut-être s'en tirer avec ne pas écrire tous les nombres de retour pour les ordinateurs individuels à chaque étape, vous pourriez être en mesure d'accumuler les chiffres sur l'ordinateur 1 pour plusieurs étapes, mais vous ne les mathématiques.
Oh, enfin obtenir la moyenne de la 500000000th et 500000001st valeurs (mais à vérifier il y a assez de 00s là, je n'ai pas).
EDIT: @Romain -- eh bien, si vous ne pouvez pas le croire, même s'il est vrai, alors il n'y a aucun point dans mon révéler la vérité ou de la fausseté de la proposition. Ce que je voulais dire à l'état a été que la force brute, parfois, beats smart dans une course. Il m'a fallu environ 15 secondes pour concevoir un algorithme qui je suis confiant que je peux mettre en œuvre, ce qui fonctionne, et qui sera adaptable à un large éventail de tailles d'entrées et le nombre d'ordinateurs et réglable pour les caractéristiques des ordinateurs et des modalités de travail en réseau. Si il vous prend, ou quelqu'un d'autre, disons de 15 minutes, afin de concevoir un algorithme plus évolué, j'ai un 14m45s avantage de code ma solution et de commencer à courir.
Mais je reconnais volontiers c'est tous affirmation, je n'ai pas mesuré quoi que ce soit.
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:
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:
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:
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:
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!
Comment à ce sujet:- chaque nœud peut prendre de 1 milliard de dollars/100 numéros. À chaque nœud, les éléments peuvent être triés et médiane peut être trouvé. Trouver la médiane des médianes. nous pouvons, en agrégeant les chiffres des nombres inférieurs à la médiane de la médiane sur tous les nœuds de trouver x%:y% split qui de la médiane-de-médianes fait. Maintenant, demandez à tous les nœuds pour supprimer des éléments de moins que la médiane des médianes( en prenant exemple de 30%:70% split).30% les chiffres sont supprimés. 70% de 1 milliard de dollars est 700million. Maintenant, tous les nœuds qui supprimés à moins de 3 millions d'nœuds peuvent envoyer ces nœuds supplémentaires retour à un ordinateur principal. L'ordinateur principal redistribue de manière que tous les nœuds ont presque le même nombre de nœuds(7million). Maintenant que le problème est réduit à 700million numéros.... continue jusqu'à ce que nous avons un plus petit ensemble qui peut être calculée sur une comp.
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 pense que Steve Jessop la réponse sera la plus rapide.
Si le réseau de transfert de données taille est le goulot d'étranglement, voici une autre approche.
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!
Vous pouvez utiliser le tournoi de l'arbre méthode pour trouver la médiane.
Nous pouvons créer un arbre avec 1000 congé de nœuds tel que chaque nœud feuille est un tableau.
Ensuite, nous menons n/2 tournois entre les différents tableaux.La valeur de la racine après le n/2 tournois en est le résultat.
http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
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.
Eh bien, supposons que vous savez que le nombre d'entiers distincts est (dire) de 4 milliards de dollars, alors vous pouvez seau en 64 ko de seaux et d'obtenir un système distribué, le nombre de chaque compartiment à partir de chaque ordinateur du cluster(100 ordinateurs). Combiner tous ces chiffres. Maintenant, trouver le seau qui a de la médiane, et cette fois seulement demander des seaux pour le 64 ko éléments qui se trouvent dans votre cible seau. Cela nécessite O(1) (en particulier 2) des requêtes sur votre "cluster". 😀
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.
Temps-la complexité:
Diviser le 1 milliards de chiffres dans 100 machines. Chaque machine dispose de 10^7 numéros.
Pour chaque numéro entrant à une machine, store le nombre, la fréquence de la carte,
nombre -> count. Aussi stocker le nombre minimum de chaque machine.
Trouver médian dans chaque machine: à partir de min nombre dans chaque machine, somme comtes jusqu'à l'indice médian est atteint. La médiane de chaque machine, ce sera l'env. moindre et plus de 5*10^6 numéros.
Trouver la médiane de tous les médianes, qui sera moindre et plus de env. 50*10^7 numéros, qui est la médiane de 1 milliard de dollars de chiffres.
Maintenant, certains d'optimisation de la 2ème étape: au Lieu de les stocker dans une carte fréquence, store le nombre de comptes dans une variable tableau de bits. Par exemple: Permet de dire à partir de min nombre dans une machine, ce sont le nombre de fréquences:
Ci-dessus peuvent être stockées dans le tableau de bits que:
Remarque que, globalement, il en coûtera environ 10^7 bits pour chaque machine, car chaque machine ne gère que 10^7 numéros. 10^7bits = 1.25*10^6 octets, ce qui est de 1,25 MO
Donc, avec l'approche ci-dessus chaque machine devra 1.25 MO d'espace pour calculer les locaux de la médiane. Et la médiane des valeurs moyennes peuvent être calculées à partir de ces 100 locaux médianes, résultant en une médiane de 1 milliard de dollars de chiffres.
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.
Steve Jessop la réponse est fausse:
considérer 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, ce qui est contenu dans le second groupe.
La médiane des quatre groupes sont de 6, 24, 30, 36, Le total médian 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 sont déjà jetés à tort.
Cet algorithme en charge uniquement le cas lorsqu'il y a deux groupes.