Python sum, why not strings? [closed]
6 ответов
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 укажет на это новичкам.
Кстати, это ограничение действует «навсегда», то есть с тех пор, как сумма была добавлена как встроенная функция ( rev. 32347 )
Вот источник: http://svn.python.org/view/python/trunk/Python/bltinmodule.c?revision=81029&view=markup
Во встроенной_сумме function у нас есть этот фрагмент кода:
/* 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);
}
Итак ... это ваш ответ.
Это явно проверено в коде и отклонено.
Edit: Переместил части о неизменяемости в историю.
В основном, это вопрос предварительного распределения. Когда вы используете оператор типа
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, однако, имеет задачу выяснить реальный размер строки до начала работы и поэтому теоретически выделит только один раз, в начале, а затем просто заполнит эту новую строку, что намного дешевле, чем другое решение.
Фактически вы можете использовать sum (..) для объединения строк, если вы используете соответствующий начальный объект! Конечно, если вы зайдете так далеко, вы уже достаточно поняли, чтобы использовать "". Join (..) в любом случае ..
>>> class ZeroObject(object):
... def __add__(self, other):
... return other
...
>>> sum(["hi", "there"], ZeroObject())
'hithere'
Из документации:
Предпочтительный и быстрый способ конкатенации последовательность строк путем вызова ''.join(sequence).
Заставив sum отказаться от операций над строками, Python побудил вас использовать правильный метод.
Краткий ответ: Эффективность.
Длинный ответ: функция 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²).
Таким образом, суммамин строк будет намного медленнее, чем суммамин чисел.
str.join не выделяет никаких промежуточных объектов. Он предварительно выделяет буфер, достаточно большой для хранения объединенных строк, и копирует строковые данные. Он выполняется за время O(N), намного быстрее, чем sum.