Python-сообщество

python 2.7

def f1():
  d=''
  for i in range(1000):
    d+=str(i)
  return d
  
def f2():
  d=[]
  for i in range(1000):
      d.append(str(i))
  return ''.join(d)
  
if __name__ == '__main__':
    import timeit
    print timeit.timeit("f1()", setup="from __main__ import f1")
    print timeit.timeit("f2()", setup="from __main__ import f2")

220.748425007
249.266052008

Наверно подразумевалось что .join лучше использовать в таких случаях:

def f1(ls):
    res = ''
    for n in ls:
        res += n
    return res
def f2(ls):
    return ''.join(ls)
%%timeit
f1(['asdbdf', 'ewfwef', '123123'])
1000000 loops, best of 3: 348 ns per loop
%%timeit
f2(['asdbdf', 'ewfwef', '123123'])
1000000 loops, best of 3: 233 ns per loop

Насколько помню, в старых версиях питона конкатенация работала медленно, но в новых версиях ее оптимизировали и она стала чуть быстрее join.

Я как-то об этом же создавал тему, только найти ее не могу. Как, с одной стороны, строки иммутабельные, а с другой - конкатекация за O(n)?

http://docs.python.org/2/library/stdtypes.html#sequence-types-str-unicode-list-tuple-bytearray-buffer-xrange

6. CPython implementation detail: If s and t are both strings, some Python implementations such as CPython can usually perform an in-place optimization for assignments of the form s = s + t or s += t. When applicable, this optimization makes quadratic run-time much less likely. This optimization is both version and implementation dependent. For performance sensitive code, it is preferable to use the str.join() method which assures consistent linear concatenation performance across versions and implementations.

Changed in version 2.4: Formerly, string concatenation never occurred in-place.

Что-то я перечитываю этот кусок доки и никак понять не могу, откуда при конкатенации строк появляется квадратичная сложность, с которой они борются?

Отсюда.

s = ""
for t in range(2**16):
    s += 'a'

odnochlen
Видим арифметическую прогрессию, а сумма арифметической прогрессии n*(n+1)/2 => O(n**2) символов надо копировать для создании строки длиной n.

Проблемы возникают только в цикле, когда таки O(n**2). Цикл, не указан, да. Он, кстати, есть и в твоем примере. Для трех переменных можно писать + и не париться.

Отредактировано odnochlen (Окт. 29, 2012 11:44:46)