Comment lire efficacement des lignes de gros fichier texte en Python dans différents ordres: a) ligne aléatoire à chaque fois, b) commençant au milieu ...?

Question

J'ai un grand fichier texte (5 millions à 10 millions de lignes). Chaque ligne contient 10 à 5 000 éléments alphanumériques séparés l'un de l'autre par un espace ou une virgule. Chaque ligne se termine par un saut de ligne. Le nombre de lignes est connu avant l'exécution et le fichier texte ne change pas pendant l'exécution.

Chaque fois que le code est exécuté, il reçoit 50-200 listes de recherche, chacune contenant 2 à 10 éléments (mots). Pour chacune de ces listes de recherche, je voudrais trouver x le nombre de lignes dans le fichier texte qui contient contient au moins un élément de cette liste. Le nombre de lignes x varie de 5 à 10 lignes et est défini lors de l'exécution. La correspondance est insensible à la casse et doit être exacte sur la limite de mot (par exemple, "foo" correspond à ", foo" mais pas à "foobar").

Chaque liste de recherche est l'un des trois stratégies de commande de recherche:

• normal. Commencez à la première ligne, recherchez ligne par ligne dans commande consécutive jusqu'à ce qu'il trouve x nombre de lignes ou atteint la dernière ligne .

• Aléatoire. Choisissez des lignes au hasard dans le fichier texte. Continuez jusqu'à ce qu'il trouve x nombre de lignes ou a terminé la recherche de chaque ligne.

• Plage de godet. Par exemple, la priorité de la plage de recherche peut être d'abord parcourir les lignes 1 000 000 à 1 499 999, puis les lignes 0 à 999 999, puis les lignes 1 500 000 à 2 199 999, etc. Il peut y avoir entre 3 et 20 godets, chacun couvrant une gamme de 100 000 à 5 000 000 de lignes. Le nombre de compartiments et de plages de numéros de ligne est indiqué lors de l'exécution. Dans chaque plage, effectuez une recherche consécutivement. Recherchez jusqu'à ce qu'il trouve x nombre de lignes ou atteint la fin du dernier compartiment.

Voici ce que je l'ai écrit pour la « recherche normale » [code de test vérifie toutes les lignes à la fin du fichier sans arrêt après x lignes; dans la version finale, après qu'il trouve x résultats correspondant à une liste de recherche, il va arrêter et passer à la prochaine liste de recherche]:

import re 
textFile = "bigTextFile.txt" 
searchItems = ["foo","bar","anotherfoo","anotherbar","etc"] 
searchStrategy = "normal" #could be "normal", "random", "bucket"; this code is just for "normal" 
results = [] 
with open(textFile) as inFile: 
    for line in inFile: 
     regex = re.compile('(' + '|'.join('\\b'+item+'\\b' for item in searchItems) +')', re.IGNORECASE) 
     match = regex.search(line) 
     if match is not None: 
      analysisResult = analyze_the_match(line) 
      results.append(analysisResult) 

Ce code pour la « recherche normale » fonctionne. De ce que j'ai essayé, il semble que ce soit le plus rapide, mais je suis nouveau avec Python et je suppose qu'il doit y avoir un meilleur moyen (vitesse/efficacité) de le faire.

[mise à jour en réponse aux commentaires afin de mieux expliquer la raison de différentes stratégies de recherche] Les articles sont très asymétrique.En jouant avec les données, j'ai trouvé qu'environ la moitié des recherches se termineraient avant 10.000 lignes, 40% pourraient prendre quelques millions de lignes pour trouver suffisamment de correspondances, et 10% ne trouveront pas assez de correspondances dans tout le fichier texte. Les éléments de chaque ligne n'ont aucun rapport avec la ligne dans laquelle ils se trouvent, mais les plages de lignes sont similaires (c'est-à-dire que les lignes 100 000-500 000 sont liées, 1 500 000-1 750 000 sont liées, etc.). Le code peut être exécuté plusieurs fois pour une liste de recherche donnée, et pour chaque exécution, la priorité peut être de se concentrer sur une plage de lignes différente. Si le fichier texte entier n'a que x lignes avec les éléments dans une liste de recherche particulière, alors le résultat sera toujours les lignes x. Mais pour de nombreuses listes de recherche, il y a 2x, 10x, ou 100,000x lignes qui correspondent, et à des moments différents, je voudrais choisir des lignes différentes. À certains moments, une plage particulière peut être la priorité, à d'autres moments, l'échantillonnage aléatoire est préférable, et parfois trouver les premières lignes x dès le début est bien, d'où la recherche "normale", "aléatoire" et "bucket" stratégies.

J'apprécierais vraiment des idées pour «aléatoire» et «seau», car je ne suis pas sûr de la meilleure façon de les aborder efficacement. Je ai joué avec linecache, itertools islice, readlines (par @Martin Thoma en this answer, readlines est étonnamment rapide), ainsi que de modifier le code ci-dessus, mais mes tentatives de "aléatoire" et "seau" sont tous maladroits, inefficaces, et je sachez que je ne sais pas assez pour savoir ce qui pourrait être mieux :).

Des suggestions? Merci.

Answer 1

Pour les recherches aléatoires et les recherches par seau, vous pouvez effectuer une analyse linéaire du fichier et créer une liste de résultats candidats, en remplaçant un candidat de la liste si la liste est complète et qu'un meilleur candidat arrive.

Pour les sélections aléatoires, vous calculez simplement la probabilité qu'un candidat figure dans la liste et utilisez un nombre aléatoire pour déterminer si le candidat est placé dans la liste ou non.

Pour les sélections de compartiment, un candidat remplace un membre de liste existant si son rang de compartiment est meilleur que celui de l'élément existant.

Pour la sélection aléatoire:

import random 
candidates = [] 
n = 0 
with open(textFile) as inFile: 
    for line in inFile: 
     if valid_candidate(line): # use regex here 
      n += 1 
      if n <= x: 
       candidates.append(line) 
      else: 
       i = random.randrange(n) 
       if i < x: 
        candidates[i] = line 
results = [] 
for line in candidates: 
    analysisResult = analyze_the_match(line) 
    results.append(analysisResult) 

Pour la sélection du godet:

import bisect 
candidates = [] 
n = 0 
with open(textFile) as inFile: 
    for line in inFile: 
     n += 1 
     if valid_candidate(line): # use regex here 
      rank = get_rank(n) # use n to determine the bucket and assign a rank, lower numbers are higher rank 
      bisect.insort(candidates, (rank, n, line)) 
results = [] 
for rank, n, line in candidates[:x]: 
    analysisResult = analyze_the_match(line) 
    results.append(analysisResult)