[解決済み】('x',)の'x'は'x'=='x'よりも速いのはなぜか?
質問
>>> timeit.timeit("'x' in ('x',)")
0.04869917374131205
>>> timeit.timeit("'x' == 'x'")
0.06144205736110564
また、複数の要素を持つタプルでも動作し、どちらのバージョンも線形に成長するようです。
>>> timeit.timeit("'x' in ('x', 'y')")
0.04866674801541748
>>> timeit.timeit("'x' == 'x' or 'x' == 'y'")
0.06565782838087131
>>> timeit.timeit("'x' in ('y', 'x')")
0.08975995576448526
>>> timeit.timeit("'x' == 'y' or 'x' == 'y'")
0.12992391047427532
これを踏まえて、私は次のように考えています。
まったく
を使い始める。
in
の代わりに、あらゆる場所で
==
!
解決方法は?
David Woleverに話したように、これには見た目以上の意味がある。
is
を実行することによって証明することができます。
min(Timer("x == x", setup="x = 'a' * 1000000").repeat(10, 10000))
#>>> 0.00045456900261342525
min(Timer("x == y", setup="x = 'a' * 1000000; y = 'a' * 1000000").repeat(10, 10000))
#>>> 0.5256857610074803
1つ目は、IDでチェックするため、高速化しかできない。
なぜ片方が時間がかかるのか、その理由を知るために、実行状況をトレースしてみましょう。
どちらも
ceval.c
から
COMPARE_OP
これが関係するバイトコードであるため
TARGET(COMPARE_OP) {
PyObject *right = POP();
PyObject *left = TOP();
PyObject *res = cmp_outcome(oparg, left, right);
Py_DECREF(left);
Py_DECREF(right);
SET_TOP(res);
if (res == NULL)
goto error;
PREDICT(POP_JUMP_IF_FALSE);
PREDICT(POP_JUMP_IF_TRUE);
DISPATCH();
}
これはスタックから値をポップします(厳密には1つだけポップします)。
PyObject *right = POP();
PyObject *left = TOP();
と入力し、比較を実行します。
PyObject *res = cmp_outcome(oparg, left, right);
cmp_outcome
はこれです。
static PyObject *
cmp_outcome(int op, PyObject *v, PyObject *w)
{
int res = 0;
switch (op) {
case PyCmp_IS: ...
case PyCmp_IS_NOT: ...
case PyCmp_IN:
res = PySequence_Contains(w, v);
if (res < 0)
return NULL;
break;
case PyCmp_NOT_IN: ...
case PyCmp_EXC_MATCH: ...
default:
return PyObject_RichCompare(v, w, op);
}
v = res ? Py_True : Py_False;
Py_INCREF(v);
return v;
}
ここでパスが分岐します。その
PyCmp_IN
ブランチが行います。
int
PySequence_Contains(PyObject *seq, PyObject *ob)
{
Py_ssize_t result;
PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
if (sqm != NULL && sqm->sq_contains != NULL)
return (*sqm->sq_contains)(seq, ob);
result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);
}
タプルは次のように定義されることに注意してください。
static PySequenceMethods tuple_as_sequence = {
...
(objobjproc)tuplecontains, /* sq_contains */
};
PyTypeObject PyTuple_Type = {
...
&tuple_as_sequence, /* tp_as_sequence */
...
};
そこで、ブランチ
if (sqm != NULL && sqm->sq_contains != NULL)
が取られ
*sqm->sq_contains
であり、これは関数
(objobjproc)tuplecontains
が取られます。
これは
static int
tuplecontains(PyTupleObject *a, PyObject *el)
{
Py_ssize_t i;
int cmp;
for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
Py_EQ);
return cmp;
}
...待てよ、これは
PyObject_RichCompareBool
もう一方のブランチが取ったもの?いや、あれは
PyObject_RichCompare
.
このコードパスは短かったので、おそらくこの2つのスピードの違いだけでしょう。比較してみましょう。
int
PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
{
PyObject *res;
int ok;
/* Quick result when objects are the same.
Guarantees that identity implies equality. */
if (v == w) {
if (op == Py_EQ)
return 1;
else if (op == Py_NE)
return 0;
}
...
}
のコードパスは
PyObject_RichCompareBool
はすぐに終了してしまいます。例えば
PyObject_RichCompare
を実行します。
PyObject *
PyObject_RichCompare(PyObject *v, PyObject *w, int op)
{
PyObject *res;
assert(Py_LT <= op && op <= Py_GE);
if (v == NULL || w == NULL) { ... }
if (Py_EnterRecursiveCall(" in comparison"))
return NULL;
res = do_richcompare(v, w, op);
Py_LeaveRecursiveCall();
return res;
}
は
Py_EnterRecursiveCall
/
Py_LeaveRecursiveCall
のコンボは前のパスで取られていませんが、これらはいくつかのグローバルのインクリメントとデクリメントを行った後にショートカットする、比較的迅速なマクロです。
do_richcompare
が行います。
static PyObject *
do_richcompare(PyObject *v, PyObject *w, int op)
{
richcmpfunc f;
PyObject *res;
int checked_reverse_op = 0;
if (v->ob_type != w->ob_type && ...) { ... }
if ((f = v->ob_type->tp_richcompare) != NULL) {
res = (*f)(v, w, op);
if (res != Py_NotImplemented)
return res;
...
}
...
}
を呼び出すためのいくつかの簡単なチェックを行います。
v->ob_type->tp_richcompare
である
PyTypeObject PyUnicode_Type = {
...
PyUnicode_RichCompare, /* tp_richcompare */
...
};
を行うものです。
PyObject *
PyUnicode_RichCompare(PyObject *left, PyObject *right, int op)
{
int result;
PyObject *v;
if (!PyUnicode_Check(left) || !PyUnicode_Check(right))
Py_RETURN_NOTIMPLEMENTED;
if (PyUnicode_READY(left) == -1 ||
PyUnicode_READY(right) == -1)
return NULL;
if (left == right) {
switch (op) {
case Py_EQ:
case Py_LE:
case Py_GE:
/* a string is equal to itself */
v = Py_True;
break;
case Py_NE:
case Py_LT:
case Py_GT:
v = Py_False;
break;
default:
...
}
}
else if (...) { ... }
else { ...}
Py_INCREF(v);
return v;
}
すなわち、このショートカットは
left == right
を実行した後でなければなりません。
if (!PyUnicode_Check(left) || !PyUnicode_Check(right))
if (PyUnicode_READY(left) == -1 ||
PyUnicode_READY(right) == -1)
すべてのパスは次のようになります (手動で再帰的にインライン化、アンロール、既知のブランチのプルーニングを行います)。
POP() # Stack stuff
TOP() #
#
case PyCmp_IN: # Dispatch on operation
#
sqm != NULL # Dispatch to builtin op
sqm->sq_contains != NULL #
*sqm->sq_contains #
#
cmp == 0 # Do comparison in loop
i < Py_SIZE(a) #
v == w #
op == Py_EQ #
++i #
cmp == 0 #
#
res < 0 # Convert to Python-space
res ? Py_True : Py_False #
Py_INCREF(v) #
#
Py_DECREF(left) # Stack stuff
Py_DECREF(right) #
SET_TOP(res) #
res == NULL #
DISPATCH() #
対
POP() # Stack stuff
TOP() #
#
default: # Dispatch on operation
#
Py_LT <= op # Checking operation
op <= Py_GE #
v == NULL #
w == NULL #
Py_EnterRecursiveCall(...) # Recursive check
#
v->ob_type != w->ob_type # More operation checks
f = v->ob_type->tp_richcompare # Dispatch to builtin op
f != NULL #
#
!PyUnicode_Check(left) # ...More checks
!PyUnicode_Check(right)) #
PyUnicode_READY(left) == -1 #
PyUnicode_READY(right) == -1 #
left == right # Finally, doing comparison
case Py_EQ: # Immediately short circuit
Py_INCREF(v); #
#
res != Py_NotImplemented #
#
Py_LeaveRecursiveCall() # Recursive check
#
Py_DECREF(left) # Stack stuff
Py_DECREF(right) #
SET_TOP(res) #
res == NULL #
DISPATCH() #
今すぐ
PyUnicode_Check
と
PyUnicode_READY
は2つのフィールドをチェックするだけなのでかなり安上がりですが、上の方がより小さなコードパスであることは明らかでしょう、関数呼び出しが少なく、switch
文があり、ほんの少し細くなっています。
TL;DR:
へのディスパッチはどちらも
if (left_pointer == right_pointer)
違いは、そこに到達するまでにどれだけの作業を行うかです。
in
が少ないだけです。
関連
-
Python入門 openを使ったファイルの読み書きの方法
-
[解決済み】Pythonでgoogle APIのJSONコードを読み込むとエラーになる件
-
[解決済み] SQLiteのINSERT/per-secondのパフォーマンスを向上させる
-
[解決済み] B "の印刷が "#"の印刷より劇的に遅いのはなぜですか?
-
[解決済み] Python 3で「1000000000000000 in range(1000000000000001)」はなぜ速いのですか?
-
[解決済み] 要素ごとの加算は、結合ループよりも分離ループの方がはるかに高速なのはなぜですか?
-
[解決済み] なぜC++はPythonよりもstdinからの行の読み込みが遅いのですか?
-
[解決済み] <は<=より速いのか?
-
[解決済み] なぜ[]はlist()よりも速いのですか?
-
[解決済み] Intel CPU の _mm_popcnt_u64 で、32 ビットのループカウンターを 64 ビットに置き換えると、パフォーマンスが著しく低下します。
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
opencvとpillowを用いた顔認証システム(デモあり)
-
Python jiabaライブラリの使用方法について説明
-
Python 可視化 big_screen ライブラリ サンプル 詳細
-
PyQt5はユーザーログインGUIインターフェースとログイン後のジャンプを実装しています。
-
Python LeNetネットワークの説明とpytorchでの実装
-
[解決済み】RuntimeWarning: invalid value encountered in double_scalars で numpy の除算ができない。
-
[解決済み】ImportError: PILという名前のモジュールがない
-
[解決済み】socket.error: [Errno 48] アドレスはすでに使用中です。
-
[解決済み】Python: SyntaxError: キーワードは式になり得ない
-
[解決済み】ValueError: xとyは同じサイズでなければならない