代码之家 › 专栏 › 技术社区 › OTZ

在Python中进行多个字符串替换的最快实现

string python php

8

OTZ · 技术社区 · 16 年前

replace 在字符串上链接(即。 text.replace(a, b).replace(c, d).replace(e, f)... 例如,您将如何实现一个类似PHP的快速函数 htmlspecialchars 在Python中?

我比较了(1)倍数

n=10次,结果如下:

在100个字符上:

TIME: 0 ms [ replace_method(str) ]
TIME: 5 ms [ regular_expression_method(str, dict) ]
TIME: 1 ms [ matts_multi_replace_method(list, str) ]

在1000个字符上:

TIME: 0 ms [ replace_method(str) ]
TIME: 3 ms [ regular_expression_method(str, dict) ]
TIME: 2 ms [ matts_multi_replace_method(list, str) ]

TIME: 3 ms [ replace_method(str) ]
TIME: 7 ms [ regular_expression_method(str, dict) ]
TIME: 5 ms [ matts_multi_replace_method(list, str) ]

在100000个字符上:

TIME: 36 ms [ replace_method(str) ]
TIME: 46 ms [ regular_expression_method(str, dict) ]
TIME: 39 ms [ matts_multi_replace_method(list, str) ]

在1000000个字符上:

TIME: 318 ms [ replace_method(str) ]
TIME: 360 ms [ regular_expression_method(str, dict) ]
TIME: 320 ms [ matts_multi_replace_method(list, str) ]

在3687809个字符上:

TIME: 1.277524 sec [ replace_method(str) ]
TIME: 1.290590 sec [ regular_expression_method(str, dict) ]
TIME: 1.116601 sec [ matts_multi_replace_method(list, str) ]

代替 方法在相当大的输入字符串上。

有人有办法用一根更小的绳子来敲打它吗?

3 回复 | 直到 7 年前

1

6

Matt Anderson 16 年前

像下面这样的可能?用第一个要替换的“from”项将文本拆分为若干部分,然后用下一个要替换的“from”项将这些部分递归地拆分为若干子部分,依此类推,直到您访问了所有替换项。然后在递归函数完成时,为每个函数加入“to”替换项。

下面的代码可能有点难理解(它是为我写的,我自己写的),但它似乎能按预期运行。我没有对它进行基准测试,但我怀疑它会相当快。

def multi_replace(pairs, text):
    stack = list(pairs)
    stack.reverse()
    def replace(stack, parts):
        if not stack:
            return parts
        # copy the stack so I don't disturb parallel recursions
        stack = list(stack) 
        from_, to = stack.pop()
        #print 'split (%r=>%r)' % (from_, to), parts
        split_parts = [replace(stack, part.split(from_)) for part in parts]
        parts = [to.join(split_subparts) for split_subparts in split_parts]
        #print 'join (%r=>%r)' % (from_, to), parts
        return parts
    return replace(stack, [text])[0]


print multi_replace(
    [('foo', 'bar'), ('baaz', 'foo'), ('quux', 'moop')], 
    'foobarbaazfooquuxquux')

barbarfoobarmoopmoop

2

1

sophros 7 年前

.replace 方法胜过所有其他方法(请参见上面我的基准。)

3

0

Walter Mundt 16 年前

多快?还有,你的弦有多大?

有一个相当简单的问题 recipe

如果这还不够好,老实说,您可能需要编写一些C代码。您可以构建一个简单的状态机来执行所有替换,然后逐字节处理任何字符串,而不必沿着机器回溯来实际执行工作。然而,我怀疑你会击败正则表达式引擎不去C和优化。