quelle est la meilleure façon de trier un tableau énorme. disons que j'ai 1G RAM, le tableau est 16G. Quelle est la méthode la plus efficace pour cela? J'ai assez de disque pour les fichiers.trier un énorme tableau
Diviser en blocs et trier 512 Mo à la fois en 32 fichiers. Ensuite, effectuez un tri en fusion des fichiers dans un fichier.
S'il s'agit d'un tableau d'entiers, vous pouvez vous débrouiller avec un type de base naïf (O(n)) et n'utilisez pratiquement pas de RAM du tout. La première question serait "Quel genre de données est-ce?". Si ses données arbitraires, alors un mergesort externe est probablement votre meilleure option.
-tjw
Quel langage de programmation avez-vous l'intention d'utiliser? Vous semblez être le plus concerné par l'utilisation de la mémoire. Quel est l'état de la mémoire virtuelle? Avez-vous même besoin de vous en soucier? * Quelle est votre définition de 'meilleur' * - temps, échange réduit ou autre? –
@ p.campbell pas un problème pratique. Focus sur l'algorithme et la solution. Merci :) –
@ p.campbell ouais un peu. J'ai déjà rencontré une autre question importante. alors est venu avec celui-ci. prépare toujours pour l'interview d'Amazon. LOL ~ –