Python中基于元组列表的迭代查找/替换

Question

我有一个元组列表，每个元组包含一个要查找和替换的值，我想将其应用于一个字符串。最有效的方法是什么？由于我将会迭代地应用它，因此性能是我最关心的问题。

更具体地说，processThis() 的内部应该是什么样子？

x = 'find1, find2, find3'
y = [('find1', 'replace1'), ('find2', 'replace2'), ('find3', 'replace3')]

def processThis(str,lst):
     # Do something here
     return something

>>> processThis(x,y)
'replace1, replace2, replace3'

感谢大家！

- c_harm

Answer 1

您可以考虑使用re.sub函数：

import re
REPLACEMENTS = dict([('find1', 'replace1'),
                     ('find2', 'replace2'),
                     ('find3', 'replace3')])

def replacer(m):
    return REPLACEMENTS[m.group(0)]

x = 'find1, find2, find3'
r = re.compile('|'.join(REPLACEMENTS.keys()))
print r.sub(replacer, x)

- mhawke

---

@cpharmston：使用replace()需要为每个替换调用一次。如果有许多替换和/或工作字符串很长，这将是低效的。re.sub()应该只处理一次工作字符串，但有一些设置开销。 - mhawke

Python已经维护了一个编译后的正则表达式缓存。请在你的Python目录下运行fgrep cache your_python_directory/Lib/re.py。 - John Machin

re.sub会逐步扫描文本中的每个位置，并测试该位置是否匹配“查找” - 没有自动机。时间复杂度为O（（文本大小）（“查找”数量）（平均“查找”大小））。多次使用str.replace（）：相同。然而：str.replace使用Boyer-Moore变体快速跳过文本，但会多次遍历文本，可能破坏内存缓存，并且会因为每次需要替换“查找”时都创建一个新的替换字符串而分割内存。re.sub只遍历文本一次，不跳过文本，并且仅创建一次repl字符串。re.sub可能是获胜者。进行基准测试。 - John Machin

当然可以。这是我的圆周率公式。有什么相关性吗？ - John Machin

@mhawke 抱歉挖掘一个古老的问题，但这对我非常有帮助。我的问题是...为什么REPLACEMENTS要大写？ - Amanda

Answer 2

一些注意事项：

1. 关于过早优化、基准测试、瓶颈、100 微不足道等常见论点。
2. 有些情况下，不同的解决方案会返回不同的结果。例如，如果 y = [('one', 'two'), ('two', 'three')] 且 x = 'one'，那么 mhawke 的解决方案将返回 'two'，而 Unknown 的解决方案将返回 'three'。
3. 在一个愚蠢的编造示例中测试了一下，mhawke 的解决方案稍微快了一点。不过，使用你自己的数据进行测试应该很容易。

- jtb

---

如果您愿意，我很想听一下常规参数。我始终是个新手 :) - chuckharmston

+1 指出结果不同，这很重要！ - mhawke

@cpharmston：每当像这样的问题出现在StackOverflow或其他地方时，总会有人抱怨除非这个函数实际上是应用程序的瓶颈，否则性能并不是最重要的考虑因素。他们会建议更好地关注边缘情况的正确性、可读性/可维护性甚至编程时间。我很讨厌成为那个人（下班后），因为这个讨论很有趣，但由于这个函数在渐进意义下是一致的，并且存在正确性差异，我想至少暗示一下这个论点。 - jtb

在StackOverflow上搜索“过早优化”以查看有关这些问题的大量讨论，甚至包括一个关于如何应对抱怨过早优化的相当元的问题 :-) http://stackoverflow.com/questions/438158/how-should-we-handle-premature-optimization-discussion-in-optimization-questions - jtb

啊，谢谢jtb。不过反对担心性能的论点很有道理，但我有两个反驳意见：（1）这最终将成为可重用的Django应用程序中的代码，因此在这种情况下，计划最坏情况可能是明智的选择。（2）我之所以将其作为学术练习，是为了帮助我学习Python。即使实际差异微不足道，通常也有正确的做事方式。关于正确方式的讨论（或分歧）通常会引导人们进行启发性的对话，就像这次一样。谢谢大家！ - chuckharmston

Answer 3

和 mhawke 的答案一样，使用 str_replace 方法进行封装

def str_replace(data, search_n_replace_dict):
    import re
    REPLACEMENTS = search_n_replace_dict

    def replacer(m):
        return REPLACEMENTS[m.group(0)]

    r = re.compile('|'.join(REPLACEMENTS.keys()))
    return r.sub(replacer, data)

然后我们可以像下面这样使用示例调用此方法

s = "abcd abcd efgh efgh;;;;;; lkmnkd kkkkk"
d = dict({ 'abcd' : 'aaaa', 'efgh' : 'eeee', 'mnkd' : 'mmmm' })


print (s)
print ("\n")
print(str_replace(s, d))

输出：

abcd abcd efgh efgh;;;;;; lkmnkd kkkkk


aaaa aaaa eeee eeee;;;;;; lkmmmm kkkkk

- leela

Answer 4

x = 'find1, find2, find3'
y = [('find1', 'replace1'), ('find2', 'replace2'), ('find3', 'replace3')]

def processThis(str,lst):
    for find, replace in lst:
        str = str.replace(find, replace)

    return str

>>> processThis(x,y)
'replace1, replace2, replace3'

- Unknown

---

你比我快了大约5秒钟 :) - Mathieu

谢谢，Unknown！这是一个明显的解决方案，效果很好，但我担心性能问题。如果y的长度为100，并且我在页面上应用它10次，那么我们将在一个页面中执行1000个离散的str.replace()调用。这对我来说似乎不太优化；难道正则表达式不更适合吗？ - chuckharmston

不，您仍然需要使用相同的 re.sub 函数和正则表达式。如果您想要绝对最快的速度，可能需要降到 C 级别来实现自己基于 switch 表进行替换的流式正则表达式。 - Unknown

我撤回我的原始评论。Mhawke的解决方案可能更快。我不确定re.sub是否只会在字符串上迭代一次，但是这个解决方案更经常进入C模式。你应该测试这个解决方案，看看它是否足够快，或者测试Mhawke的解决方案以确保。我确信它们要么差不多，要么在不同情况下一个更快。 - Unknown

"Unknown" 是错误的。使用包含所有要匹配的源字符串的正则表达式--"find1|find2|find3"--不会重复扫描字符串。请参考mhawke的答案。 - Glenn Maynard

快速测试： -在非常小的测试中，其中 len(y) = 3，在 30 个字符的字符串上运行三次且有 2 次替换时，str.replace() 稍微快一些（约 8%）。 -在中等大小的测试中，其中 len(y) = 20，在 200 个字符的字符串上运行 20 次且有 10 次替换时，re.sub() 明显快一些（约 22%）。 -在大型测试中，其中 len(y) = 500，在 5000 个字符的字符串上运行 500 次且有 25 次替换时，re.sub 明显更快（约 60%）。感谢大家的出色讨论！ - chuckharmston

Answer 5

s = reduce(lambda x, repl: str.replace(x, *repl), lst, s)

- Glenn Maynard