私はその情報源を見ていたソートされたコンテナそして驚いたのはこの行:
self._load, self._twice, self._half = load, load * 2, load >> 1
ここにload整数があります。なぜ、ある場所ではビット シフトを使用し、別の場所では乗算を使用するのでしょうか。ビット シフトは 2 による整数除算よりも高速であると考えられますが、乗算もシフトに置き換えてみてはどうでしょうか。次のケースをベンチマークしました。
- (掛ける、割る)
- （シフト、シフト）
- （時間、シフト）
- (シフト、除算)
そして、#3 は他の選択肢よりも一貫して高速であることがわかりました。
# self._load, self._twice, self._half = load, load * 2, load >> 1
import random
import timeit
import pandas as pd
x = random.randint(10 ** 3, 10 ** 6)
def test_naive():
a, b, c = x, 2 * x, x // 2
def test_shift():
a, b, c = x, x << 1, x >> 1
def test_mixed():
a, b, c = x, x * 2, x >> 1
def test_mixed_swapped():
a, b, c = x, x << 1, x // 2
def observe(k):
print(k)
return {
'naive': timeit.timeit(test_naive),
'shift': timeit.timeit(test_shift),
'mixed': timeit.timeit(test_mixed),
'mixed_swapped': timeit.timeit(test_mixed_swapped),
}
def get_observations():
return pd.DataFrame([observe(k) for k in range(100)])
質問：
私のテストは有効ですか? 有効である場合、(乗算、シフト) が (シフト、シフト) よりも高速なのはなぜですか?
Ubuntu 14.04 で Python 3.5 を実行しています。
編集
上記は質問の元の記述です。Dan Getz 氏は回答の中で優れた説明をしています。
完全性を期すために、x乗算の最適化が適用されない場合のより大きなサンプル図を以下に示します。
ベストアンサー1
これは、CPython 3.5 では小さな数の乗算が最適化されているのに対し、小さな数の左シフトは最適化されていないためと思われます。正の左シフトでは、計算の一部として結果を格納するための大きな整数オブジェクトが常に作成されますが、テストで使用した種類の乗算では、特別な最適化によってこれが回避され、正しいサイズの整数オブジェクトが作成されます。これは次のコードで確認できます。Pythonの整数実装のソースコード。
Python の整数は任意の精度であるため、整数の「桁」の配列として保存され、整数の桁あたりのビット数に制限があります。したがって、一般的なケースでは、整数に関する操作は単一の操作ではなく、複数の「桁」の場合を処理する必要があります。pyport.hこのビット制限と定義されている64 ビット プラットフォームでは 30 ビット、それ以外の場合は 15 ビットです。(説明を簡単にするために、ここからは 30 と呼びます。ただし、32 ビット用にコンパイルされた Python を使用している場合、ベンチマークの結果はx32,768 未満かどうかによって変わることに注意してください。)
操作の入力と出力がこの30ビットの制限内に収まる場合、操作は一般的な方法ではなく最適化された方法で処理できます。整数乗算の実装以下のとおりであります：
static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
CHECK_BINOP(a, b);
/* fast path for single-digit multiplication */
if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
/* if we don't have long long then we're almost certainly
using 15-bit digits, so v will fit in a long. In the
unlikely event that we're using 30-bit digits on a platform
without long long, a large v will just cause us to fall
through to the general multiplication code below. */
if (v >= LONG_MIN && v <= LONG_MAX)
return PyLong_FromLong((long)v);
#endif
}
したがって、それぞれが 30 ビットの数字に収まる 2 つの整数を乗算する場合、これは整数を配列として処理するのではなく、CPython インタープリターによって直接乗算として実行されます。MEDIUM_VALUE()正の整数オブジェクトに対して呼び出されると、単純に最初の30ビットの数字が取得されます。結果が単一の30ビットの数字に収まる場合は、PyLong_FromLongLong()比較的少数の操作でこれに気づき、それを保存するための 1 桁の整数オブジェクトを作成します。
対照的に、左シフトはこのように最適化されておらず、すべての左シフトはシフトされる整数を配列として扱います。特に、long_lshift()小さいながらも正の左シフトの場合、長さが後で 1 に切り捨てられるためだけに、常に 2 桁の整数オブジェクトが作成されます。（私のコメントは/*** ***/）
static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
/*** ... ***/
wordshift = shiftby / PyLong_SHIFT; /*** zero for small w ***/
remshift = shiftby - wordshift * PyLong_SHIFT; /*** w for small w ***/
oldsize = Py_ABS(Py_SIZE(a)); /*** 1 for small v > 0 ***/
newsize = oldsize + wordshift;
if (remshift)
++newsize; /*** here newsize becomes at least 2 for w > 0, v > 0 ***/
z = _PyLong_New(newsize);
/*** ... ***/
}
整数除算
整数の切り捨て除算が右シフトに比べてパフォーマンスが悪いという質問はなかった。それはあなたの（そして私の）期待に合致したからだ。しかし、小さな正の数を別の小さな正の数で割るのは、小さな乗算ほど最適化されていない。すべてのもの//は商とそして関数を使用して残りを計算するlong_divrem()この剰余は、掛け算、 そして新しく割り当てられた整数オブジェクトに格納される、この状況ではすぐに破棄されます。
少なくとも、この質問が最初に出されたときはそうでした。CPython 3.6では、ファストパス小さい整数用のが//追加されたため、小さい整数用の//beats も追加されました。>>