Tri énorme Nombre d'Entiers à partir du disque dur
Compte tenu de 100 GO de Données entier sur Disque Dur avec la RAM d'un montant de 2 GO, comment faire pour trier les nombres entiers avec le minimum d'opération de disque. Ici, chercher de l'un certain nombre de disque est considéré comme une opération de disque( même si, en réalité un bloc de données peut être récupérée).
Nous pouvons utiliser l'espace supplémentaire sur le disque pour le stockage temporaire et pas besoin de considérer que les opérations de nettoyage des espaces temporaires utilisés.
est-ce un genre de Devoirs? et mettre un peu de code que vous avez essayé ?
double possible de Comment faire pour trier les 100 GO de dollars de chaînes de caractères.
Voir aussi stackoverflow.com/questions/134158/... et stackoverflow.com/questions/3961245/...
Non ce n'est pas de devoirs 🙂
De quelle taille sont les entiers?
double possible de Comment faire pour trier les 100 GO de dollars de chaînes de caractères.
Voir aussi stackoverflow.com/questions/134158/... et stackoverflow.com/questions/3961245/...
Non ce n'est pas de devoirs 🙂
De quelle taille sont les entiers?
OriginalL'auteur Shamim Hafiz | 2010-10-25
Vous devez vous connecter pour publier un commentaire.
Que d'autres personnes ont noté, vous pouvez utiliser un O(n) comptage de tri. Toutefois, il existe quelques problèmes supplémentaires que vous devez considérer. Nous allons supposer que vous êtes stocker des nombres entiers de 32 bits, donc 100 GO ~ 27e9 ints.
Si tous les nombres entiers sont les mêmes, alors il va se produire ~27e9 fois, ce qui est plus grand qu'un 32 bits int. Donc vos compteurs devront être les entiers 64 bits.
Avec 2 go de RAM, vous ne pouvez stocker qu' ~125e6 compteurs dans la mémoire RAM à la fois. Si nous ne pouvons pas faire d'hypothèses sur la distribution des nombres entiers, il nous faudrait:
Je pense que la dernière est la meilleure option. Depuis nous avons besoin d' ~4e9 64 bits compteurs et ne peut stocker 2 GO, nous aurions besoin de courir à travers l'ensemble de la matrice ~16 fois. La première option est clairement pas bon si l'on considère la rencontre d'une séquence d'entiers tels que 0,1<<31,0. Ces compteurs ne seraient pas stockées dans la mémoire RAM dans le même temps, et donc au moins 2 HD écrit sont nécessaires.
À cause de cela, je pense à la taille de votre problème (100 GO), un N-way merge serait mieux, car cela ne ferait qu'exigent la lecture de l'ensemble de la matrice log_2(100) ~ 8 fois.
Cependant, si l'intervieweur immédiatement changé la question de "10TB tableau, toujours 2 GO de RAM", puis le comptage, le tri serait facile de gagner.
OriginalL'auteur Dijkstra
Puisque les données triées est de type entier (4 octets) et la quantité de données est de 100 GO (où GO est de 2^30), vous auriez 26,843,545,600 entiers à trier. Puisque vous avez 4,294,967,296 possible des valeurs entières, vous pouvez représenter ces données sous forme de tableau de longs qui servent de compteurs, qui consommerait environ 34 GO d'espace disque. Lire à travers les 100 GO de données à la fois, l'incrémentation des compteurs individuels pour chaque valeur entière (300 GO de disque totale de l'accès à la lecture de la valeur, de lire le compteur, écrire le compteur incrémenté), puis de lire les compteurs dans l'ordre, l'écriture, le nombre de valeurs que vous lisez de chaque valeur (134 GO au total accès au disque).
Ce serait de trier les données en utilisant un total de 434 GO d'accès au disque. Si vous utilisez de la RAM pour stocker une partie de la gamme de valeur entière compteurs, vous pourrait techniquement inférieur à l'amt d'accès au disque encore plus.
Il y a 2^32 nombres entiers de 32 bits, et 8 octets de long, alors qu'il faudrait exactement 32 GO (où GO est de 2^30) pour stocker tous les compteurs. Cependant, chaque compteur exige seulement 35 bits pour stocker jusqu'à 26,843,545,600, de sorte que vous besoin de 2^32*35/8 octets, ou en vertu de 18GB de tenir les compteurs. En outre, vous pouvez utiliser votre 2 GO de RAM pour le cache fréquemment utilisés compteurs, la réduction de votre utilisation du disque encore plus.
Oui, le maintien de certaines valeurs dans la mémoire permettrait également d'améliorer la performance. Une autre possibilité pourrait être de fait garder les compteurs en mémoire jusqu'à ce que nous arrivons à un point où nous ne serons pas en mesure d'accueillir tout plus. Dans ce cas, nous rincer ces et mettre à jour les compteurs sur le disque.
Je crains que dans ce cas, l'accès au disque doit être mesurée en nombre d'accès et pas que de la circulation (bien que le trafic pourrait être aussi énorme). Les disques durs est horrible temps de recherche, et les disques Ssd ne sont pas largement utilisées (et de leur faible vitesse d'écriture).
Je pense que ce serait terriblement lent si vous avez à lire/écrire pour le HD pour chaque entier. Comme Gabe dit, la mise en cache permettrait d'améliorer les résultats, mais si vous avez seulement 2 GO de RAM, vous n'réduire de moitié le nombre de lecture/écriture à la HD (~5e10). Je pense que le fait d'avoir 2 go de tableau de int64 des compteurs de RAM (car on pourrait avoir le même nombre 26e9 fois) et de balayage à travers le HD 100 fois, en ignorant les entiers qui ne sont pas dans les limites du tableau, serait plus rapide. Bien sûr, si vous savez quelque chose à propos de la distribution des nombres entiers, on pourrait améliorer davantage.
OriginalL'auteur Mark Synowiec
Pour moi la réponse à cette question dépend cruically sur la distribution attendue des chiffres dans le fichier.
Il y a de 12,5 Milliards de dollars ints à 100 go de données int.
Il y a aussi ~4,3 Milliards de dollars distinctes ints.
Donné une distribution parfaitement uniforme à travers tous les possibles ints que vous attendez chaque int de montrer à peu près 3 fois donner ou prendre. Ce faible niveau de duplication ne garantit pas la modification d'un standard de la routine de tri (sortes de morceaux à la fois et fusionne ensuite les morceaux ensemble).
Cependant, si l'on restreint le fichier "services de renseignements" à tous les non-négatif, nous avons immédiatement attendre à ce que chacun valide int apparaissent à peu près 6 fois. C'est l'approche d'un niveau de duplication qui peut entraîner des changements dans les routines de tri. Donc, je pense que vous devriez demander à l'intervieweur si quelque chose de plus peut être supposé à propos de la distribution de services de renseignements sur le disque. Après tout, il serait étrange d'avoir 100 GO de données et n'ont aucune idée de si elle présente un schéma prévisible.
Ouais, je reçois ce que vous avez écrit les questions de l'entrevue. Mais vous devriez demander à l'entrevue, si les chiffres dans le fichier de venir d'une distribution ou d'une autre. Parce que d'avoir que la connaissance (ou non) a de graves implications -- vous devez montrer que vous vous rendez compte que.
Bon point, la plupart des enquêteurs s'attendre à la personne interrogée de poser quelques questions de clarification. Ceux signifier beaucoup de choses sur la façon dont la personne pense et traite les problèmes présentés.
J'ai pensé à ça, mais en comptant est bon que lorsque la gamme est restreinte. Il doit être capable de gérer n'importe quelle entrée, et même la taille de DWORD n'est pas suffisant pour stocker le max possible de compter.
OriginalL'auteur Ivan
Je pense qu'un algorithme rapide pour un autre 100 GO d'espace libre sur disque dur sont la condition préalable.
Suffit d'utiliser toute sorte sur 2 go de morceaux et de les mettre en arrière. Maintenant, vous avez 50 triés morceaux dans le fichier, et vous cand l'utilisation de la fusion de tri comme suggéré par Mihir sur eux. Écrire la sortie de la mémoire tampon qu'il remplit dans le fichier de sortie. Vous aurez juste à affiner l'entrée et la sortie des tailles de mémoire tampon.
Il y a des solutions avec le comptage. Il ne peut pas être utilisée sur cette grande plage et le maximum possible de compter. Vous ne pouvez les stocker QWORD compteurs sur le disque, mais cela signifie beaucoup de nombre d'accès aléatoires, qui sera certainement plus lent que de travailler avec les plus grands tampons.
mais comment?
Regarder le post de Mark Synowiec.
Si vous sélectionnez l'entrée en 50 égalité des morceaux de la taille, de Fusion et le Tri est une bonne réponse. Vous obtenez 400 GO total I/O - 100 GO pour lire l'entrée, 100 GO pour écrire les 50 fichiers, 100 GO de lire tous les 50 fichiers de nouveau, et 100 GO pour produire la sortie.
depuis que vous avez jamais précisé la taille des entiers, il semble prématuré de dire une solution de comptage serait pratique. Même si elle l'est, le pire des cas, le rendement sera lamentable.
OriginalL'auteur ruslik
Fusion De Tri est une approche populaire quand il s'agit de la mémoire limitée
Gunner, en fait, non :), vous êtes probablement à la réflexion sur la mémoire principale algorithmes de tri, ce qui n'est pas le débat ici.
OriginalL'auteur Mihir Mathuria
De 100 go de données integer signifie que vous aurez un grand nombre de données en double. Je serais personnellement choisir un (bucketsort/sélection) /mergesort approche de mon premier instinct si j'essaie de minimiser le disque I/O.
Première lecture un peu moins de 1 go de données en mémoire, mergesort que les données en mémoire. Vider sur le disque. Répétez l'opération pour chaque partie de la mémoire. Ensuite, vous pouvez marcher chaque morceau de données et de saisir toutes les 0s, répétez l'opération pour chaque entier. Ça va prendre du temps, mais c'est seulement 203GB Lire et 200GO écrire pire des cas (théorique).
Fusion de tri nécessite O(n) de la mémoire supplémentaire.
Vous essayez de réduire au minimum les opérations de disque et n'ont aucune limite sur les opérations CPU. Vous pouvez faire une fusion en O(1) d'espace supplémentaire si vous faites votre fusion en O(n^2) temps CPU. Personnellement, cependant, je viens de lire de 2 go et de QuickSort.
Je pense que la RAM en fonction de tri n'a pas beaucoup d'importance. Nous pouvons utiliser Heapsort constante d'une quantité supplémentaire de l'utilisation de la mémoire et pas de scénario du pire cas de quicksort. - Je choisir heapsort, parce que c'est en place.
Je voudrais aller avec un pur mergesort. O(1) mémoire principale de l'espace en streaming, triées de la sortie d'une mémoire secondaire), de Sorte que l'ensemble de la mémoire peut être utilisée pour l'entrée/la sortie du buffer (lecture/écriture en gros morceaux). Je ne comprends pas d'où l'O(n^2) Gabe mentionne vient de, la fusion est O(n).
OriginalL'auteur OmnipotentEntity