Что в Python эффективнее? Изменение списков или строк?

Question

Независимо от простоты использования, что является более эффективным в вычислительном отношении? Постоянно нарезать списки и добавлять к ним? Или брать подстроки и делать то же самое?

В качестве примера, скажем, у меня есть две двоичные строки "11011" и "01001". Если я представлю их как списки, я буду выбирать случайную точку «среза». Допустим, я получаю 3. Я возьму первые 3 символа первой строки и оставшиеся символы второй строки (так что мне придется разрезать оба) и создам из нее новую строку.

Будет ли это более эффективно сделать путем вырезания подстрок или представления его в виде списка ([1, 1, 0, 1, 1]), а не строки?

Answer 1

>>> a = "11011"
>>> b = "01001"
>>> import timeit
>>> def strslice():
    return a[:3] + b[3:]

>>> def lstslice():
    return list(a)[:3] + list(b)[3:]
>>> c = list(a)
>>> d = list(b)
>>> def lsts():
    return c[:3] + d[3:]

>>> timeit.timeit(strslice)
0.5103488475836432
>>> timeit.timeit(lstslice)
2.4350100538824613
>>> timeit.timeit(lsts)
1.0648406858527295

Answer 2

timeit - хороший инструмент для микро-бенчмаркинга, но его нужно использовать с особой осторожностью, когда операции, которые вы хотите сравнить, могут включать изменения на месте - в этом случае вам необходимо включить дополнительные операции предназначен для изготовления необходимых копий. Тогда в первый раз просто «лишние» накладные расходы:

$ python -mtimeit -s'a="11011";b="01001"' 'la=list(a);lb=list(b)'
100000 loops, best of 3: 5.01 usec per loop
$ python -mtimeit -s'a="11011";b="01001"' 'la=list(a);lb=list(b)'
100000 loops, best of 3: 5.06 usec per loop

Таким образом, создание двух совершенно новых списков, которые нам нужны (чтобы избежать изменений), стоит чуть более 5 микросекунд (при фокусировке на небольшие различия запустите все как минимум 2-3 раза, чтобы взглянуть на диапазон неопределенности). После чего:

$ python -mtimeit -s'a="11011";b="01001"' 'la=list(a);lb=list(b);x=a[:3]+b[3:]'
100000 loops, best of 3: 5.5 usec per loop
$ python -mtimeit -s'a="11011";b="01001"' 'la=list(a);lb=list(b);x=a[:3]+b[3:]'
100000 loops, best of 3: 5.47 usec per loop

нарезка и конкатенация строк в этом случае могут стоить еще 410-490 наносекунд. И:

$ python -mtimeit -s'a="11011";b="01001"' 'la=list(a);lb=list(b);la[3:]=lb[3:]'
100000 loops, best of 3: 5.99 usec per loop
$ python -mtimeit -s'a="11011";b="01001"' 'la=list(a);lb=list(b);la[3:]=lb[3:]'
100000 loops, best of 3: 5.99 usec per loop

Объединение списка на месте может стоить 930-980 наносекунд. Разница безопасно выше уровней шума / неопределенности, поэтому вы можете с уверенностью утверждать, что для этого варианта использования работа со строками займет примерно вдвое меньше времени, чем работа со списками. Конечно, также важно измерить диапазон вариантов использования, которые соответствуют и типичны для ваших типичных узких мест!

Answer 3

Как правило, изменение списков более эффективно, чем изменение строк, поскольку строки являются неизменяемыми.

Answer 4

Это действительно зависит от реальных случаев использования, и, как уже говорили другие, профилируйте его, но в целом добавление в списки будет лучше, потому что это можно сделать на месте, тогда как «добавление к строкам» фактически создает новую строку это объединяет старые строки. Это может быстро съесть память. (Что на самом деле отличается от эффективности вычислений).

Редактировать: Если вы хотите вычислительной эффективности с двоичными значениями, не используйте строки или списки. Используйте целые и побитовые операции. В последних версиях Python вы можете использовать двоичные представления, когда они вам нужны:

>>> bin(42)
'0b101010'
>>> 0b101010
42
>>> int('101010')
101010
>>> int('101010', 2)
42
>>> int('0b101010')
...
ValueError: invalid literal for int() with base 10: '0b101010'
>>> int('0b101010', 2)
42

Редактировать 2:

def strslice(a, b):
    return a[:3] + b[3:]

может быть лучше написать что-то вроде:

def binspice(a, b):
    mask = 0b11100
    return (a & mask) + (b & ~mask)

>>> a = 0b11011
>>> b = 0b1001
>>> bin(binsplice(a, b))
'0b11001
>>> 

Возможно, потребуется изменить, если ваши двоичные числа имеют разные размеры.