Lire un fichier énorme en Python

Question

J'ai un fichier texte de 384 Mo avec 50 millions de lignes. Chaque ligne contient 2 entiers séparés par des espaces: une clé et une valeur. Le fichier est trié par clé. J'ai besoin d'un moyen efficace de rechercher les valeurs d'une liste d'environ 200 clés en Python.

Mon approche actuelle est incluse ci-dessous. Cela prend 30 secondes. Il doit y avoir des foo de Python plus efficaces pour obtenir une efficacité raisonnable de quelques secondes au maximum.

# list contains a sorted list of the keys we need to lookup 
# there is a sentinel at the end of list to simplify the code 
# we use pointer to iterate through the list of keys 
for line in fin: 
    line = map(int, line.split()) 
    while line[0] == list[pointer].key: 
    list[pointer].value = line[1] 
    pointer += 1 
    while line[0] > list[pointer].key: 
    pointer += 1 
    if pointer >= len(list) - 1: 
    break # end of list; -1 is due to sentinel 

recherche binaire Codé + chercher une solution (merci kigurai!):

entries = 24935502 # number of entries 
width = 18  # fixed width of an entry in the file padded with spaces 
        # at the end of each line 
for i, search in enumerate(list): # list contains the list of search keys 
    left, right = 0, entries-1 
    key = None 
    while key != search and left <= right: 
    mid = (left + right)/2 
    fin.seek(mid * width) 
    key, value = map(int, fin.readline().split()) 
    if search > key: 
     left = mid + 1 
    else: 
     right = mid - 1 
    if key != search: 
    value = None # for when search key is not found 
    search.result = value # store the result of the search 

Answer 1

Si vous n'avez besoin que de 200 à 50 millions de lignes, il est inutile de tout lire en mémoire. Je trier la liste des clés de recherche et ensuite appliquer la recherche binaire au fichier en utilisant seek() ou quelque chose de similaire. De cette façon, vous ne liriez pas tout le fichier en mémoire, ce qui, je pense, devrait accélérer les choses.

Answer 2

J'utiliseraient mémoire Maping: http://docs.python.org/library/mmap.html.
De cette façon, vous pouvez utiliser le fichier comme s'il était stocké en mémoire, mais le système d'exploitation décide quelles pages doivent être lues dans le fichier.

Answer 3

On ne sait pas très bien à quoi sert "list [pointeur]". Considérez ceci, cependant.

from collections import defaultdict 
keyValues= defaultdict(list) 
targetKeys= # some list of keys 
for line in fin: 
    key, value = map(int, line.split()) 
    if key in targetKeys: 
     keyValues[key].append(value) 

Answer 4

Une optimisation possible consiste à faire un peu de mise en mémoire tampon en utilisant l'option sizehint dans file.readlines(..). Cela vous permet de charger plusieurs lignes dans la mémoire totalisant environ sizehint octets.

Answer 5

optimisation légère de réponse S.Lotts:

from collections import defaultdict 
keyValues= defaultdict(list) 
targetKeys= # some list of keys as strings 
for line in fin: 
    key, value = line.split() 
    if key in targetKeys: 
     keyValues[key].append(value) 

Comme nous utilisons un dictionnaire plutôt que d'une liste, les clés ne doivent pas être des nombres. Cela enregistre l'opération map() et une conversion de chaîne en nombre entier pour chaque ligne. Si vous voulez que les touches soient des nombres, faites la conversion à la fin, quand vous n'avez à le faire qu'une seule fois pour chaque touche, plutôt que pour chacune des 50 millions de lignes.

Answer 6

Si vous avez un contrôle sur le format du fichier, les réponses "tri et recherche binaire" sont correctes. Le détail est que cela ne fonctionne qu'avec des enregistrements de taille et de décalage fixes (enfin, je dois dire que cela ne marche que très facilement avec des enregistrements de longueur fixe). Avec les enregistrements de longueur fixe, vous pouvez facilement rechercher() autour du fichier trié pour trouver vos clés.

Answer 7

Vous devez mettre en œuvre la recherche binaire en utilisant seek()

Answer 8

Voici une recherche binaire récursive sur le fichier texte

import os, stat 

class IntegerKeyTextFile(object): 
    def __init__(self, filename): 
     self.filename = filename 
     self.f = open(self.filename, 'r') 
     self.getStatinfo() 

    def getStatinfo(self): 
     self.statinfo = os.stat(self.filename) 
     self.size = self.statinfo[stat.ST_SIZE] 

    def parse(self, line): 
     key, value = line.split() 
     k = int(key) 
     v = int(value) 
     return (k,v) 

    def __getitem__(self, key): 
     return self.findKey(key) 

    def findKey(self, keyToFind, startpoint=0, endpoint=None): 
     "Recursively search a text file" 

     if endpoint is None: 
      endpoint = self.size 

     currentpoint = (startpoint + endpoint) // 2 

     while True: 
      self.f.seek(currentpoint) 
      if currentpoint <> 0: 
       # may not start at a line break! Discard. 
       baddata = self.f.readline() 

      linestart = self.f.tell() 
      keyatpoint = self.f.readline() 

      if not keyatpoint: 
       # read returned empty - end of file 
       raise KeyError('key %d not found'%(keyToFind,)) 

      k,v = self.parse(keyatpoint) 

      if k == keyToFind: 
       print 'key found at ', linestart, ' with value ', v 
       return v 

      if endpoint == startpoint: 
        raise KeyError('key %d not found'%(keyToFind,)) 

      if k > keyToFind: 
       return self.findKey(keyToFind, startpoint, currentpoint) 
      else: 
       return self.findKey(keyToFind, currentpoint, endpoint) 

Un fichier texte exemple créé en jEdit semble fonctionner:

>>> i = integertext.IntegerKeyTextFile('c:\\sampledata.txt') 
>>> i[1] 
key found at 0 with value 345 
345 

Il pourrait certainement être amélioré en mettant en cache les clés trouvées et en utilisant le cache pour déterminer les futurs points de recherche.