it-swarm-vi.com

Các bộ dữ liệu có hiệu quả hơn các danh sách trong Python không?

Có sự khác biệt về hiệu năng giữa các bộ dữ liệu và danh sách khi nói đến việc khởi tạo và truy xuất các phần tử không?

191
Readonly

Mô-đun dis phân tách mã byte cho một hàm và rất hữu ích để xem sự khác biệt giữa các bộ dữ liệu và danh sách.

Trong trường hợp này, bạn có thể thấy rằng việc truy cập một phần tử sẽ tạo mã giống hệt nhau, nhưng việc gán Tuple nhanh hơn nhiều so với việc gán danh sách.

>>> 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
152
Mark Harrison

Nói chung, bạn có thể mong đợi các bộ dữ liệu sẽ nhanh hơn một chút. Tuy nhiên, bạn chắc chắn nên kiểm tra trường hợp cụ thể của mình (nếu sự khác biệt có thể ảnh hưởng đến hiệu suất của chương trình của bạn - hãy nhớ "tối ưu hóa sớm là gốc rễ của mọi tội lỗi").

Python làm điều này rất dễ dàng: timeit là bạn của bạn.

$ 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

và ...

$ 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

Vì vậy, trong trường hợp này, việc khởi tạo gần như là một thứ tự cường độ nhanh hơn cho Tuple, nhưng việc truy cập vật phẩm thực sự có phần nhanh hơn cho danh sách! Vì vậy, nếu bạn đang tạo một vài bộ dữ liệu và truy cập chúng nhiều lần, thì thực tế có thể sử dụng danh sách nhanh hơn.

Tất nhiên, nếu bạn muốn thay đổi một mục, danh sách chắc chắn sẽ nhanh hơn vì bạn cần tạo toàn bộ Tuple mới để thay đổi một mục của nó (vì tuples là bất biến).

194
dF.

Tóm lược

Các bộ dữ liệu có xu hướng hoạt động tốt hơn danh sách trong hầu hết mọi danh mục:

1) Tuples có thể không đổi gấp .

2) Tuples có thể được sử dụng lại thay vì sao chép.

3) Tuples nhỏ gọn và không phân bổ quá mức.

4) Tuples trực tiếp tham chiếu các yếu tố của họ.

Tuples có thể được gấp lại liên tục

Các bộ hằng số có thể được tính toán trước bằng trình tối ưu hóa lổ nhìn trộm của Python hoặc trình tối ưu hóa AST. Danh sách, mặt khác, được xây dựng từ đầu:

    >>> 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 không cần phải sao chép

Đang chạy Tuple(some_Tuple) trả về ngay lập tức. Vì các bộ dữ liệu là bất biến, nên chúng không phải sao chép:

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

Ngược lại, list(some_list) yêu cầu tất cả dữ liệu được sao chép vào một danh sách mới:

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

Tuples không phân bổ quá mức

Vì kích thước của Tuple là cố định, nên nó có thể được lưu trữ gọn hơn so với các danh sách cần phân bổ quá mức để thực hiện append () hoạt động hiệu quả.

Điều này mang lại cho tuples một lợi thế không gian đẹp:

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

Dưới đây là nhận xét từ Đối tượng/listobject.c giải thích những gì danh sách đang làm:

/* 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 đề cập trực tiếp đến các yếu tố của họ

Tham chiếu đến các đối tượng được kết hợp trực tiếp trong một đối tượng Tuple. Ngược lại, các danh sách có thêm một lớp gián tiếp với một mảng con trỏ bên ngoài.

Điều này mang lại cho bộ dữ liệu một lợi thế tốc độ nhỏ để tra cứu được lập chỉ mục và giải nén:

$ 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

Ở đây là cách Tuple (10, 20) được lưu trữ:

    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;

Ở đây là cách danh sách [10, 20] được lưu trữ:

    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;

Lưu ý rằng đối tượng Tuple kết hợp trực tiếp hai con trỏ dữ liệu trong khi đối tượng danh sách có thêm một lớp cảm ứng cho một mảng bên ngoài giữ hai con trỏ dữ liệu.

166
Raymond Hettinger

Tuples, là bất biến, là bộ nhớ hiệu quả hơn; liệt kê, để hiệu quả, tổng thể bộ nhớ để cho phép nối thêm mà không cần reallocs. Vì vậy, nếu bạn muốn lặp qua một chuỗi các giá trị không đổi trong mã của mình (ví dụ for direction in 'up', 'right', 'down', 'left':), các bộ dữ liệu được ưu tiên, vì các bộ dữ liệu đó được tính toán trước trong thời gian biên dịch.

Tốc độ truy cập phải giống nhau (cả hai đều được lưu trữ dưới dạng các mảng liền kề trong bộ nhớ).

Nhưng, alist.append(item) được ưu tiên hơn nhiều so với atuple+= (item,) khi bạn xử lý dữ liệu có thể thay đổi. Hãy nhớ rằng, bộ dữ liệu được dự định sẽ được coi là bản ghi mà không có tên trường.

31
tzot

Bạn cũng nên xem xét mô-đun array trong thư viện chuẩn nếu tất cả các mục trong danh sách hoặc Tuple của bạn có cùng loại C. Nó sẽ mất ít bộ nhớ hơn và có thể nhanh hơn.

9
Ralph Corderoy

Tuples nên hiệu quả hơn một chút và vì điều đó, nhanh hơn so với danh sách vì chúng là bất biến.

4
ctcherry

Đây là một tiêu chuẩn nhỏ khác, chỉ vì lợi ích của nó ..

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)

Hãy trung bình những điều này:

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

Bạn có thể gọi nó gần như không kết luận.

Nhưng chắc chắn, các bộ dữ liệu đã mất 101.239% thời gian hoặc 1.239% thêm thời gian để thực hiện công việc so với danh sách.

3
Dev Aggarwal