Python ではタプルはリストよりも効率的ですか?
https://stackoverflow.com/questions/68630
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
要素のインスタンス化と取得に関して、タプルとリストの間にパフォーマンスの違いはありますか?
解決
の dis モジュールは関数のバイト コードを逆アセンブルし、タプルとリストの違いを確認するのに役立ちます。
この場合、要素にアクセスすると同じコードが生成されますが、タプルを割り当てる方がリストを割り当てるよりもはるかに高速であることがわかります。
>>> def a():
... x=[1,2,3,4,5]
... y=x[2]
...
>>> def b():
... x=(1,2,3,4,5)
... y=x[2]
...
>>> import dis
>>> dis.dis(a)
2 0 LOAD_CONST 1 (1)
3 LOAD_CONST 2 (2)
6 LOAD_CONST 3 (3)
9 LOAD_CONST 4 (4)
12 LOAD_CONST 5 (5)
15 BUILD_LIST 5
18 STORE_FAST 0 (x)
3 21 LOAD_FAST 0 (x)
24 LOAD_CONST 2 (2)
27 BINARY_SUBSCR
28 STORE_FAST 1 (y)
31 LOAD_CONST 0 (None)
34 RETURN_VALUE
>>> dis.dis(b)
2 0 LOAD_CONST 6 ((1, 2, 3, 4, 5))
3 STORE_FAST 0 (x)
3 6 LOAD_FAST 0 (x)
9 LOAD_CONST 2 (2)
12 BINARY_SUBSCR
13 STORE_FAST 1 (y)
16 LOAD_CONST 0 (None)
19 RETURN_VALUE
他のヒント
一般に、タプルの方が若干速いと予想されるかもしれません。ただし、必ず特定のケースをテストする必要があります (違いがプログラムのパフォーマンスに影響を与える可能性がある場合は、「時期尚早の最適化が諸悪の根源」であることを忘れないでください)。
Python を使用すると、これが非常に簡単になります。 時間 あなたの友だちです。
$ python -m timeit "x=(1,2,3,4,5,6,7,8)"
10000000 loops, best of 3: 0.0388 usec per loop
$ python -m timeit "x=[1,2,3,4,5,6,7,8]"
1000000 loops, best of 3: 0.363 usec per loop
そして...
$ python -m timeit -s "x=(1,2,3,4,5,6,7,8)" "y=x[3]"
10000000 loops, best of 3: 0.0938 usec per loop
$ python -m timeit -s "x=[1,2,3,4,5,6,7,8]" "y=x[3]"
10000000 loops, best of 3: 0.0649 usec per loop
したがって、この場合、タプルのインスタンス化はほぼ 1 桁高速ですが、項目へのアクセスは実際にはリストの方が若干高速です。したがって、いくつかのタプルを作成し、それらに何度もアクセスする場合は、実際には代わりにリストを使用した方が速い可能性があります。
もちろんそうしたいなら 変化 項目の場合、その項目の 1 つを変更するには新しいタプル全体を作成する必要があるため、リストは間違いなく高速になります (タプルは不変であるため)。
まとめ
タプルはリストよりもパフォーマンスが優れている傾向があります ほぼすべてのカテゴリーで:
1) タプルは次のとおりです。 折り畳まれた定数.
2) タプルはコピーする代わりに再利用できます。
3) タプルはコンパクトであり、過剰割り当てはありません。
4) タプルはその要素を直接参照します。
タプルは定数折り畳むことができる
定数のタプルは、Python のピープホール オプティマイザーまたは AST オプティマイザーによって事前計算できます。一方、リストはゼロから構築されます。
>>> from dis import dis
>>> dis(compile("(10, 'abc')", '', 'eval'))
1 0 LOAD_CONST 2 ((10, 'abc'))
3 RETURN_VALUE
>>> dis(compile("[10, 'abc']", '', 'eval'))
1 0 LOAD_CONST 0 (10)
3 LOAD_CONST 1 ('abc')
6 BUILD_LIST 2
9 RETURN_VALUE
タプルをコピーする必要はありません
ランニング tuple(some_tuple) すぐにそれ自体が戻ります。タプルは不変であるため、コピーする必要はありません。
>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True
対照的に、 list(some_list) すべてのデータを新しいリストにコピーする必要があります。
>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False
タプルは過剰割り当てを行わない
タプルのサイズは固定されているため、作成するために過剰な割り当てが必要なリストよりもコンパクトに格納できます。 追加() 効率的な運用。
これにより、タプルに優れたスペース上の利点がもたらされます。
>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200
からのコメントはこちら オブジェクト/listobject.c これはリストが何をしているのかを説明しています:
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
* Note: new_allocated won't overflow because the largest possible value
* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
*/
タプルはその要素を直接参照します
オブジェクトへの参照は、タプル オブジェクトに直接組み込まれます。対照的に、リストには、ポインターの外部配列への間接層が追加されています。
これにより、タプルのインデックス付き検索とアンパックの速度が若干向上します。
$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'a[1]'
10000000 loops, best of 3: 0.0304 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'a[1]'
10000000 loops, best of 3: 0.0309 usec per loop
$ python3.6 -m timeit -s 'a = (10, 20, 30)' 'x, y, z = a'
10000000 loops, best of 3: 0.0249 usec per loop
$ python3.6 -m timeit -s 'a = [10, 20, 30]' 'x, y, z = a'
10000000 loops, best of 3: 0.0251 usec per loop
ここ タプルはどうですか (10, 20) 保存されています：
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
PyObject *ob_item[2]; /* store a pointer to 10 and a pointer to 20 */
} PyTupleObject;
ここ リストはどうですか [10, 20] 保存されています：
PyObject arr[2]; /* store a pointer to 10 and a pointer to 20 */
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
PyObject **ob_item = arr; /* store a pointer to the two-pointer array */
Py_ssize_t allocated;
} PyListObject;
タプル オブジェクトには 2 つのデータ ポインターが直接組み込まれていますが、リスト オブジェクトには 2 つのデータ ポインターを保持する外部配列への間接層が追加されていることに注意してください。
タプルは不変であるため、メモリ効率が高くなります。リストでは、効率を高めるために、定数なしで追加できるようにメモリを過剰に割り当てます。 reallocs.したがって、コード内で一定の値のシーケンスを反復処理する場合 (例: for direction in 'up', 'right', 'down', 'left':)、タプルはコンパイル時に事前に計算されるため、タプルが推奨されます。
アクセス速度は同じである必要があります (両方ともメモリ内に連続した配列として格納されます)。
しかし、 alist.append(item) より好まれる atuple+= (item,) 可変データを扱う場合。タプルはフィールド名のないレコードとして扱われることを目的としていることに注意してください。
次のことも考慮する必要があります。 array リストまたはタプル内のすべての項目が同じ C 型である場合は、標準ライブラリのモジュール。必要なメモリが少なくなり、速度が向上します。
タプルは不変であるため、リストよりも若干効率が良く、そのため高速になります。
参考までに、もう 1 つの小さなベンチマークを示します。
In [11]: %timeit list(range(100))
749 ns ± 2.41 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [12]: %timeit tuple(range(100))
781 ns ± 3.34 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [1]: %timeit list(range(1_000))
13.5 µs ± 466 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [2]: %timeit tuple(range(1_000))
12.4 µs ± 182 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [7]: %timeit list(range(10_000))
182 µs ± 810 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [8]: %timeit tuple(range(10_000))
188 µs ± 2.38 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [3]: %timeit list(range(1_00_000))
2.76 ms ± 30.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [4]: %timeit tuple(range(1_00_000))
2.74 ms ± 31.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [10]: %timeit list(range(10_00_000))
28.1 ms ± 266 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [9]: %timeit tuple(range(10_00_000))
28.5 ms ± 447 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
これらを平均してみましょう:
In [3]: l = np.array([749 * 10 ** -9, 13.5 * 10 ** -6, 182 * 10 ** -6, 2.76 * 10 ** -3, 28.1 * 10 ** -3])
In [2]: t = np.array([781 * 10 ** -9, 12.4 * 10 ** -6, 188 * 10 ** -6, 2.74 * 10 ** -3, 28.5 * 10 ** -3])
In [11]: np.average(l)
Out[11]: 0.0062112498000000006
In [12]: np.average(t)
Out[12]: 0.0062882362
In [17]: np.average(t) / np.average(l) * 100
Out[17]: 101.23946713590554
ほぼ決定的ではないと言ってもいいでしょう。
しかし確かに、タプルはかかりました 101.239% 時間、または 1.239% リストに比べて、仕事をするのに余分な時間がかかります。
タプルの読み取り効率が非常に高い主な理由は、タプルが不変であるためです。
なぜ不変オブジェクトは読みやすいのでしょうか?
その理由は、リストとは異なり、タプルはメモリ キャッシュに保存できるためです。プログラムは可変である (いつでも変更できる) ため、常にリストのメモリ位置から読み取ります。
