为什么list元素替换比python中的字符串元素替换慢？

Question

我试图将数据结构中的一组元素替换为其他值.在python的情况下,在字符串中进行这种替换似乎比在列表中快得多(如下面的基准测试所示).有人可以解释原因.

注意:这些测试是使用python 2.7执行的.

def string_replace_test(s, chars):
    """Replaces a set of chars to 0"""
    new = s
    for c in chars:
        new = new.replace(c, '0')
    return new

def list_replace_test(s, chars):
    """Replaces a set of chars to 0"""
    for a in xrange(len(s)):
        if s[a] in chars:
            s[a] = '0'

if __name__ == '__main__':
    import timeit
    s = """
        Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec
        etfringilla purus. Pellentesque bibendum urna at neque consectetur
        at tincidunt nulla luctus. Pellentesque augue lacus, interdum id
        lectus vitae, laoreet suscipit arcu.
        """
    s2 = list(s)
    chars = ['a', 'e', 'i', 'o', 'u']
    print(timeit.timeit("string_replace_test(s, chars)", setup="from __main__ import string_replace_test, s, chars"))
    print(timeit.timeit("list_replace_test(s2, chars)", setup="from __main__ import list_replace_test, s2, chars"))

输出:

5.09572291374
49.3243050575

使用range():

5.01253795624
53.2320859432

Answer 1

由于没有list.replace()功能,你建立了自己的,但选择了一个慢的方法.

改为使用列表理解:

def list_replace_test(s, chars):
    """Replaces a set of chars to 0"""
    return [a if a not in chars else '0' for a in s]

这仍然比字符串替换慢,因为你无法在这里避免Python循环.

使用一组chars帮助:

chars = set(chars)

但是,替换文本中单个字符的最快方法实际上是一种不同的技术.使用str.translate()为:

from string import maketrans

map = maketrans('aeiou', '0' * 5)
def str_translate(s, map):
    return s.translate(map)

随着这些变化,时间变为:

>>> timeit.timeit("list_replace_test(s2, chars)", setup="from __main__ import list_replace_test, s2, chars")
28.60542392730713
>>> timeit.timeit("string_replace_test(s, chars)", setup="from __main__ import string_replace_test, s, chars")
4.002871990203857
>>> timeit.timeit("str_translate(s, map)", setup="from __main__ import str_translate, s, map")
0.7250571250915527

str.replace()从水中吹出的循环呼叫也是如此.

Answer 2

差异主要是由于这str.replace是一个用C语言实现的方法,它可以在字符串上迭代得更快.它也可以使用更简单的比较(使用简单的C函数)而不是调用python方法.

你可以很容易地看到巨大的不同:

In [3]: s = """
   ...:      Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec
   ...:      etfringilla purus. Pellentesque bibendum urna at neque consectetur
   ...:      at tincidunt nulla luctus. Pellentesque augue lacus, interdum id
   ...:      lectus vitae, laoreet suscipit arcu.
   ...:      """

In [4]: s2 = list(s)

In [5]: %%timeit
   ...: s.replace('a', '0')
   ...: 
1000000 loops, best of 3: 545 ns per loop

In [6]: %%timeit
   ...: for i, el in enumerate(s2):
   ...:     if el == 'a':
   ...:         s2[i] = '0'
   ...: 
100000 loops, best of 3: 17.9 us per loop
In [7]: 17.9 * 1000 / 545
Out[7]: 32.84403669724771

正如您所看到的,str.replace运行速度比纯python循环快33倍.即使您想要替换多个元音时列表代码应该更快(特别是如果您使用集合而不是列表作为chars参数),要替换的字符数必须很大才能使代码足够有效.

例如:

In [14]: %%timeit
    ...: for i, el in enumerate(s2):
    ...:     if el in 'abcdefghijklmnopqrstuvwxyz':
    ...:         s2[i] = '0'
    ...: 
100000 loops, best of 3: 16.4 us per loop

请注意,时间几乎与以前相同,而:

In [17]: %%timeit S = s
    ...: for c in 'abcdefghijklmnopqrstuvwxyz':
    ...:     S = S.replace(c, '0')
    ...: 
100000 loops, best of 3: 5.63 us per loop

仍然更快,但时间增加了10倍.

实际上,从字符串中更改某些字符的最快方法是使用该translate方法,该方法允许replace通过单个调用执行多个s:

In [1]: import string

In [2]: table = string.maketrans('aeiou', '00000')

In [3]: s = """
   ...:      Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec
   ...:      etfringilla purus. Pellentesque bibendum urna at neque consectetur
   ...:      at tincidunt nulla luctus. Pellentesque augue lacus, interdum id
   ...:      lectus vitae, laoreet suscipit arcu.
   ...:      """

In [4]: %timeit s.translate(table)
1000000 loops, best of 3: 557 ns per loop

请注意,它需要与单个时间相同的时间,str.replace但它在一次传递中执行所有替换,就像您对列表所拥有的代码一样.

请注意,在python3中str.translate将比在python2中慢得多,特别是如果你只翻译几个字符.这是因为它必须处理unicode字符,因此使用a dict来执行转换而不是索引字符串.