Filtre à puce avec python

Question

Salut
J'ai besoin de filtrer toutes les lignes qui ne contiennent pas des symboles de liste énorme « nécessaire », par exemple le code suivant:

def any_it(iterable):
      for element in iterable:
          if element: return True
      return False

regexp = re.compile(r'fruit=([A-Z]+)')
necessary = ['YELLOW', 'GREEN', 'RED', ...] # huge list of 10 000 members
f = open("huge_file", "r") ## file with > 100 000 lines
lines = f.readlines()
f.close()

## File rows like, let's say:
# 1 djhds fruit=REDSOMETHING sdkjld
# 2 sdhfkjk fruit=GREENORANGE lkjfldk
# 3 dskjldsj fruit=YELLOWDOG sldkfjsdl
# 4 gfhfg fruit=REDSOMETHINGELSE fgdgdfg

filtered = (line for line in lines if any_it(regexp.findall(line)[0].startswith(x) for x in necessary))

Je python 2.4, donc je ne peux pas utiliser intégré any().
J'attends depuis longtemps pour ce filtrage, mais est-il un moyen d'optimiser? Par exemple la ligne 1 et 4 contient « ROUGE .. » modèle, si nous avons constaté que « RED .. » pattern est ok, peut-on SKIP recherche dans la liste 10000 membres pour la ligne 4 du même modèle ??
Y at-il une autre façon d'optimiser le filtrage
Merci.
... édité ...
UPD: Voir les données exemple réel dans les commentaires à ce poste. Je suis également intéressé par le tri par « fruits » le résultat. Merci!
... fin édité ...

Answer 1

Je suis convaincu réponse de Zach est sur la bonne voie. Par curiosité, j'ai mis en place une autre version (intégrant les commentaires de Zach sur l'utilisation d'un dict au lieu de bisect) et croisai dans une solution qui correspond à votre exemple.

#!/usr/bin/env python
import re
from trieMatch import PrefixMatch # https://gist.github.com/736416

pm = PrefixMatch(['YELLOW', 'GREEN', 'RED', ]) # huge list of 10 000 members
# if list is static, it might be worth picking "pm" to avoid rebuilding each time

f = open("huge_file.txt", "r") ## file with > 100 000 lines
lines = f.readlines()
f.close()

regexp = re.compile(r'^.*?fruit=([A-Z]+)')
filtered = (line for line in lines if pm.match(regexp.match(line).group(1)))

Par souci de concision, la mise en œuvre de PrefixMatch est publié ici .

Si votre liste de préfixes necessary est statique ou change rarement, vous pouvez accélérer les exécutions ultérieures par décapage et réutilisation de l'objet PickleMatch au lieu de le reconstruire à chaque fois.

Mise à jour (sur les résultats classés)

Selon le changelog pour Python 2.4 :

  

touche doit être une fonction unique paramètre qui prend un élément de liste et   renvoie une clé de comparaison pour la   élément. La liste est ensuite triée à l'aide   les touches de comparaison.

aussi, la source code, ligne 1792 :

/* Special wrapper to support stable sorting using the decorate-sort-undecorate
   pattern.  Holds a key which is used for comparisons and the original record
   which is returned during the undecorate phase.  By exposing only the key
   .... */

Cela signifie que votre modèle de regex est seulement évaluée une fois pour chaque entrée (pas une seule fois pour chaque comparer), donc il ne devrait pas être trop coûteux à faire:

sorted_generator = sorted(filtered, key=regexp.match(line).group(1))

Answer 2

Si vous avez organisé la liste necessary comme Trie, alors vous pouvez regarder dans cette structure arborescente à vérifier si le fruit commence par un préfixe valide. Cela devrait être plus rapide que la comparaison du fruit contre chaque préfixe.

Par exemple (testé uniquement légèrement):

import bisect
import re

class Node(object):
    def __init__(self):
        self.children = []
        self.children_values = []
        self.exists = False

    # Based on code at http://docs.python.org/library/bisect.html                
    def _index_of(self, ch):
        i = bisect.bisect_left(self.children_values, ch)
        if i != len(self.children_values) and self.children_values[i] == ch:
            return (i, self.children[i])
        return (i, None)

    def add(self, value):
        if len(value) == 0:
            self.exists = True
            return
        i, child = self._index_of(value[0])
        if not child:
            child = Node()
            self.children.insert(i, child)
            self.children_values.insert(i, value[0])
        child.add(value[1:])

    def contains_prefix_of(self, value):
        if self.exists:
            return True
        i, child = self._index_of(value[0])
        if not child:
            return False
        return child.contains_prefix_of(value[1:])

necessary = ['RED', 'GREEN', 'BLUE', 'ORANGE', 'BLACK',
             'LIGHTRED', 'LIGHTGREEN', 'GRAY']

trie = Node()
for value in necessary:
    trie.add(value)

# Find lines that match values in the trie
filtered = []
regexp = re.compile(r'fruit=([A-Z]+)')
for line in open('whatever-file'):
    fruit = regexp.findall(line)[0]
    if trie.contains_prefix_of(fruit):
        filtered.append(line)

Cela change votre algorithme de O(N * k), où N est le nombre d'éléments de necessary et k est la longueur de fruit, juste O(k) (plus ou moins). Il ne prend plus de mémoire si, mais ce pourrait être un compromis intéressant pour votre cas.

Answer 3

Personnellement, je aime votre code tout comme puisque vous considérez comme « fruit = COLOR » comme un modèle que d'autres ne fonctionne pas. Je pense que vous voulez trouver une solution comme memoization qui vous permet de sauter test problème déjà résolu, mais ce n'est pas le cas, je suppose.

def any_it (iterable):       pour l'élément en iterable:           si l'élément: Vrai retour       return false

= nécessaires [ 'JAUNE', 'VERT', 'RED', ...]

prédicat = ligne lambda: any_it ( "fruit =" + couleur dans la ligne de couleur dans nécessaire)

filtré = ifilter (prédicat, ouvert ( "testest"))

Answer 4

Testé (mais unbenchmarked) Code:

import re
import fileinput

regexp = re.compile(r'^.*?fruit=([A-Z]+)')
necessary = ['YELLOW', 'GREEN', 'RED', ]

filtered = []
for line in fileinput.input(["test.txt"]):
    try:
        key = regexp.match(line).group(1)
    except AttributeError:
        continue # no match
    for p in necessary:
        if key.startswith(p):
            filtered.append(line)
            break

# "filtered" now holds your results
print "".join(filtered)

Diff de code en question:

1. Nous ne pas d'abord charger le fichier entier en mémoire (comme cela se fait lorsque vous utilisez file.readlines()). Au lieu de cela, nous traitons chaque ligne que le fichier est lu. J'utilise le module fileinput ici par souci de concision, mais on peut aussi utiliser line = file.readline() et une boucle de while line:.

2. Nous itérer arrêter la liste des necessary une fois par correspondance est trouvée.

3. Nous avons modifié le modèle regex et l'utilisation re.match au lieu de re.findall. Cela suppose que chaque ligne ne contiendrait un "fruit = ..." entrée.

Mise à jour

Si le format du fichier d'entrée est compatible, vous pouvez presser un peu plus de performance en se débarrassant de regex tout à fait.

try:
    # with line = "2 asdasd fruit=SOMETHING asdasd...."
    key = line.split(" ", 3)[2].split("=")[1]
except:
    continue # no match

Answer 5

filtered=[]
for line in open('huge_file'):
    found=regexp.findall(line)
    if found:
        fruit=found[0]
        for x in necessary:
            if fruit.startswith(x):
                filtered.append(line)
                break

ou peut-être:

necessary=['fruit=%s'%x for x in necessary]
filtered=[]
for line in open('huge_file'):
    for x in necessary:
        if x in line:
            filtered.append(line)
            break

Answer 6

Je fait une liste simple ['fruit=RED','fruit=GREEN'... etc. avec ['fruit='+n for n in necessary], puis utilisez in plutôt que d'un regex pour les tester. Je ne pense pas qu'il y ait une façon de le faire très rapidement, cependant.

filtered = (line for line in f if any(a in line for a in necessary_simple))

(La toute fonction () fait la même chose que votre fonction any_it ())

Oh, et se débarrasser de file.readlines (), juste itérateur sur le fichier.

Answer 7

code non testé:

filtered = []
for line in lines:
    value = line.split('=', 1)[1].split(' ',1)[0]
    if value not in necessary:
        filtered.append(line)

Ce devrait être plus rapide que 10 000 modèle correspondant à des motifs sur une ligne. Peut-être il existe des moyens encore plus rapides. :)

Answer 8

Il ne faut pas prendre trop de temps pour parcourir 100.000 cordes, mais je vois que vous avez une liste de 10.000 chaînes, qui signifie que vous itérer 10 000 * 100 000 = 1000000000 fois les cordes, donc je ne sais pas qu'est-ce que vous attendez. .. Quant à votre question, si vous rencontrez un mot dans la liste et vous avez seulement besoin de 1 ou plus (si vous voulez exacly 1 vous devez parcourir la liste complète) vous peut sauter le reste, il devrait optimiser l'opération de recherche.