[解決済み] Pythonの配列はなぜ遅いのか？

質問

期待した array.array はリストよりも高速です。配列は箱詰めされていないように見えるからです。

しかし、以下のような結果になってしまいます。

In [1]: import array

In [2]: L = list(range(100000000))

In [3]: A = array.array('l', range(100000000))

In [4]: %timeit sum(L)
1 loop, best of 3: 667 ms per loop

In [5]: %timeit sum(A)
1 loop, best of 3: 1.41 s per loop

In [6]: %timeit sum(L)
1 loop, best of 3: 627 ms per loop

In [7]: %timeit sum(A)
1 loop, best of 3: 1.39 s per loop

このような差の原因は何でしょうか？

解決方法は？

その ストレージ はquot;unboxed"ですが、Pythonは要素にアクセスするたびに、それを使って何かをするためにquot;box"（通常のPythonオブジェクトにそれを埋め込む）する必要があります。 例えば、あなたの sum(A) は配列を繰り返し、整数を1つずつ通常のPythonの int オブジェクトを作成します。 その分時間がかかります。 あなたの sum(L) すべてのボックス化は、リストが作成されたときに行われました。

つまり、一般的には配列の方が遅いのですが、必要なメモリはかなり少なくて済みます。

これは最近のPython 3のコードですが、Pythonが最初にリリースされたときからのすべてのCPythonの実装に同じ基本的な考え方が適用されます。

以下は、リストアイテムにアクセスするコードです。

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    /* error checking omitted */
    return ((PyListObject *)op) -> ob_item[i];
}

ほとんどないんですよ。 somelist[i] を返すだけです。 i のレイアウトに準拠した初期セグメントを持つ構造体へのポインタです。 struct PyObject ).

そして、ここで __getitem__ の実装は array タイプコード付き l :

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

生メモリは、プラットフォームネイティブのベクトルとして扱われます。 C long の整数値です。 i 'th C long が読み上げられ、次に PyLong_FromLong() が呼び出され、ネイティブの C long をPythonの long オブジェクトを作成します (Python 3 では、Python 2 の int と long は、実際には型として表示されます。 int ).

このボクシングは、Pythonの新しいメモリを割り当てる必要があります。 int オブジェクトを生成し、ネイティブの C long のビットを注入します。 元の例の文脈では、このオブジェクトの寿命は非常に短いものです (ちょうど sum() を実行中の合計に追加するために、さらに時間が必要です。 int オブジェクトを作成します。

CPythonの実装では、スピードの違いはここから来ていますし、これまでも、そしてこれからも来るでしょう。