为什么迭代一个小string比一个小列表慢？

我正在玩timeit，注意到对一个小string做一个简单的列表理解要比在一个小单string列表上做同样的操作花费的时间要长。 任何解释？ 这几乎是时间的1.35倍。

>>> from timeit import timeit >>> timeit("[x for x in 'abc']") 2.0691067844831528 >>> timeit("[x for x in ['a', 'b', 'c']]") 1.5286479570345861 

什么发生在一个较低的水平，这是由此造成的？

Answer 1

TL; DR

• 一旦大量的开销被删除，实际的速度差异接近70％（或更多），Python 2。

• 对象创build没有错。 这两种方法都不会创build一个新的对象，因为一个字符的string被caching。

• 差别是不明显的，但可能是由于对string索引进行大量的检查而产生的，关于types和格式。 这也很有可能由于需要检查返回什么。

• 列表索引非常快。

---

---

 >>> 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 

你在这里看到，由于每次构build列表，列表变体可能会变慢。

这是

  9 LOAD_CONST 3 ('a') 12 LOAD_CONST 4 ('b') 15 LOAD_CONST 5 ('c') 18 BUILD_LIST 3 

部分。 string变体只有

  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')) 

因为元组是不可改变的。 testing：

 >>> 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行为exception快速。

让我们删除理解和重新时间。 _ =是为了防止它被优化。

 >>> 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改变了理解，有更安全的范围。

那么，现在改善基准（我只是删除不是迭代的开销）。 这通过预分配来移除迭代器的构build：

 >>> 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 

我们可以检查是否调用它是开销：

 >>> 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 

差异似乎很小，但至less有一半的成本是开销：

 >>> 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 

所以速度差异足以决定责怪它。 我认为。

那么为什么索引一个列表更快？

那么，我会回来给你，但我的猜测是，这是检查internedstring（或caching字符，如果它是一个单独的机制）。 这将比最佳速度快。 但我会去检查源（虽然我不舒服在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)的caching字符。

所以我们将运行（删除第一个检查）

 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) 

（这是无聊的，因为断言在debugging中被忽略[所以我可以检查他们很快]和((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)) 

（由于类似的原因，这也是无聊的，假设macros（ 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; } 

这证实了我的怀疑：

• 这被caching：

   PyObject *unicode = unicode_latin1[ch]; 

• 这应该是快的。 if (!unicode)没有运行，所以在这种情况下字面上相当于

   PyObject *unicode = unicode_latin1[ch]; Py_INCREF(unicode); return unicode; 

老实说，在testing之后， 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))) 

（如果macrosIS_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] ），我们就完成了。

所以列表的检查肯定比较less ，速度的小差别肯定意味着它可能是相关的。

---

我认为一般来说，Unicode只有更多的types检查和间接(->) 。 看来我错过了一点，但是什么 ？

Answer 2

当你遍历大部分容器对象（列表，元组，字典，…）时，迭代器传递容器中的对象。

但是当你迭代一个string时，必须为每个交付的字符创build一个新的对象 – 一个string不是“容器”，就像一个容器一样。 在迭代创build这些对象之前，string中的单个字符不作为不同的对象存在。

Answer 3

您可能会因为为string创build迭代器而招致开销。 数组在实例化时已经包含一个迭代器。

编辑：

 >>> timeit("[x for x in ['a','b','c']]") 0.3818681240081787 >>> timeit("[x for x in 'abc']") 0.3732869625091553 

这是运行使用2.7，但在我的MacBook Pro亲7。 这可能是系统configuration差异的结果。

Answer 4

无法确认Python 2的结果：在Python 2中，如果您迭代string或列表…并且元组相当快速，似乎没有什么区别！

 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