3

今天我试图找到一种方法,对python中的字符串进行一些处理。一些比我说不使用+=但使用的高级程序员''.join()我也可以在例如:http ://wiki.python.org/moin/PythonSpeed/#Use_the_best_algorithms_and_fastest_tools 中阅读此内容。但是我自己对此进行了测试,发现了一些奇怪的结果(这不是我试图猜测它们,而是我想了解)。这个想法是如果有一个"This is \"an example text\"包含空格的字符串”字符串应该被转换为Thisis"an example text"containingspaces空格被删除,但只在引号之外。

我测量了我算法的两种不同版本的性能,一种使用 the ''.join(list),另一种使用+=

import time

#uses '+=' operator
def strip_spaces ( s ):
    ret_val = ""
    quote_found = False
    for i in s:
        if i == '"':
            quote_found = not quote_found

        if i == ' ' and quote_found == True:
            ret_val += i

        if i != ' ':
            ret_val += i
    return ret_val

#uses "".join ()   
def strip_spaces_join ( s ):
    #ret_val = ""
    ret_val = []
    quote_found = False
    for i in s:
        if i == '"':
            quote_found = not quote_found

        if i == ' ' and quote_found == True:
            #ret_val = ''.join( (ret_val, i) )
            ret_val.append(i)

        if i != ' ':
            #ret_val = ''.join( (ret_val,i) )
            ret_val.append(i)
    return ''.join(ret_val)


def time_function ( function, data):
    time1 = time.time();
    function(data)
    time2 = time.time()
    print "it took about {0} seconds".format(time2-time1)

在我的机器上,这产生了这个输出,对使用的算法有一点优势+=

print '#using += yields ', timeit.timeit('f(string)', 'from __main__ import string, strip_spaces as f', number=1000)
print '#using \'\'.join() yields ', timeit.timeit('f(string)', 'from __main__ import string, strip_spaces_join as f', number=1000)

当与 timeit 计时:

#using += yields  0.0130770206451
#using ''.join() yields  0.0108470916748

差别真的很小。但是为什么''.join()没有明确执行使用的功能+=,但 ''.join() 版本似乎有一点优势。我用 python-2.7.3 在 Ubuntu 12.04 上测试了这个

4

4 回答 4

8

在比较算法时使用正确的方法;使用该timeit模块来消除 CPU 利用率和交换的波动。

使用timeit显示两种方法之间几乎没有区别,但''.join()速度快:

>>> s = 1000 * string
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces as f', number=100)
1.3209099769592285
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces_join as f', number=100)
1.2893600463867188
>>> s = 10000 * string
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces as f', number=100)
14.545105934143066
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces_join as f', number=100)
14.43651008605957

函数中的大部分工作是循环每个字符并测试引号和空格,而不是字符串连接本身。此外,该''.join()变体做的工作更多;您首先将元素附加到列表中(这将替换+=字符串连接操作),然后在最后使用''.join(). 而且这种方法仍然稍微快一点。

您可能想要剥离正在完成的工作以比较连接部分:

def inplace_add_concatenation(s):
    res = ''
    for c in s:
        res += c

def str_join_concatenation(s):
    ''.join(s)

这表明:

>>> s = list(1000 * string)
>>> timeit.timeit('f(s)', 'from __main__ import s, inplace_add_concatenation as f', number=1000)
6.113742113113403
>>> timeit.timeit('f(s)', 'from __main__ import s, str_join_concatenation as f', number=1000)
0.6616439819335938

这表明串联''.join()仍然比. 速度差在于回路;在这两种情况下都是一个列表,但循环 C 中的值,而另一个版本必须完成它在 Python 中循环的所有工作。这让这里变得与众不同。+=s''.join()

于 2013-05-27T22:10:54.177 回答
3

另一种选择是编写一个使用生成器连接的函数,而不是每次都附加到列表中。

例如:

def strip_spaces_gen(s):
    quote_found = False
    for i in s:
        if i == '"':
            quote_found = not quote_found
        if i == ' ' and quote_found == True:
            # Note: you (c|sh)ould drop the == True, but I'll leave it here so as to not give an unfair advantage over the other functions
            yield i
        if i != ' ':
            yield i

def strip_spaces_join_gen(ing):
     return ''.join(strip_spaces_gen(ing))

对于较短的字符串,这似乎大致相同(作为连接):

In [20]: s = "This is \"an example text\" containing spaces"

In [21]: %timeit strip_spaces_join_gen(s)
10000 loops, best of 3: 22 us per loop

In [22]: %timeit strip_spaces(s)
100000 loops, best of 3: 13.8 us per loop

In [23]: %timeit strip_spaces_join(s)
10000 loops, best of 3: 23.1 us per loop

但对于较大的字符串更快。

In [24]: s = s * 1000

In [25]: %timeit strip_spaces_join_gen(s)
100 loops, best of 3: 12.9 ms per loop

In [26]: %timeit strip_spaces(s)
100 loops, best of 3: 17.1 ms per loop

In [27]: %timeit strip_spaces_join(s)
100 loops, best of 3: 17.5 ms per loop
于 2013-05-27T22:29:34.023 回答
3

(这可能是 OP 已经知道的很多细节,但是完整地解决这个问题可以帮助其他最终解决这个问题的人)

问题mystring += suffix在于字符串是不可变的,所以这实际上等价于mystring = mystring + suffix. 所以实现必须创建一个新的字符串对象,将所有字符从mystring上面复制到它,然后从suffix之后复制所有字符。然后mystring名称被反弹来引用新的字符串;被引用的原始字符串对象mystring未被触及。

就其本身而言,这实际上不是问题。连接这两个字符串的任何方法都必须这样做,包括''.join([mystring, suffix]); 这实际上更糟,因为它必须首先构造一个列表对象,然后对其进行迭代,虽然在拼接空字符串时没有实际的数据传输,但至少需要一条指令来整理。mystringsuffix

+=反复这样做时,问题就出现了。像这样的东西:

mystring = ''
for c in 'abcdefg' * 1000000:
    mystring += c

请记住,这mystring += c相当于mystring = mystring + c. 因此,在循环的第一次迭代中,它评估'' + 'a'总共复制 1 个字符。接下来,它'a' + 'b'总共复制 2 个字符。然后'ab' + 'c'是 3 个字符,然后'abc' + 'd'是 4 个字符,我想你可以看到这是怎么回事。每个后续+=都重复前一个的所有工作,然后也复制新字符串。这变得非常浪费。

''.join(...)更好,因为在那里你等到你知道所有字符串来复制它们中的任何一个,然后将每个字符串直接复制到最终字符串对象中的正确位置。与某些评论和答案所说的相反,即使您必须修改循环以将字符串附加到字符串列表,然后join在循环之后将它们附加,情况仍然如此。列表不是不可变的,因此追加到列表会修改它,并且它也只需要追加单个引用而不是复制字符串中的所有字符。对列表执行数千个附加操作比执行数千个字符串操作要快得多。+=

即使没有循环,重复的字符串+=理论上也是一个问题,如果你只是编写你的源代码,比如:

s = 'foo'
s += 'bar'
s += 'baz'
...

但在实践中,您不太可能手动编写足够长的代码序列,除非涉及的字符串非常庞大。所以只要注意+=循环(或递归函数)。


尝试计时时可能看不到此结果的原因是,实际上+=在 CPython 解释器中对字符串进行了优化。让我们回到我愚蠢的示例循环:

mystring = ''
for c in 'abcdefg' * 1000000:
    mystring += c

每次这样做时mystring = mystring + c值都会mystring变成垃圾并被删除,并且名称mystring最终会引用一个新创建的字符串,该字符串完全以旧对象的内容开头。我们可以通过识别它mystring即将变成垃圾来优化它,这样我们就可以在没有任何人关心的情况下做任何我们喜欢的事情。因此,即使字符串在 Python 级别是不可变的,但在实现级别,我们会让它们动态扩展,我们将target += source通过执行正常的分配新字符串和复制方法来实现,或者通过扩展目标字符串并仅复制源字符,取决于是否target会被做成垃圾

这种优化的问题在于它很容易被破坏。它在小型自包含循环上工作得非常好(顺便说一句,这是最容易转换为 usingjoin的)。但是,如果您正在做一些更复杂的事情,并且您不小心最终得到了多个对字符串的引用,那么代码会突然运行得慢很多。

假设您在循环中有一些日志记录调用,并且日志记录系统将其消息缓冲一段时间以便一次打印它们(应该是安全的;字符串是不可变的)。在日志系统中对您的字符串的引用可能会阻止+=优化的适用。

假设您已将循环编写为递归函数(Python 并不真正喜欢它,但仍然)+=出于某种原因构建了一个字符串。外部堆栈帧仍将引用旧值。

或者,您对字符串所做的事情可能是生成一系列对象,因此您将它们传递给一个类;如果类直接将字符串存储在实例中,优化就会消失,但如果类首先操作它们,那么优化仍然有效。

本质上,看起来像一个非常基本的原始操作的性能要么可以,要么很差,它取决于其他代码,而不是使用+=. 在极端情况下,您可能会对一个完全独立的文件(甚至可能是第三方包)进行更改,这会在您的一个模块中引入大量的性能退化,而该模块已经很长时间没有更改了!

另外,我的理解是+=优化只在 CPython 上很容易实现,因为它利用了引用计数;您可以通过查看目标字符串的引用计数轻松判断目标字符串何时为垃圾,而对于更复杂的垃圾收集,您只能在删除引用并等待垃圾收集器运行后才能判断;为时已晚,无法决定如何实施+=。再说一次,真正简单的基本代码在 Python 实现之间移植时不应该有任何问题,但当您将其移动到另一个实现时,它可能会突然运行得太慢而无法使用。


这里有一些基准测试来显示问题的规模:

import timeit

def plus_equals(data):
    s = ''
    for c in data:
        s += c

def simple_join(data):
    s = ''.join(data)

def append_join(data):
    l = []
    for c in data:
        l.append(c)
    s = ''.join(l)

def plus_equals_non_garbage(data):
    s = ''
    for c in data:
        dummy = s
        s += c

def plus_equals_maybe_non_garbage(data):
    s = ''
    for i, c in enumerate(data):
        if i % 1000 == 0:
            dummy = s
        s += c

def plus_equals_enumerate(data):
    s = ''
    for i, c in enumerate(data):
        if i % 1000 == -1:
            dummy = s
        s += c

data = ['abcdefg'] * 1000000

for f in (
    plus_equals,
    simple_join,
    append_join,
    plus_equals_non_garbage,
    plus_equals_maybe_non_garbage,
    plus_equals_enumerate,
  ):
    print '{:30}{:20.15f}'.format(f.__name__, timeit.timeit(
        'm.{0.__name__}(m.data)'.format(f),
        setup='import __main__ as m',
        number=1
    ))

在我的系统上打印:

plus_equals                      0.066924095153809
simple_join                      0.013648986816406
append_join                      0.086287975311279
plus_equals_non_garbage        540.663727998733521
plus_equals_maybe_non_garbage    0.731688976287842
plus_equals_enumerate            0.156824111938477

当它工作时,优化+=工作非常好(甚至比愚蠢的append_join版本略胜一筹)。我的数字表明,在某些情况下,您可能可以通过替换append+来优化代码,但这种好处不值得冒其他一些未来更改意外导致井喷的风险(如果有任何其他实际工作,很可能会变得微乎其微)在循环中进行;如果没有,那么您应该使用类似版本的东西)。join+=simple_join

通过比较plus_equals_maybe_non_garbage可以plus_equals_enumerate看出,即使优化只在千分之一+=的操作中失败,仍然有 5 倍的性能损失。

的优化+=实际上只是为了拯救那些没有经验的 Python 程序员,或者只是快速懒惰地编写一些草稿代码的人。如果您正在考虑自己在做什么,那么您应该使用join.


摘要:对于固定的少量连接,使用+=是很好的。使用循环来构建字符串总是更好。在实践中,由于优化,您可能看不到将代码移植到的巨大改进。无论如何,您仍然应该使用,因为优化是不可靠的,并且在它无法启动时的差异可能是巨大的。join+=join+=join

于 2013-05-28T06:48:28.133 回答
1

+=和之间的性能差异.join取决于很多因素:

  1. 操作系统。在类 unix 或 Windows 系统上为越来越大的字符串运行此命令会产生完全不同的结果。通常,您会看到在 Windows 下运行时间明显增加。

  2. Python 实现。默认情况下,我们谈论 CPython,但也有其他实现,例如 Jython 或 PyPy。让我们看看 PyPy。使用上面答案中的源代码:

    CPython 2.7:
    python concat.py 
    inplace_add_concatenation: 0.420897960663
    str_join_concatenation:    0.061793088913
    ratio: 6.81140833169
    
    PyPy 1.9:
    pypy concat.py 
    inplace_add_concatenation: 1.26573014259
    str_join_concatenation:    0.0392870903015
    ratio: 32.2174570038
    

尽管与 CPython 相比,PyPy 以加速而闻名,但它的+=版本却较慢。在 PyPy 的默认版本中不包含 `+=' 优化是故意的。

处理性能的经验法则:“永远不要猜测,永远衡量。”

阅读文档也有帮助:

6 CPython 实现细节:如果 s 和 t 都是字符串,一些 Python 实现(例如 CPython)通常可以对 s = s + t 或 s += t 形式的赋值执行就地优化。如果适用,这种优化会大大降低二次运行时间的可能性。这种优化既依赖于版本,也依赖于实现。对于性能敏感的代码,最好使用 str.join() 方法,该方法可确保跨版本和实现的线性连接性能一致。"""

来自http://docs.python.org/2/library/stdtypes.html#typesseq

于 2013-05-27T23:07:13.360 回答