Comment utiliser efficacement les fonctions d'entrée/sortie de fichiers sur des fichiers volumineux (en utilisant une taille de mémoire limitée)

Question

Il existe un algorithme que je veux implémenter sur C++, qui comprend de nombreuses entrées/sorties de fichiers. Bien que j'ai implémenté des choses similaires sur des échelles plus petites, cette fois j'ai besoin de travailler sur des fichiers de plusieurs Go. Je sais qu'il y a de nouvelles choses que je devrais considérer quand la taille de dossier est plus grande que la taille de mémoire disponible, et je devrais également être préoccupé au coût.

Mon plan est de obtenir la taille de la mémoire allouée et l'utiliser pour lire une partie prédéterminée et enregistrer les résultats sur un fichier txt pour chaque passage. Cependant, je devrai lire et modifier le fichier txt résultant ligne par ligne après chaque passage pour le mettre à jour, puisque le fichier txt résultant sera une liste liée (les blocs d'octets correspondront aux noeuds).

Est-il efficace de conserver les résultats de ces passages dans un fichier txt et de les mettre à jour ligne par ligne pour chaque passage? J'apprécierais si vous pouvez me faire savoir tout changement qui peut rendre l'algorithme plus efficace. J'apprécierais également si vous pourriez écrire quelques exemples courts/rapides puisque je n'ai jamais utilisé la production d'entrée de dossier autre que le type «lisez ce dossier entier», «écrivez ceci comme le dossier entier».

Édition: Le système d'exploitation est Linux et Mac OS.

De nombreux segments d'octets se répètent à l'intérieur d'un fichier binaire et je souhaite trier le nombre de fois que certaines combinaisons se répètent. Par exemple, si un fichier binaire est 111111100000001110101010100000111, je vais compter le nombre d'occurrences de certains modèles prédéterminés tels que 110111001010, 10101011 etc. et les trier. La taille de fichier minimum que je m'attends est de 1 Go et le maximum est d'environ 10-20 Go. Je vais chercher environ 1.000.000.000 de schémas et je vais les trier tous. Alors j'ai pensé que depuis que j'ai besoin de mettre à jour le fichier de sortie chaque fois que mon tampon est plein, je pourrais aussi faire une liste chaînée et mettre à jour la liste (devrait être ~ O (n)) nlog (n)) à la fin.

Answer 1

est ici un moyen efficace de le faire:

Ouvrez votre fichier source et accéder à vos données avec mmap(). De cette façon, vous accédez directement au OS disk-cahe et vous éliminer la copie de la mémoire de kernel mode à user mode. Si vos fichiers sont très volumineux, il est préférable d'utiliser les plus petits fichiers mmapp-ed views pour éviter la création de grandes tables de pages.

En fonction du nombre de modèles distincts que vous utilisez, vous disposez des options suivantes:

Si le nombre de motifs est assez petit pour tenir dans la mémoire:

• Si les valeurs sont sparse: stockez-les dans un map avec des paires pattern/count.
• Si les valeurs sont quelque peu continues, stockez les comptes dans un vector, où la position est la valeur de votre modèle, en fonction d'un décalage si nécessaire.

Si le nombre de modèles peut obtenir grand:

(vous parlez de 1 milliard de modèles - dépend de la façon unique qu'ils sont), vous pouvez créer un mmap-ed outputfile et stocker les comptes là, mais assurez-vous que toutes les valeurs (ou paires) ont la même largeur, c'est à dire stocker tout en binaire (vous pouvez l'utiliser comme vous le feriez avec un tableau).

Si la plupart des valeurs sont distinctes, stockez-les à l'emplacement de votre valeur de modèle - par exemple, si le modèle (32bit?) + Compte 8 octets, stockez-les à la position pattern-value * 8 pour un accès rapide. Dans le cas où il existe de grandes lacunes dans vos valeurs de modèle, mais que vous voulez éviter d'insérer une donnée en mouvement, pensez à utiliser un sparse file (temporaire) pour stocker les valeurs directement à la bonne position.

Si vous n'aviez besoin que d'un comptage, vous pouvez stocker les comptages (32 bits) uniquement, à leur position spécifique, mais si vous avez besoin d'un tri, vous aurez également besoin des valeurs de modèle.

Pour les trier, je préférerais utiliser radix sort.