Apakah tuple lebih efisien daripada daftar di Python?

Jawaban:

172

The dismodul disassembles kode byte untuk fungsi dan berguna untuk melihat perbedaan antara tupel dan daftar.

Dalam hal ini, Anda dapat melihat bahwa mengakses elemen menghasilkan kode yang identik, tetapi menetapkan tuple jauh lebih cepat daripada menetapkan daftar.

>>> 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
Mark Harrison
sumber
66
Err, hanya saja bytecode yang sama dihasilkan secara absolut tidak berarti operasi yang sama terjadi pada level C (dan karenanya cpu). Cobalah membuat kelas ListLikedengan __getitem__yang melakukan sesuatu yang sangat lambat, lalu bongkar x = ListLike((1, 2, 3, 4, 5)); y = x[2]. Bytecode akan lebih seperti contoh tuple di atas daripada contoh daftar, tetapi apakah Anda benar-benar percaya itu berarti kinerja akan serupa?
mzz
2
Tampaknya Anda mengatakan bahwa beberapa jenis lebih efisien daripada yang lain. Itu masuk akal, tetapi overhead daftar dan generasi tupel tampaknya ortogonal dengan tipe data yang terlibat, dengan peringatan bahwa mereka adalah daftar dan tupel dari tipe data yang sama.
Mark Harrison
11
Jumlah byte-code, seperti jumlah baris-of-code, tidak memiliki banyak hubungan dengan kecepatan-eksekusi (dan karenanya efisiensi dan kinerja).
martineau
18
Meskipun saran Anda dapat menyimpulkan apa pun dari penghitungan ops adalah sesat, ini menunjukkan perbedaan utama: tupel konstan disimpan seperti itu dalam bytecode dan hanya direferensikan saat digunakan, sedangkan daftar perlu dibangun saat runtime.
poolie
6
Jawaban ini menunjukkan kepada kita bahwa Python mengakui konstanta tuple. Senang mendengarnya! Tetapi apa yang terjadi ketika mencoba membangun tuple atau daftar dari nilai variabel?
Tom
211

Secara umum, Anda mungkin mengharapkan tuple menjadi sedikit lebih cepat. Namun Anda harus menguji kasus spesifik Anda (jika perbedaannya mungkin berdampak pada kinerja program Anda - ingat "optimasi prematur adalah akar dari semua kejahatan").

Python membuatnya sangat mudah: timeit adalah teman Anda.

$ 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

dan...

$ 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

Jadi dalam kasus ini, instantiasi hampir merupakan urutan besarnya lebih cepat untuk tuple, tetapi akses item sebenarnya agak lebih cepat untuk daftar! Jadi, jika Anda membuat beberapa tupel dan mengaksesnya berkali-kali, mungkin sebenarnya lebih cepat menggunakan daftar.

Tentu saja jika Anda ingin mengubah item, daftar pasti akan lebih cepat karena Anda harus membuat tuple baru untuk mengubah satu item (karena tuple tidak dapat diubah).

dF.
sumber
3
Dengan versi python apa pengujian Anda!
Matt Joiner
2
Ada tes lain yang menarik - python -m timeit "x=tuple(xrange(999999))"vs python -m timeit "x=list(xrange(999999))". Seperti yang diduga, butuh waktu lebih lama untuk mematerialisasi tuple daripada daftar.
Hamish Grubijan
3
Tampaknya aneh bahwa akses tuple lebih lambat dari akses daftar. Namun, mencobanya dengan Python 2.7 di PC Windows 7 saya, perbedaannya hanya 10%, jadi tidak penting.
ToolmakerSteve
51
FWIW, akses daftar lebih cepat daripada akses tupel di Python 2 tetapi hanya karena ada kasus khusus untuk daftar di BINARY_SUBSCR dalam Python / ceval.c. Dalam Python 3, optimasi itu hilang, dan akses tuple menjadi sedikit lebih cepat daripada akses daftar.
Raymond Hettinger
3
@yoopoo, tes pertama membuat daftar sejuta kali, tetapi yang kedua membuat daftar sekali dan mengaksesnya jutaan kali. Ini -s "SETUP_CODE"dijalankan sebelum kode waktu aktual.
leewz
203

Ringkasan

Tuples cenderung berkinerja lebih baik daripada daftar di hampir setiap kategori:

1) Tuples dapat dilipat secara konstan .

2) Tuples dapat digunakan kembali alih-alih disalin.

3) Tuple kompak dan tidak mengalokasikan berlebihan.

4) Tuples mereferensikan elemen mereka secara langsung.

Tuples dapat dilipat secara konstan

Tupel konstanta dapat dihitung dengan pengoptimal lubang pengintai Python atau pengoptimal AST. Daftar, di sisi lain, bisa dibangun dari awal:

    >>> 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 

Tuples tidak perlu disalin

Menjalankan tuple(some_tuple)kembali segera dengan sendirinya. Karena tupel tidak dapat diubah, mereka tidak harus disalin:

>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True

Sebaliknya, list(some_list)mengharuskan semua data untuk disalin ke daftar baru:

>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False

Tuples tidak mengalokasikan secara berlebihan

Karena ukuran tuple ditetapkan, ia dapat disimpan lebih kompak daripada daftar yang perlu dialokasikan berlebihan untuk membuat operasi append () lebih efisien.

Ini memberi tuple keuntungan ruang yang bagus:

>>> import sys
>>> sys.getsizeof(tuple(iter(range(10))))
128
>>> sys.getsizeof(list(iter(range(10))))
200

Berikut adalah komentar dari Objects / listobject.c yang menjelaskan apa yang dilakukan daftar:

/* 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.
 */

Tuples merujuk langsung ke elemen mereka

Referensi ke objek digabungkan secara langsung dalam objek tuple. Sebaliknya, daftar memiliki lapisan tipuan ekstra ke array eksternal pointer.

Ini memberi tuple keuntungan kecepatan kecil untuk pencarian yang diindeks dan dibongkar:

$ 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

Ini adalah bagaimana tuple (10, 20)disimpan:

    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;

Berikut cara penyimpanan daftar [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;

Perhatikan bahwa objek tuple menggabungkan dua pointer data secara langsung sementara objek daftar memiliki lapisan tipuan tambahan ke array eksternal yang memegang dua pointer data.

Raymond Hettinger
sumber
19
Akhirnya, seseorang menempatkan struct C!
osman
1
Internally, tuples are stored a little more efficiently than lists, and also tuples can be accessed slightly faster. Bagaimana Anda bisa menjelaskan hasil dari jawaban dF.
DRz
5
Ketika bekerja dengan ~ 50k daftar ~ 100 elemen daftar, memindahkan struktur ini ke tuple kali pencarian menurun dengan beberapa urutan besarnya untuk beberapa pencarian. Saya percaya ini disebabkan oleh lokalitas cache yang lebih besar dari tuple setelah Anda mulai menggunakan tuple karena penghapusan lapisan kedua tipuan yang Anda tunjukkan.
horta
tuple(some_tuple)hanya mengembalikan some_tuplesendiri jika some_tuplehashable — ketika isinya secara kekal berubah dan hashable. Jika tidak, tuple(some_tuple)kembalikan tuple baru. Misalnya, ketika some_tupleberisi item yang bisa diubah.
Luciano Ramalho
Tuple tidak selalu lebih cepat. Pertimbangkan `` `t = () untuk i dalam rentang (1.100): t + = il = [] untuk i dalam kisaran (1.1000): a.append (i)` `` Yang kedua lebih cepat
melvil james
32

Tuples, yang tidak berubah, lebih hemat memori; daftar, untuk efisiensi, memori keseluruhan untuk memungkinkan menambahkan tanpa reallocs konstan . Jadi, jika Anda ingin beralih melalui urutan konstan nilai dalam kode Anda (misalnya for direction in 'up', 'right', 'down', 'left':), tupel lebih disukai, karena tupel seperti itu telah dihitung sebelumnya dalam waktu kompilasi.

Kecepatan akses harus sama (keduanya disimpan sebagai array yang bersebelahan dalam memori).

Tapi, alist.append(item)lebih disukai atuple+= (item,)ketika Anda berurusan dengan data yang bisa berubah. Ingat, tupel dimaksudkan untuk diperlakukan sebagai catatan tanpa nama bidang.

tzot
sumber
1
apa waktu kompilasi dengan python?
balki
1
@balki: waktu ketika sumber python dikompilasi ke bytecode (bytecode yang mungkin disimpan sebagai file .py [co]).
tzot
Kutipan akan sangat bagus jika memungkinkan.
Grijesh Chauhan
9

Anda juga harus mempertimbangkan arraymodul di perpustakaan standar jika semua item dalam daftar atau tupel Anda memiliki tipe C yang sama. Ini akan memakan sedikit memori dan bisa lebih cepat.

Eponim
sumber
15
Ini akan memakan lebih sedikit memori, tetapi waktu akses mungkin akan sedikit lebih lambat, daripada lebih cepat. Mengakses elemen membutuhkan nilai yang dikemas untuk dibuka kotaknya ke integer nyata, yang akan memperlambat proses.
Brian
5

Berikut ini adalah patokan kecil lain, hanya demi itu ..

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)

Mari kita rata-rata ini:

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

Anda dapat menyebutnya hampir tidak meyakinkan.

Tetapi tentu saja, tuple mengambil 101.239%waktu, atau 1.239%waktu ekstra untuk melakukan pekerjaan dibandingkan dengan daftar.

Dev Aggarwal
sumber
4

Tuple harus sedikit lebih efisien dan karena itu, lebih cepat, daripada daftar karena mereka tidak berubah.

ctcherry
sumber
4
Mengapa Anda mengatakan bahwa keabadian, dalam dan dari dirinya sendiri, meningkatkan efisiensi? Terutama efisiensi instantiation dan pengambilan?
Blair Conrad
1
Sepertinya balasan Markus di atas milikku telah membahas instruksi yang dibongkar tentang apa yang terjadi di dalam Python. Anda dapat melihat bahwa Instansiasi mengambil instruksi lebih sedikit, namun dalam kasus ini, pengambilan tampaknya identik.
ctcherry
tuple abadi memiliki akses yang lebih cepat daripada daftar yang bisa berubah
noobninja
-6

Alasan utama Tuple menjadi sangat efisien dalam membaca adalah karena itu tidak berubah.

Mengapa objek yang tidak dapat diubah mudah dibaca?

Alasannya tuple dapat disimpan dalam cache memori, tidak seperti daftar. Program selalu membaca dari daftar lokasi memori karena dapat berubah (dapat berubah sewaktu-waktu).

Divakar
sumber