Lecture efficace de quelques lignes d'un très grand fichier binaire

Question

Voici un exemple simple pour illustrer mon problème : J'ai un grand fichier binaire avec 10 millions de valeurs.

Je veux obtenir les valeurs de 5K à partir de certains points de ce fichier.

J'ai une liste d'index qui me donne l'endroit exact dans le fichier où se trouve ma valeur.

Pour résoudre ce problème, j'ai essayé deux méthodes :

1. En passant par les valeurs et en utilisant simplement seek() (depuis le début du fichier) pour obtenir chaque valeur, quelque chose comme ceci :

   binaryFile_new = open(binary_folder_path, "r+b")
   for index in index_list:
       binaryFile_new.seek (size * (index), 0)
       wanted_line = binaryFile_new.read (size)
       wanted_line_list.append(wanted_line)
   binaryFile_new.close()

   Mais si je comprends bien, cette solution lit depuis le début pour chaque index, donc la complexité est O(N**2) en termes de taille de fichier.

2. Trier les index pour pouvoir parcourir le fichier "une fois" tout en cherchant à partir de la position actuelle avec quelque chose comme ça :

   binaryFile_new = open(binary_folder_path, "r+b")
   sorted_index_list = sorted(index_list)
   for i, index in enumerate(sorted_index_list):
           if i == 0:
                   binaryFile_new.seek (size * (v), 0)
               else:
                   binaryFile_new.seek ((index - sorted_index_list[i-1]) * size - size, 1)
       binaryFile_new.seek (size * (index), 0)
       wanted_line = binaryFile_new.read (size)
       wanted_line_list.append(wanted_line)
   binaryFile_new.close()

   Je m'attendais à ce que la deuxième solution soit beaucoup plus rapide car, en théorie, elle parcourrait l'ensemble du fichier en une seule fois O(N).

   Mais pour une raison quelconque, les deux solutions fonctionnent de la même manière.

J'ai également une contrainte forte sur l'utilisation de la mémoire, car j'exécute cette opération en parallèle et sur de nombreux fichiers, je ne peux donc pas lire les fichiers en mémoire.

Peut-être que le mmap sera utile ? Cependant, je pense que mmap balaie également l'ensemble du fichier jusqu'à l'index, il ne s'agit donc pas d'un "véritable" accès aléatoire.

Answer 1

Je choisirais le numéro 1 :

for index in index_list:
    binary_file.seek(size * index)
    # ...

(J'ai nettoyé un peu votre code pour respecter les conventions de nommage de Python et pour éviter d'utiliser une formule magique 0 constante, comme SEEK_SET est de toute façon par défaut).

Si je comprends bien, cette solution lit depuis le début pour chaque index, donc la complexité est O(N**2) en termes de taille de fichier.

Non, un seek() ne "lit pas depuis le début", cela irait à l'encontre du but de la recherche. La recherche au début du fichier et à la fin du fichier a à peu près le même coût.

Trier les index pour pouvoir parcourir le fichier "une fois" tout en cherchant à partir de la position actuelle.

Je n'arrive pas à trouver rapidement une référence à ce sujet, mais je crois qu'il est absolument inutile de calculer le décalage relatif afin d'utiliser SEEK_CUR au lieu de SEEK_SET.

Il peut y avoir une petite amélioration en recherchant les positions dont vous avez besoin dans l'ordre plutôt qu'aléatoirement, car il y a plus de chances que vos lectures aléatoires soient servies par le cache, au cas où plusieurs des points que vous devez lire se trouvent proches les uns des autres (et que vos modèles de lecture déclenchent le read-ahead dans le système de fichiers).

Peut-être que le paquet mmap vous aidera ? Cependant, je pense que mmap scanne également l'ensemble du fichier jusqu'à l'index, donc ce n'est pas un "vrai" accès aléatoire.

mmap n'analyse pas le fichier. Il configure une région dans la mémoire virtuelle de votre programme pour correspondre au fichier, de sorte que l'accès à une page de cette région la première fois conduit à un défaut de page, pendant lequel le système d'exploitation lit cette page (plusieurs Ko) du fichier (en supposant qu'elle n'est pas dans le cache de page) avant de laisser votre programme continuer.

L'internet regorge de discussions sur les mérites relatifs de l'agriculture et de la pêche. read vs mmap mais je vous recommande ne vous embêtez pas à essayer d'optimiser en utilisant mmap et profitez de ce temps pour vous renseigner sur le mémoire virtuelle et le cache des pages .

[edit] lecture par morceaux plus grands que les size de vos valeurs pourrait vous faire gagner un peu de temps CPU dans le cas où beaucoup des valeurs que vous devez lire sont dans le même chunk (ce qui n'est pas une donnée) - mais à moins que votre programme ne soit lié au CPU en production, je ne ferais pas d'erreur.