DjangoBB LoFi version

Полная версия: Все таки, конкатенация строк сложением зло или нет?

Начало » Python для новичков » Все таки, конкатенация строк сложением зло или нет?

FishHook

Окт. 28, 2012 10:46:02

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 правильней и быстрее, а на деле получается как то все не так, как пишут.

sergeek

Окт. 28, 2012 10:57:00

Наверно подразумевалось что .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

dimy44

Окт. 28, 2012 11:20:38

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

odnochlen

Окт. 28, 2012 11:53:33

Я как-то об этом же создавал тему, только найти ее не могу. Как, с одной стороны, строки иммутабельные, а с другой - конкатекация за 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.

Типа для универсальности - или list и join, или StringIO, или bytearray. Для себя я не парюсь

PooH

Окт. 29, 2012 05:18:05

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

odnochlen

Окт. 29, 2012 09:00:46

Отсюда.

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

При сложении создается новый экземпляр строки и копируется содержимое старой. Где-то так:

a
aa
aaa
…

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

PooH

Окт. 29, 2012 11:37:55

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

Это шутка такая? Вы же внешний цикл в пример ввели, вот квадрат и появился

odnochlen

Окт. 29, 2012 11:44:04

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