Я играл с 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
Что происходит на более низком уровне, что вызывает это?
Фактическая разница в скорости приближается к 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 быстры (путем их отключения [я думаю, это работает на утверждениях уровня 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]), и все готово.
Таким образом, для списков определенно меньше проверок, а небольшие различия в скорости, безусловно, подразумевают, что это может иметь значение.
Я думаю, что в целом для Unicode просто больше проверки типов и косвенности (->). Кажется, я что-то упускаю, но что?
get_latin1_char() больше не существует в unicode_getitem(), а находится в более низком уровне unicode_char. Итак, теперь есть другой уровень вызова функции - или нет (в зависимости от используемых компилятором и флагов оптимизации). На этом уровне детализации надежных ответов просто нет ;-)
- person Tim Peters; 27.05.2014
PyList_GetItem() - после проверки ошибок это просто return ((PyListObject *)op) -> ob_item[i]. Очень короткий и худой. Индексация строк не медленная, но код намного сложнее, чем для индексации списка.
- person Tim Peters; 27.05.2014
При переборе большинства объектов-контейнеров (списков, кортежей, словарей и т. д.) итератор доставляет объекты в контейнер.
Но когда вы перебираете строку, для каждого доставленного символа должен быть создан объект new — строка не является «контейнером» в том же смысле, что и список. Отдельные символы в строке не существуют как отдельные объекты до того, как итерация создаст эти объекты.
is. Это звучит правильно, но я действительно не думаю, что это возможно.
- person Veedrac; 26.05.2014
stringobject.c показывает, что __getitem__ для строк просто извлекает результат из таблицы сохраненных односимвольных строк, поэтому затраты на выделение для них возникают только один раз.
- person user2357112 supports Monica; 26.05.2014
s = chr(256), s is chr(256) возвращает False - одного знания типа недостаточно, потому что под обложками существует множество особых случаев, запускающих данные values.
- person Tim Peters; 27.05.2014
Вы можете понести накладные расходы на создание итератора для строки. Принимая во внимание, что массив уже содержит итератор при создании экземпляра.
РЕДАКТИРОВАТЬ:
>>> timeit("[x for x in ['a','b','c']]")
0.3818681240081787
>>> timeit("[x for x in 'abc']")
0.3732869625091553
Это было запущено с использованием 2.7, но на моем Mac Book Pro i7. Это может быть результатом разницы в конфигурации системы.
