Умный фильтр с питоном

Question

Привет
Мне нужно отфильтровать все строки, которые не содержат символов из огромного списка "необходимых", пример кода:

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))

У меня есть Python 2.4, поэтому я не могу использовать встроенный-in any().
Я долго жду эту фильтрацию, но есть ли способ ее оптимизировать?Например, строки 1 и 4 содержат шаблон «RED ..», если мы обнаружили, что шаблон «RED ..» в порядке, можем ли мы пропустить поиск в списке из 10000 членов для строки 4 с тем же шаблоном ??
Есть ли некоторыеЕще один способ оптимизировать фильтрацию?
Спасибо.
... отредактировано ...
UPD: Смотрите реальные примеры данных в комментариях к этому сообщению.Меня также интересует сортировка по «фруктам» результата.Спасибо!
... конец отредактирован ...

Answer 1

Если вы организовали список necessary как три , то вы можете посмотреть в этом блоке, чтобы проверить, начинается ли fruit с действительного префикса. Это должно быть быстрее, чем сравнение fruit с каждым префиксом.

Например (только слегка проверено):

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)

Это меняет ваш алгоритм с O(N * k), где N - это число элементов necessary, а k - это длина fruit, до просто O(k) (больше или меньше). Хотя для этого требуется больше памяти, но это может быть полезным компромиссом для вашего случая.

Answer 2

Я убежден Ответ Зака ​​ на правильном пути.Из любопытства я реализовал другую версию (включающую комментарии Зака ​​об использовании dict вместо bisect) и свел ее в решение, соответствующее вашему примеру.

#!/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)))

Для краткости, реализация PrefixMatch is опубликовано здесь .

Если ваш список necessary префиксов статичен или изменяется нечасто, вы можете ускорить последующие запуски, выбрав и повторно использовав объект PickleMatch вместо восстановленияэто каждый раз.

обновление (по отсортированным результатам)

Согласно changelog для Python 2.4 :

ключ должен бытьоднопараметрическая функция, которая принимает элемент списка и возвращает ключ сравнения для элемента.Затем список сортируется с помощью клавиш сравнения.

также, в исходный код, строка 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
   .... */

Это означает, что ваш шаблон регулярного выраженияоценивается только один раз для каждой записи (не один раз для каждого сравнения), поэтому это не должно быть слишком дорого:

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

Answer 3

Мне лично нравится ваш код как есть, поскольку вы рассматриваете "fruit = COLOR" как шаблон, который другие не делают. Я думаю, что вы хотите найти какое-то решение, такое как запоминание, которое позволит вам пропустить тестирование для уже решенной проблемы, но я полагаю, что это не тот случай.

def any_it (повторяемый): для элемента в итерируемом: элемент if: вернуть True вернуть Ложь

обязательно = ['ЖЕЛТЫЙ', 'ЗЕЛЕНЫЙ', 'КРАСНЫЙ', ...]

предикат = лямбда-строка: any_it ("fruit =" + цвет в строке для нужного цвета)

Filter = Ifilter (предикат, открытый ("тест"))

Answer 4

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

или, может быть:

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 5

Я бы составил простой список ['fruit=RED','fruit=GREEN'... и т. Д. С помощью ['fruit='+n for n in necessary], а затем использовал бы in вместо регулярных выражений для их проверки.Я не думаю, что есть какой-то способ сделать это очень быстро.

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

(функция any () делает то же самое, что и ваша функция any_it ())

Ohи избавьтесь от file.readlines (), просто переберите файл.

Answer 6

Протестированный (но не бенчмаркированный) код:

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)

Различаются по коду:

1. Сначала мы не загружаем весь файл в память (как есть)сделано, когда вы используете file.readlines()).Вместо этого мы обрабатываем каждую строку при чтении файла. Для краткости я использую здесь модуль fileinput, но можно также использовать line = file.readline() и цикл while line:.

2. Мы прекращаем итерацию по списку necessary, как только найдено совпадение.

3. Мы изменили шаблон регулярного выражения и используем re.match вместо re.findall.Предполагается, что каждая строка будет содержать только одну запись "fruit = ...".

update

Если формат входного файла согласован, вы можете сжатьнемного повысить производительность, избавившись от регулярных выражений.

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

Answer 7

Это не займет слишком много времени, чтобы перебрать 100 000 строк, но я вижу, что у вас есть список из 10000 строк, что означает, что вы перебираете строки в 10 000 * 100 000 = 1 000 000 000 раз, поэтому я не знаю, чего вы ожидали. .. Что касается вашего вопроса, если вы встретите слово из списка, и вам нужно только 1 или более (если вы хотите точно 1, вам нужно перебрать весь список), вы можете пропустить остальное, следует оптимизировать операция поиска.

Answer 8

Непроверенный код:

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

Это должно быть быстрее, чем сопоставление с шаблоном с 10 000 рисунками на линии.Возможно, есть даже более быстрые способы.:)