为什么迭代一个小字符串比小列表慢？
我正在玩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
在更低的层面上发生了什么？
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与bytestrings竞争。 我们可以通过以下两种方式尝试使用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
所以速度差异足以决定责怪它。 我认为。
那么为什么索引列表要快得多呢？
那么，我会回到你身上，但我的猜测是，这是检查interned字符串（或缓存字符，如果它是一个单独的机制）。 这将比最佳速度更快。 但我会去检查源代码（尽管我在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分钟内得到修复和合并。 像...是的。 该死的。 他们让Skeet感到羞耻。
#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] （ ((PyListObject *)op) -> ob_item[i] ），我们就完成了。
所以对列表的检查肯定比较少，而小的速度差异肯定意味着它可能是相关的。
我认为一般来说，Unicode只有更多的类型检查和间接(->) 。 看来我错过了一个观点，但是什么？
当迭代大多数容器对象（列表，元组，字典，...）时，迭代器会将容器中的对象传递出去。
但是，当你遍历一个字符串时，必须为每个交付的字符创建一个新的对象 - 一个字符串不是“容器”，就像一个容器一样。 在迭代创建这些对象之前，字符串中的单个字符不作为不同的对象存在。
您可能会因为为字符串创建迭代器而招致开销。 数组在实例化时已经包含一个迭代器。
编辑：
>>> timeit("[x for x in ['a','b','c']]")
0.3818681240081787
>>> timeit("[x for x in 'abc']")
0.3732869625091553
这是运行使用2.7，但在我的MacBook Pro亲7。 这可能是系统配置差异的结果。
链接地址: http://www.djcxy.com/p/31601.html上一篇: Why is it slower to iterate over a small string than a small list?