Сумма Python, почему бы не строки?

Ответ 1

Python пытается отговорить вас от "суммирования" строк. Вы должны присоединиться к ним:

"".join(list_of_strings)

Это намного быстрее и использует гораздо меньше памяти.

Быстрый тест:

$ python -m timeit -s 'import operator; strings = ["a"]*10000' 'r = reduce(operator.add, strings)'
100 loops, best of 3: 8.46 msec per loop
$ python -m timeit -s 'import operator; strings = ["a"]*10000' 'r = "".join(strings)'
1000 loops, best of 3: 296 usec per loop

Изменить (чтобы ответить на редактирование OP). Что касается того, почему строки были, по-видимому, "выделены", я считаю, что это просто вопрос оптимизации для общего случая, а также для обеспечения наилучшей практики: вы можете присоединяться к строкам намного быстрее с помощью '.join, поэтому явно запрещающие строки на sum укажут это на новичков.

BTW, это ограничение было "навсегда", т.е. поскольку sum был добавлен как встроенная функция (rev. 32347)

Ответ 2

Фактически вы можете использовать sum(..) для конкатенации строк, если вы используете соответствующий начальный объект! Конечно, если вы заходите так далеко, вы уже достаточно поняли, чтобы использовать "".join(..) в любом случае..

>>> class ZeroObject(object):
...  def __add__(self, other):
...   return other
...
>>> sum(["hi", "there"], ZeroObject())
'hithere'

Ответ 3

Здесь источник: http://svn.python.org/view/python/trunk/Python/bltinmodule.c?revision=81029&view=markup

В функции builtin_sum мы имеем этот бит кода:

     /* reject string values for 'start' parameter */
        if (PyObject_TypeCheck(result, &PyBaseString_Type)) {
            PyErr_SetString(PyExc_TypeError,
                "sum() can't sum strings [use ''.join(seq) instead]");
            Py_DECREF(iter);
            return NULL;
        }
        Py_INCREF(result);
    }

Итак, вот ваш ответ.

Он явно проверяется в коде и отклоняется.

Ответ 4

От документы:

Предпочтительный, быстрый способ конкатенировать последовательность строк - это вызов ''.join(последовательность).

Отменив sum для работы с строками, Python предложил вам использовать правильный метод.

Ответ 5

Краткий ответ: эффективность.

Длинный ответ: функция sum должна создать объект для каждой частичной суммы.

Предположим, что время, необходимое для создания объекта, прямо пропорционально размеру его данных. Пусть N обозначает количество элементов в последовательности, чтобы суммировать.

double всегда имеют одинаковый размер, что делает sum время работы O (1) × N = O (N).

int (ранее известный как long) имеет длину. Обозначим через M абсолютное значение наибольшего элемента последовательности. Тогда sum наихудшее время работы: lg (M) + lg (2M) + lg (3M) +... + lg (NM) = N × lg (M) + lg (N!) = O (N log N).

Для str (где M = длина самой длинной строки) наихудшее время работы: M + 2M + 3M +... + NM = M × (1 + 2 +... + N ) = O (N²).

Таким образом, строки sum ming будут намного медленнее, чем числа sum ming.

str.join не выделяет никаких промежуточных объектов. Он предопределяет буфер, достаточно большой для хранения объединенных строк, и копирует строковые данные. Он работает в O (N) времени, намного быстрее, чем sum.

Ответ 6

Причина Почему

@dan04 имеет отличное объяснение затрат на использование sum в больших списках строк.

Недопустимая часть вопроса о том, почему str не разрешена для sum, заключается в том, что многие, многие люди пытались использовать sum для строк, и не многие используют sum для списков и кортежей и других O ( n ** 2) структуры данных. Ловушка заключается в том, что sum отлично подходит для коротких списков строк, но затем запускается в производство, где списки могут быть огромными, а производительность замедляется до обхода. Это была такая общая ловушка, что было принято решение игнорировать утиную печать в этом случае и не допускать использования строк с помощью sum.

Ответ 7

Изменить: Перемещено части об неизменяемости в историю.

В принципе, это вопрос предварительного распределения. Когда вы используете инструкцию типа

sum(["a", "b", "c", ..., ])

и ожидать, что он будет работать аналогично оператору reduce, генерируемый код выглядит примерно так:

v1 = "" + "a" # must allocate v1 and set its size to len("") + len("a")
v2 = v1 + "b" # must allocate v2 and set its size to len("a") + len("b")
...
res = v10000 + "$" # must allocate res and set its size to len(v9999) + len("$")

В каждом из этих шагов создается новая строка, которая может дать некоторые накладные расходы на копирование, поскольку строки становятся длиннее и длиннее. Но, может быть, и не здесь. Более важно то, что каждая новая строка в каждой строке должна быть выделена для ее определенного размера (который я не знаю, что он должен выделять на каждой итерации оператора reduce, могут быть некоторые очевидные эвристики для использования, и Python может выделите немного больше здесь и там для повторного использования, но в нескольких точках новая строка будет достаточно большой, чтобы это больше не помогло, и Python должен снова выделить, что довольно дорого.

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

Ответ 8

Я не знаю почему, но это работает!

import operator
def sum_of_strings(list_of_strings):
    return reduce(operator.add, list_of_strings)