私は 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
これを引き起こしている低レベルで何が起こっているのでしょうか?
ベストアンサー1
要約
Python 2 の場合、オーバーヘッドの多くが削除されると、実際の速度の差は 70% (またはそれ以上) に近くなります。
オブジェクトの作成はない障害です。どちらの方法でも、1 文字の文字列がキャッシュされるため、新しいオブジェクトは作成されません。
違いは明らかではありませんが、文字列のインデックス作成において、型と整形式性に関するチェックの数が多いことから生じている可能性があります。また、何を返すかをチェックする必要があるためである可能性も高いです。
リストのインデックス作成は驚くほど高速です。
>>> 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 の方が高速です。これは当然のことです (
strPython 3 では多くの注目が集まっています)。
実際、この差unicodeはbytes非常に小さく、印象的です。
それでは、私にとっては速くて便利なこの 1 つのケースを分析してみましょう。
>>> 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
実際には、Tim Peter の 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 配列をインデックスで読み取るため高速です。結果 はch256 未満になるため、 にキャッシュされた文字を返します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;
正直に言うと、テスト後、assertsは高速です（無効にすることで[I考える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)
（
タブ！タブ！！！
) (
問題21587
）
それが修正され、統合されました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
したがって、がオンでない限り、これは通常非常に簡単です (2 つの間接参照といくつかのブール値チェック)。Py_LIMITED_APIオンの場合は... ???
次にインデックスとキャスト ( ((PyListObject *)op) -> ob_item[i]) を実行して完了です。
だから間違いなく少ないリストをチェックし、速度の差がわずかであることは、それが関連している可能性があることを確かに示唆しています。
一般的に、Unicodeでは型チェックと間接参照が多くなると思います(->)。私が見落としている点があるようですが、何?