0

我有许多文件,我想用另一个替换特定字符串的所有实例。

我目前有这个代码:


    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)

这工作正常,但是对于映射的大小和我正在处理的文件的大小来说非常慢。

例如,在“映射”字典中有 60728 个键值对。我需要处理多达 50 个文件并将“key”的所有实例替换为相应的值,并且 50 个文件中的每个文件大约有 250000 行。

还有多个实例需要在一行上替换多个键,因此我不能只找到第一个匹配项然后继续。

所以我的问题是:

有没有更快的方法来完成上述操作?我曾考虑过使用正则表达式,但我不确定如何制作一个使用字典中的键/值对进行多次内联替换的正则表达式。

如果您需要更多信息,请告诉我。

4

4 回答 4

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用于展示如何使用网络上的机器的文档。
  • 这段代码还是很简单的。我很想知道它是否能提高你的速度。
  • 使用多处理似乎有很多骇人听闻的警告,我试图在评论中指出。由于我还不能测试代码,可能是我没有正确使用多处理。
于 2013-09-13T00:02:50.390 回答
1

根据http://pravin.paratey.com/posts/super-quick-find-replace,正则表达式是使用 Python 的最快方法。(构建 Trie 数据结构对于 C++ 来说是最快的):

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' )
于 2013-09-12T23:37:25.180 回答
1

缓慢的部分是搜索,而不是替换。(即使我错了,您可以通过首先搜索所有索引,然后从末尾拆分和替换来轻松加快替换部分;只有搜索部分需要聪明。)

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

因此,如果您坚持使用幼稚的算法,您将不会比 cjrh 的实现做得更好。(您可以尝试将它编译为 Cython 或在 PyPy 中运行它以查看它是否有帮助,但我怀疑它是否会有很大帮助 - 正如他解释的那样,所有内部循环都已经在 C 中了。)

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

前缀树的标准实现是trie。但是,正如Efficient String Matching: An Aid to Bibliographic Search和 Wikipedia 文章 Aho-Corasick string matching algorithm 解释的那样,您可以通过使用带有额外链接的自定义数据结构来进一步优化此用例。(IIRC,这将平均情况提高了 logM。)

Aho 和 Corasick 通过从后备树中编译一个有限状态机来进一步优化事情,这并不适合所有问题,但听起来它适合你的问题。(您重复使用相同的映射 dict 50 次。)

有许多变体算法具有额外的好处,因此可能值得进一步研究。(常见的用例是病毒扫描程序和包过滤器之类的东西,它们可能对您的搜索有所帮助。)但我认为 Aho-Corasick,甚至只是一个普通的 trie,可能就足够了。

用纯 Python 构建这些结构中的任何一个都可能会增加很多开销,以至于在 M~60000 时,额外的成本将挫败 M/logM 算法的改进。但幸运的是,您不必这样做。PyPI 上有许多 C 优化的 trie 实现,以及至少一个 Aho-Corasick 实现。如果您认为后缀匹配会更好地处理您的数据,那么也可能值得看一下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:]
于 2013-09-13T18:07:32.383 回答
0

这使用 with 块来防止泄漏文件描述符。字符串替换功能将确保在文本中替换键的所有实例。

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

# Open file for substitution
with open('file', 'r+') as fd:

    # read in all the data
    text = fd.read()

    # seek to the start of the file and truncate so file will be edited inline
    fd.seek(0)
    fd.truncate()

    for key in mappings.keys():
        text = text.replace(key, mappings[key])

    fd.write(text)
于 2013-09-12T23:59:15.440 回答