在Python中比较和替换键值对的最快方法

Question

我有许多文件，在这些文件中，我希望用另一个字符串替换特定字符串的所有实例。

我现在有这样的代码：

    mappings = {'original-1': 'replace-1', 'original-2': 'replace-2'}

    # Open file for substitution
    replaceFile = open('file', 'r+')

    # read in all the lines
    lines = replaceFile.readlines()

    # seek to the start of the file and truncate
    # (this is cause i want to do an "inline" replace
    replaceFile.seek(0)
    replaceFile.truncate()

    # Loop through each line from file
    for line in lines:
        # Loop through each Key in the mappings dict
        for i in mappings.keys():
            # if the key appears in the line
            if i in line:
                # do replacement
                line = line.replace(i, mappings[i])
        # Write the line to the file and move to next line
        replaceFile.write(line)

这是可行的，但对于映射的大小和我正在处理的文件的大小来说，它非常慢。

例如，在“映射”dict中有60728对键值对。我需要处理多达50个文件，并用相应的值替换所有的"key“实例，这50个文件中的每一个都是大约250000行。

也有多个实例，其中有多个键需要替换在一行上，因此我不能只是找到第一个匹配，然后继续。

所以我的问题是：

有更快的方法来做上面的事吗？我已经考虑过使用regex，但是我不知道如何使用dict中的键/值对来完成多个内联替换。

如果你需要更多的信息，告诉我。

Answer 1

如果表演慢了，你就得找些花哨的东西。一切都是在C级运行：

for filename in filenames:
    with open(filename, 'r+') as f:
        data = f.read()
        f.seek(0)
        f.truncate()
        for k, v in mappings.items():
            data = data.replace(k, v)
        f.write(data)

请注意，您可以运行多个进程，其中每个进程处理文件总列表的一部分。这应该能让整个工作变得更快。没有什么特别之处，只需在shell上运行多个实例，每个实例都有一个不同的文件列表。

显然是str.replace比regex.sub快。

因此，我需要更多地考虑这个问题:假设您有一个非常大的mappings。因此，在您的文件中检测到mappings中的任何一个密钥的可能性都非常低。在这个场景中，所有的时间都花在搜索上(正如@abarnert所指出的)。

在诉诸奇异的算法之前，似乎有可能至少可以使用multiprocessing并行地进行搜索，然后在一个进程中执行替换(由于明显的原因，不能在多个进程中进行替换:您将如何组合结果？)

因此，我最终决定对multiprocessing有一个基本的理解，下面的代码看上去似乎是可行的：

import multiprocessing as mp

def split_seq(seq, num_pieces):
    # Splits a list into pieces
    start = 0
    for i in xrange(num_pieces):
        stop = start + len(seq[i::num_pieces])
        yield seq[start:stop]
        start = stop   

def detect_active_keys(keys, data, queue):
    # This function MUST be at the top-level, or
    # it can't be pickled (multiprocessing using pickling)
    queue.put([k for k in keys if k in data])

def mass_replace(data, mappings):
    manager = mp.Manager()
    queue = mp.Queue()
    # Data will be SHARED (not duplicated for each process)
    d = manager.list(data) 

    # Split the MAPPINGS KEYS up into multiple LISTS, 
    # same number as CPUs
    key_batches = split_seq(mappings.keys(), mp.cpu_count())

    # Start the key detections
    processes = []
    for i, keys in enumerate(key_batches):
        p = mp.Process(target=detect_active_keys, args=(keys, d, queue))
        # This is non-blocking
        p.start()
        processes.append(p)

    # Consume the output from the queues
    active_keys = []
    for p in processes:
        # We expect one result per process exactly
        # (this is blocking)
        active_keys.append(queue.get())

    # Wait for the processes to finish
    for p in processes:
        # Note that you MUST only call join() after
        # calling queue.get()
        p.join()

    # Same as original submission, now with MUCH fewer keys
    for key in active_keys:
        data = data.replace(k, mappings[key])

    return data

if __name__ == '__main__':
    # You MUST call the mass_replace function from
    # here, due to how multiprocessing works
    filenames = <...obtain filenames...>
    mappings = <...obtain mappings...>
    for filename in filenames:
        with open(filename, 'r+') as f:
            data = mass_replace(f.read(), mappings)
            f.seek(0)
            f.truncate()
            f.write(data)

一些注意事项：

• 我还没有执行这段代码！我希望有一天能对它进行测试，但是创建测试文件需要时间等等。请将其视为介于伪代码和有效python之间。要让它运转起来应该不难。
• 可以想象，使用多台物理机器(即具有相同代码的集群)应该相当容易。multiprocessing的文档展示了如何使用网络上的机器。
• 这段代码仍然很简单。我很想知道它是否能提高你的速度。
• 在使用多重处理时，似乎有很多麻木不仁的警告，我试图在评论中指出这一点。由于我还没有能够测试代码，所以可能是因为我没有正确地使用多处理。

Answer 2

根据http://pravin.paratey.com/posts/super-quick-find-replace的说法，regex是使用Python最快的方式。(为C++构建Trie数据结构将是最快的)：

import sys, re, time, hashlib

class Regex:

    # Regex implementation of find/replace for a massive word list.

    def __init__(self, mappings):
        self._mappings = mappings

    def replace_func(self, matchObj):
        key = matchObj.group(0)
        if self._mappings.has_key(key):
            return self._mappings[key]
        else:
            return key

    def replace_all(self, filename):
        text = ''
        with open(filename, 'r+') as fp
            text = fp.read()
        text = re.sub("[a-zA-Z]+", self.replace_func, text)
        fp = with open(filename, "w") as fp:
            fp.write(text)

# mapping dictionary of (find, replace) tuples defined 
mappings = {'original-1': 'replace-1', 'original-2': 'replace-2'}

# initialize regex class with mapping tuple dictionary
r = Regex(mappings)

# replace file
r.replace_all( 'file' )

Answer 3

缓慢的部分是搜索，而不是替换。(即使我错了，你也可以通过先搜索所有的索引，然后再从末尾拆分和替换，轻松地加快替换部分的速度；只有搜索部分才需要聪明。)

对于N长字符串和M子字符串，任何简单的质量字符串搜索算法显然都是O(NM) (如果子字符串足够长，那么可能更糟)。在每个位置搜索M次的算法，而不是整个字符串上的M次，可能会带来一些缓存/分页的好处，但它可能会复杂得多，因为可能只有一点好处。

因此，如果您坚持一个天真的算法，您将不会比cjrh的实现做得更好。(您可以尝试将它编译为Cython，或者在PyPy中运行它，以确定它是否有用，但我怀疑它会有多大帮助--正如他解释的，所有的内部循环都在C中。)

加快速度的方法是一次以某种方式查找许多子字符串。这样做的标准方法是构建前缀树(或后缀树)，因此，例如，“原始-1”和“原始-2”都是同一子树“原始-”的分支，因此它们在最后一个字符之前不需要单独处理。

前缀树的标准实现是trie。然而，正如有效的字符串匹配:书目检索的辅助工具和维基百科的文章Aho字符串匹配算法所解释的那样，您可以通过使用带有额外链接的定制数据结构来进一步优化这个用例。(IIRC，这改善了logM的平均案例。)

Aho和Corasick通过从回退trie中编译一个有限的状态机来进一步优化事情，这并不适合每个问题，但听起来对您来说是合适的。(重复使用相同的映射的次数为50次。)

有许多不同的算法有额外的好处，因此它可能值得进一步的研究。(常见的用例是诸如病毒扫描器和包过滤器之类的东西，它们可能有助于搜索。)但我认为阿波罗-科拉西克，甚至只是一个普通的，可能是足够好。

用纯Python构建这些结构可能会增加大量开销，在M~60000时，额外的成本将击败M/logM算法的改进。但幸运的是你没必要这么做。许多C优化的trie实现和至少有一个Aho-Corasick实现在PyPI上。如果您认为后缀匹配会更好地处理数据，那么也可能值得研究一些类似于SuffixTree的东西，而不是使用一个通用的trie库。

不幸的是，没有数据集，其他任何人都很难进行有用的性能测试。如果您愿意，我可以编写使用几个不同模块的测试代码，然后您可以针对您的数据运行测试代码。但是，下面是一个简单的示例，使用ahocorasick进行搜索，并为该替换提供一个简单的从端到端的替换实现：

tree = ahocorasick.KeywordTree()
for key in mappings:
    tree.add(key)
tree.make()    
for start, end in reversed(list(tree.findall(target))):
    target = target[:start] + mappings[target[start:end]] + target[end:]