3

嗨
，我需要从巨大的“必要”列表中过滤掉所有不包含符号的行，示例代码：

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，所以我不能使用内置的any().
我等待这个过滤很长时间，但是有什么方法可以优化它吗？例如第 1 行和第 4 行包含“RED..”模式，如果我们发现“RED..”模式没问题，我们可以跳过在 10000 成员列表中搜索第 4 行相同的模式吗？
还有其他优化过滤的方法吗？
谢谢你。
...已编辑...
UPD：请参阅此帖子的评论中的真实示例数据。我也有兴趣按“水果”结果排序。谢谢！
...结束编辑...

4

8 回答 8

5

如果您将necessary列表组织为trie，那么您可以查看该 trie 以检查是否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)（或多或少）。虽然它确实需要更多的内存，但这对于您的情况来说可能是一个值得权衡的选择。

于 2010-12-09T13:14:34.247 回答
1

经过测试（但未进行基准测试）的代码：

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=...”条目。

更新

如果输入文件的格式是一致的，你可以通过完全摆脱正则表达式来挤出更多的性能。

try:
    # with line = "2 asdasd fruit=SOMETHING asdasd...."
    key = line.split(" ", 3)[2].split("=")[1]
except:
    continue # no match
于 2010-12-09T12:12:41.437 回答
1

我会用 制作一个简单的['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() 函数做同样的事情）

哦，摆脱 file.readlines()，只需遍历文件。

于 2010-12-09T12:12:57.360 回答
1 
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
于 2010-12-09T12:29:52.197 回答
1

我个人喜欢您的代码，因为您认为“fruit=COLOR”是其他人不认为的模式。我认为您想找到一些解决方案，例如 memoization，它可以让您跳过已经解决的问题的测试，但我猜不是这种情况。

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

必要 = ['黄色'，'绿色'，'红色'，...]

predicate = lambda line: any_it("fruit=" + color in line for color in required)

过滤 = ifilter（谓词，打开（“testest”））

于 2010-12-09T12:47:06.233 回答
1

我相信扎克的答案是正确的。出于好奇，我实现了另一个版本（结合了 Zach 关于使用 dict 而不是 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的实现。

如果您的necessary前缀列表是静态的或不经常更改，您可以通过酸洗和重用对象来加速后续运行，PickleMatch而不是每次都重新构建它。

更新（在排序结果上）

根据Python 2.4 的更新日志：

key应该是一个单参数函数，它接受一个列表元素并返回该元素的比较键。然后使用比较键对列表进行排序。

此外，在源代码中，第 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))
于 2010-12-10T16:44:47.807 回答
0

未经测试的代码：

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

这应该比将 10 000 个模式匹配到一条线上更快。可能还有更快的方法。:)

于 2010-12-09T12:10:21.720 回答
0

迭代 100,000 个字符串应该不会花费太长时间，但是我看到您有一个 10,000 个字符串列表，这意味着您迭代 10,000 * 100,000 = 1,000,000,000 次字符串，所以我不知道您期望什么...对于您的问题，如果您遇到列表中的一个单词并且您只需要 1 个或更多（如果您想要 1 个您需要遍历整个列表）您可以跳过其余部分，它应该优化搜索操作。

于 2010-12-09T12:12:17.403 回答