Почему медленнее перебирать маленькую строку, чем маленький список?
Я поиграл с timeit и заметил, что простое понимание списка по маленькой строке заняло больше времени, чем выполнение той же операции со списком маленьких односимвольных строк. Любое объяснение? Это почти в 1,35 раза больше времени.
>>> from timeit import timeit
>>> timeit("[x for x in 'abc']")
2.0691067844831528
>>> timeit("[x for x in ['a', 'b', 'c']]")
1.5286479570345861
Что происходит на более низком уровне, что вызывает это?
4 ответа
TL;DR
Фактическая разница в скорости ближе к 70% (или больше) после удаления большого количества служебной информации для Python 2.
Создание объекта не виновато. Ни один из методов не создает новый объект, так как односимвольные строки кэшируются.
Разница неочевидна, но, вероятно, создается из-за большего числа проверок индексации строк в отношении типа и корректности. Это также вполне вероятно, благодаря необходимости проверить, что вернуть.
Индексирование списков происходит очень быстро.
>>> python3 -m timeit '[x for x in "abc"]'
1000000 loops, best of 3: 0.388 usec per loop
>>> python3 -m timeit '[x for x in ["a", "b", "c"]]'
1000000 loops, best of 3: 0.436 usec per loop
Это не соответствует тому, что вы нашли...
Тогда вы должны использовать Python 2.
>>> python2 -m timeit '[x for x in "abc"]'
1000000 loops, best of 3: 0.309 usec per loop
>>> python2 -m timeit '[x for x in ["a", "b", "c"]]'
1000000 loops, best of 3: 0.212 usec per loop
Давайте объясним разницу между версиями. Я проверю скомпилированный код.
Для Python 3:
import dis
def list_iterate():
[item for item in ["a", "b", "c"]]
dis.dis(list_iterate)
#>>> 4 0 LOAD_CONST 1 (<code object <listcomp> at 0x7f4d06b118a0, file "", line 4>)
#>>> 3 LOAD_CONST 2 ('list_iterate.<locals>.<listcomp>')
#>>> 6 MAKE_FUNCTION 0
#>>> 9 LOAD_CONST 3 ('a')
#>>> 12 LOAD_CONST 4 ('b')
#>>> 15 LOAD_CONST 5 ('c')
#>>> 18 BUILD_LIST 3
#>>> 21 GET_ITER
#>>> 22 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
#>>> 25 POP_TOP
#>>> 26 LOAD_CONST 0 (None)
#>>> 29 RETURN_VALUE
def string_iterate():
[item for item in "abc"]
dis.dis(string_iterate)
#>>> 21 0 LOAD_CONST 1 (<code object <listcomp> at 0x7f4d06b17150, file "", line 21>)
#>>> 3 LOAD_CONST 2 ('string_iterate.<locals>.<listcomp>')
#>>> 6 MAKE_FUNCTION 0
#>>> 9 LOAD_CONST 3 ('abc')
#>>> 12 GET_ITER
#>>> 13 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
#>>> 16 POP_TOP
#>>> 17 LOAD_CONST 0 (None)
#>>> 20 RETURN_VALUE
Здесь вы видите, что вариант списка, вероятно, будет медленнее из-за построения списка каждый раз.
Это
9 LOAD_CONST 3 ('a')
12 LOAD_CONST 4 ('b')
15 LOAD_CONST 5 ('c')
18 BUILD_LIST 3
часть. Вариант строки имеет только
9 LOAD_CONST 3 ('abc')
Вы можете проверить, что это, кажется, имеет значение:
def string_iterate():
[item for item in ("a", "b", "c")]
dis.dis(string_iterate)
#>>> 35 0 LOAD_CONST 1 (<code object <listcomp> at 0x7f4d068be660, file "", line 35>)
#>>> 3 LOAD_CONST 2 ('string_iterate.<locals>.<listcomp>')
#>>> 6 MAKE_FUNCTION 0
#>>> 9 LOAD_CONST 6 (('a', 'b', 'c'))
#>>> 12 GET_ITER
#>>> 13 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
#>>> 16 POP_TOP
#>>> 17 LOAD_CONST 0 (None)
#>>> 20 RETURN_VALUE
Это производит только
9 LOAD_CONST 6 (('a', 'b', 'c'))
как кортежи неизменны. Тестовое задание:
>>> python3 -m timeit '[x for x in ("a", "b", "c")]'
1000000 loops, best of 3: 0.369 usec per loop
Отлично, вернемся к скорости.
Для Python 2:
def list_iterate():
[item for item in ["a", "b", "c"]]
dis.dis(list_iterate)
#>>> 2 0 BUILD_LIST 0
#>>> 3 LOAD_CONST 1 ('a')
#>>> 6 LOAD_CONST 2 ('b')
#>>> 9 LOAD_CONST 3 ('c')
#>>> 12 BUILD_LIST 3
#>>> 15 GET_ITER
#>>> >> 16 FOR_ITER 12 (to 31)
#>>> 19 STORE_FAST 0 (item)
#>>> 22 LOAD_FAST 0 (item)
#>>> 25 LIST_APPEND 2
#>>> 28 JUMP_ABSOLUTE 16
#>>> >> 31 POP_TOP
#>>> 32 LOAD_CONST 0 (None)
#>>> 35 RETURN_VALUE
def string_iterate():
[item for item in "abc"]
dis.dis(string_iterate)
#>>> 2 0 BUILD_LIST 0
#>>> 3 LOAD_CONST 1 ('abc')
#>>> 6 GET_ITER
#>>> >> 7 FOR_ITER 12 (to 22)
#>>> 10 STORE_FAST 0 (item)
#>>> 13 LOAD_FAST 0 (item)
#>>> 16 LIST_APPEND 2
#>>> 19 JUMP_ABSOLUTE 7
#>>> >> 22 POP_TOP
#>>> 23 LOAD_CONST 0 (None)
#>>> 26 RETURN_VALUE
Странно то, что у нас одно и то же здание списка, но оно все равно быстрее для этого. Python 2 работает странно быстро.
Давайте удалим понимания и перенесем время. _ = чтобы предотвратить его оптимизацию.
>>> python3 -m timeit '_ = ["a", "b", "c"]'
10000000 loops, best of 3: 0.0707 usec per loop
>>> python3 -m timeit '_ = "abc"'
100000000 loops, best of 3: 0.0171 usec per loop
Мы видим, что инициализация не настолько значительна, чтобы учесть разницу между версиями (эти цифры невелики)! Таким образом, мы можем заключить, что Python 3 имеет более медленное понимание. Это имеет смысл, поскольку Python 3 изменил понимание, чтобы сделать его более безопасным.
Что ж, теперь улучшите тест (я просто убираю накладные расходы, которые не являются итерациями). Это удаляет создание итерируемого, предварительно назначая его:
>>> python3 -m timeit -s 'iterable = "abc"' '[x for x in iterable]'
1000000 loops, best of 3: 0.387 usec per loop
>>> python3 -m timeit -s 'iterable = ["a", "b", "c"]' '[x for x in iterable]'
1000000 loops, best of 3: 0.368 usec per loop
>>> python2 -m timeit -s 'iterable = "abc"' '[x for x in iterable]'
1000000 loops, best of 3: 0.309 usec per loop
>>> python2 -m timeit -s 'iterable = ["a", "b", "c"]' '[x for x in iterable]'
10000000 loops, best of 3: 0.164 usec per loop
Мы можем проверить, звонит ли iter это накладные расходы:
>>> python3 -m timeit -s 'iterable = "abc"' 'iter(iterable)'
10000000 loops, best of 3: 0.099 usec per loop
>>> python3 -m timeit -s 'iterable = ["a", "b", "c"]' 'iter(iterable)'
10000000 loops, best of 3: 0.1 usec per loop
>>> python2 -m timeit -s 'iterable = "abc"' 'iter(iterable)'
10000000 loops, best of 3: 0.0913 usec per loop
>>> python2 -m timeit -s 'iterable = ["a", "b", "c"]' 'iter(iterable)'
10000000 loops, best of 3: 0.0854 usec per loop
Нет, это не так. Разница слишком мала, особенно для Python 3.
Так что давайте уберем еще больше ненужных накладных расходов... сделав все это медленнее! Цель состоит в том, чтобы просто иметь более длинную итерацию, чтобы время скрывалось.
>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' '[x for x in iterable]'
100 loops, best of 3: 3.12 msec per loop
>>> python3 -m timeit -s 'import random; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' '[x for x in iterable]'
100 loops, best of 3: 2.77 msec per loop
>>> python2 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' '[x for x in iterable]'
100 loops, best of 3: 2.32 msec per loop
>>> python2 -m timeit -s 'import random; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' '[x for x in iterable]'
100 loops, best of 3: 2.09 msec per loop
На самом деле это не сильно изменилось, но немного помогло.
Так что удалите понимание. Это накладные расходы, это не часть вопроса:
>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'for x in iterable: pass'
1000 loops, best of 3: 1.71 msec per loop
>>> python3 -m timeit -s 'import random; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'for x in iterable: pass'
1000 loops, best of 3: 1.36 msec per loop
>>> python2 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'for x in iterable: pass'
1000 loops, best of 3: 1.27 msec per loop
>>> python2 -m timeit -s 'import random; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'for x in iterable: pass'
1000 loops, best of 3: 935 usec per loop
Это больше походит на это! Мы можем получить немного быстрее, используя deque повторять. Это в основном то же самое, но это быстрее:
>>> python3 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 777 usec per loop
>>> python3 -m timeit -s 'import random; from collections import deque; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 405 usec per loop
>>> python2 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 805 usec per loop
>>> python2 -m timeit -s 'import random; from collections import deque; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 438 usec per loop
Что меня впечатляет, так это то, что Unicode конкурирует с байтами. Мы можем проверить это явно, попробовав bytes а также unicode в обоих:
bytes>>> python3 -m timeit -s 'import random; from collections import deque; iterable = b"".join(chr(random.randint(0, 127)).encode("ascii") for _ in range(100000))' 'deque(iterable, maxlen=0)' :( 1000 loops, best of 3: 571 usec per loop >>> python3 -m timeit -s 'import random; from collections import deque; iterable = [chr(random.randint(0, 127)).encode("ascii") for _ in range(100000)]' 'deque(iterable, maxlen=0)' 1000 loops, best of 3: 394 usec per loop>>> python2 -m timeit -s 'import random; from collections import deque; iterable = b"".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)' 1000 loops, best of 3: 757 usec per loop >>> python2 -m timeit -s 'import random; from collections import deque; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)' 1000 loops, best of 3: 438 usec per loopЗдесь вы видите Python 3 на самом деле быстрее, чем Python 2.
unicode>>> python3 -m timeit -s 'import random; from collections import deque; iterable = u"".join( chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)' 1000 loops, best of 3: 800 usec per loop >>> python3 -m timeit -s 'import random; from collections import deque; iterable = [ chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)' 1000 loops, best of 3: 394 usec per loop>>> python2 -m timeit -s 'import random; from collections import deque; iterable = u"".join(unichr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)' 1000 loops, best of 3: 1.07 msec per loop >>> python2 -m timeit -s 'import random; from collections import deque; iterable = [unichr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)' 1000 loops, best of 3: 469 usec per loopОпять же, Python 3 работает быстрее, хотя этого и следовало ожидать (
strбыло много внимания в Python 3).
На самом деле это unicode - bytes Разница очень мала, что впечатляет.
Итак, давайте проанализируем этот случай, посмотрев, как это быстро и удобно для меня:
>>> python3 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 777 usec per loop
>>> python3 -m timeit -s 'import random; from collections import deque; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 405 usec per loop
Мы можем на самом деле исключить ответ Тима Питера с 10-кратным голосованием!
>>> foo = iterable[123]
>>> iterable[36] is foo
True
Это не новые объекты!
Но стоит упомянуть: индексация затрат. Разница скорее всего будет в индексации, поэтому удалите итерацию и просто индексируйте:
>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'iterable[123]'
10000000 loops, best of 3: 0.0397 usec per loop
>>> python3 -m timeit -s 'import random; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'iterable[123]'
10000000 loops, best of 3: 0.0374 usec per loop
Разница кажется небольшой, но по крайней мере половина затрат накладные расходы:
>>> python3 -m timeit -s 'import random; iterable = [chr(random.randint(0, 127)) for _ in range(100000)]' 'iterable; 123'
100000000 loops, best of 3: 0.0173 usec per loop
таким образом, разница в скорости достаточна, чтобы принять решение обвинить в этом. Я думаю.
Так почему же индексирование списка происходит намного быстрее?
Что ж, я вернусь к вам по этому вопросу, но я предполагаю, что это связано с проверкой интернированных строк (или кэшированных символов, если это отдельный механизм). Это будет менее быстро, чем оптимально. Но я пойду проверю источник (хотя мне не комфортно в C...):).
Итак, вот источник:
static PyObject *
unicode_getitem(PyObject *self, Py_ssize_t index)
{
void *data;
enum PyUnicode_Kind kind;
Py_UCS4 ch;
PyObject *res;
if (!PyUnicode_Check(self) || PyUnicode_READY(self) == -1) {
PyErr_BadArgument();
return NULL;
}
if (index < 0 || index >= PyUnicode_GET_LENGTH(self)) {
PyErr_SetString(PyExc_IndexError, "string index out of range");
return NULL;
}
kind = PyUnicode_KIND(self);
data = PyUnicode_DATA(self);
ch = PyUnicode_READ(kind, data, index);
if (ch < 256)
return get_latin1_char(ch);
res = PyUnicode_New(1, ch);
if (res == NULL)
return NULL;
kind = PyUnicode_KIND(res);
data = PyUnicode_DATA(res);
PyUnicode_WRITE(kind, data, 0, ch);
assert(_PyUnicode_CheckConsistency(res, 1));
return res;
}
Идя сверху, у нас будет несколько проверок. Это скучно. Тогда некоторые задания, которые тоже должны быть скучными. Первая интересная строка
ch = PyUnicode_READ(kind, data, index);
но мы надеемся, что это быстро, так как мы читаем из непрерывного массива C, индексируя его. Результат, ch, будет меньше 256, поэтому мы вернем кешированный символ в get_latin1_char(ch),
Итак, мы побежим (сбросив первые чеки)
kind = PyUnicode_KIND(self);
data = PyUnicode_DATA(self);
ch = PyUnicode_READ(kind, data, index);
return get_latin1_char(ch);
куда
#define PyUnicode_KIND(op) \
(assert(PyUnicode_Check(op)), \
assert(PyUnicode_IS_READY(op)), \
((PyASCIIObject *)(op))->state.kind)
(что скучно, потому что утверждения игнорируются при отладке [поэтому я могу проверить, что они быстрые) и ((PyASCIIObject *)(op))->state.kind) является (я думаю) косвенным и броском C-уровня);
#define PyUnicode_DATA(op) \
(assert(PyUnicode_Check(op)), \
PyUnicode_IS_COMPACT(op) ? _PyUnicode_COMPACT_DATA(op) : \
_PyUnicode_NONCOMPACT_DATA(op))
(что также скучно по тем же причинам, предполагая, что макросы Something_CAPITALIZED) все быстро),
#define PyUnicode_READ(kind, data, index) \
((Py_UCS4) \
((kind) == PyUnicode_1BYTE_KIND ? \
((const Py_UCS1 *)(data))[(index)] : \
((kind) == PyUnicode_2BYTE_KIND ? \
((const Py_UCS2 *)(data))[(index)] : \
((const Py_UCS4 *)(data))[(index)] \
) \
))
(который включает в себя индексы, но на самом деле совсем не медленный) и
static PyObject*
get_latin1_char(unsigned char ch)
{
PyObject *unicode = unicode_latin1[ch];
if (!unicode) {
unicode = PyUnicode_New(1, ch);
if (!unicode)
return NULL;
PyUnicode_1BYTE_DATA(unicode)[0] = ch;
assert(_PyUnicode_CheckConsistency(unicode, 1));
unicode_latin1[ch] = unicode;
}
Py_INCREF(unicode);
return unicode;
}
Что подтверждает мое подозрение, что:
Это кешируется:
PyObject *unicode = unicode_latin1[ch];Это должно быть быстро.
if (!unicode)не запускается, так что это буквально эквивалентно в этом случаеPyObject *unicode = unicode_latin1[ch]; Py_INCREF(unicode); return unicode;
Честно говоря, после тестирования assert s бывают быстрыми (отключая их [я думаю, что это работает на утверждениях уровня C...]), единственно правдоподобно медленные части:
PyUnicode_IS_COMPACT(op)
_PyUnicode_COMPACT_DATA(op)
_PyUnicode_NONCOMPACT_DATA(op)
Которые:
#define PyUnicode_IS_COMPACT(op) \
(((PyASCIIObject*)(op))->state.compact)
(быстро, как и раньше),
#define _PyUnicode_COMPACT_DATA(op) \
(PyUnicode_IS_ASCII(op) ? \
((void*)((PyASCIIObject*)(op) + 1)) : \
((void*)((PyCompactUnicodeObject*)(op) + 1)))
(быстро, если макрос IS_ASCII быстро) и
#define _PyUnicode_NONCOMPACT_DATA(op) \
(assert(((PyUnicodeObject*)(op))->data.any), \
((((PyUnicodeObject *)(op))->data.any)))
(также быстро, как это утверждают плюс косвенность плюс приведение).
Таким образом, мы вниз (кроличья нора), чтобы:
PyUnicode_IS_ASCII
который
#define PyUnicode_IS_ASCII(op) \
(assert(PyUnicode_Check(op)), \
assert(PyUnicode_IS_READY(op)), \
((PyASCIIObject*)op)->state.ascii)
Хм... это тоже кажется быстрым...
Хорошо, хорошо, но давайте сравним это с PyList_GetItem, (Да, спасибо Тиму Питерсу за предоставленную мне дополнительную работу:P.)
PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
if (!PyList_Check(op)) {
PyErr_BadInternalCall();
return NULL;
}
if (i < 0 || i >= Py_SIZE(op)) {
if (indexerr == NULL) {
indexerr = PyUnicode_FromString(
"list index out of range");
if (indexerr == NULL)
return NULL;
}
PyErr_SetObject(PyExc_IndexError, indexerr);
return NULL;
}
return ((PyListObject *)op) -> ob_item[i];
}
Мы можем видеть, что в случаях отсутствия ошибок это просто будет работать:
PyList_Check(op)
Py_SIZE(op)
((PyListObject *)op) -> ob_item[i]
куда PyList_Check является
#define PyList_Check(op) \
PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_LIST_SUBCLASS)
( TABS! TABS!!!) ( issue21587) Это исправлено и объединено за 5 минут. Как... да. Черт. Они ставят Скита в позор.
#define Py_SIZE(ob) (((PyVarObject*)(ob))->ob_size)
#define PyType_FastSubclass(t,f) PyType_HasFeature(t,f)
#ifdef Py_LIMITED_API
#define PyType_HasFeature(t,f) ((PyType_GetFlags(t) & (f)) != 0)
#else
#define PyType_HasFeature(t,f) (((t)->tp_flags & (f)) != 0)
#endif
Так что это обычно действительно тривиально (две косвенные и несколько логических проверок), если Py_LIMITED_API в каком случае...???
Тогда есть индексация и приведение (((PyListObject *)op) -> ob_item[i]) и мы закончили.
Таким образом, определенно меньше проверок для списков, и небольшие различия в скорости, безусловно, подразумевают, что это может быть актуально.
Я думаю, в общем, просто больше проверки типов и косвенного обращения (->) для Юникода. Кажется, мне не хватает точки, но что?
Когда вы перебираете большинство контейнерных объектов (списки, кортежи, dicts, ...), итератор доставляет объекты в контейнер.
Но когда вы перебираете строку, для каждого доставленного символа должен быть создан новый объект - строка не является "контейнером" в том же смысле, что список является контейнером. Отдельные символы в строке не существуют как отдельные объекты до того, как итерация создаст эти объекты.
Вы можете понести расходы на создание итератора для строки. В то время как массив уже содержит итератор при создании экземпляра.
РЕДАКТИРОВАТЬ:
>>> timeit("[x for x in ['a','b','c']]")
0.3818681240081787
>>> timeit("[x for x in 'abc']")
0.3732869625091553
Это запускалось с использованием 2.7, но на моем MacBook Pro i7. Это может быть результатом различий в конфигурации системы.
Невозможно подтвердить результаты для Python 2: В Python 2, кажется, не имеет значения, если вы перебираете строки или списки... и кортежи довольно быстрые!
import platform
print('Python', platform.python_version())
%timeit [c for c in 'abcd']
%timeit [c for c in ['a', 'b', 'c', 'd']]
%timeit [c for c in ('a', 'b', 'c', 'd')]
Python 3.4.0
1000000 loops, best of 3: 502 ns per loop
1000000 loops, best of 3: 638 ns per loop
1000000 loops, best of 3: 475 ns per loop
import platform
print 'Python', platform.python_version()
%timeit [c for c in 'abcd']
%timeit [c for c in ['a', 'b', 'c', 'd']]
%timeit [c for c in ('a', 'b', 'c', 'd')]
Python 2.7.6
1000000 loops, best of 3: 458 ns per loop
1000000 loops, best of 3: 464 ns per loop
1000000 loops, best of 3: 280 ns per loop