Si vous avez un milliard de chiffres et de, une centaine d'ordinateurs, quelle est la meilleure façon de localiser la médiane des nombres?
une solution que j'ai est: diviser le jeu de tout aussi parmi les 100 ordinateurs - trier - trouver les médianes pour chaque jeu. trier les jeux sur les médianes. fusionner deux ensembles à la fois en commençant à partir de la plus faible à la médiane la plus élevée.
si nous avons m1
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:
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, la 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 les e/S réseau 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.
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).
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.
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 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.
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).
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
