Являются ли кортежи более эффективными, чем списки в Python?

225

Есть ли разница в производительности между кортежами и списками, когда дело доходит до создания и извлечения элементов?

Readonly
источник
9
Связанный: "Почему кортеж быстрее, чем список?"
Кристиан Чиупиту
2
Если вас интересует использование памяти между типами данных, посмотрите этот график, который я сделал: stackoverflow.com/a/30008338/2087463
tmthydvnprt

Ответы:

172

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
Марк Харрисон
источник
66
Да, просто то, что генерируется один и тот же байт-код, абсолютно не означает, что одни и те же операции происходят на уровне C (и, следовательно, cpu). Попробуйте создать класс ListLikeс классом, __getitem__который делает что-то ужасно медленное, затем разберите x = ListLike((1, 2, 3, 4, 5)); y = x[2]. Байт-код будет больше похож на приведенный выше пример кортежа, чем на пример списка, но действительно ли вы считаете, что производительность будет аналогичной?
MZZ
2
Кажется, вы говорите, что некоторые типы более эффективны, чем другие. Это имеет смысл, но издержки генерации списков и кортежей, по-видимому, ортогональны задействованному типу данных с оговоркой, что они являются списками и кортежами одного и того же типа данных.
Марк Харрисон
11
Количество байт-кодов, например, количество строк кода, имеет мало отношения к скорости выполнения (и, следовательно, эффективности и производительности).
Мартино
18
Хотя предложение о том, что вы можете сделать вывод о подсчете операций, ошибочно, это показывает ключевое отличие: постоянные кортежи сохраняются как таковые в байт-коде и просто используются при использовании, тогда как списки необходимо создавать во время выполнения.
пул
6
Этот ответ показывает нам, что Python признает константы кортежей. Это хорошо знать! Но что происходит при попытке создать кортеж или список из значений переменных?
Том
211

В целом, вы можете ожидать, что кортежи будут немного быстрее. Однако вы должны обязательно протестировать ваш конкретный случай (если разница может повлиять на производительность вашей программы - помните: «преждевременная оптимизация - корень всего зла»).

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

Так что в этом случае создание экземпляра почти на порядок быстрее для кортежа, но доступ к элементу на самом деле несколько быстрее для списка! Поэтому, если вы создаете несколько кортежей и обращаетесь к ним много-много раз, на самом деле может быть быстрее использовать списки.

Конечно, если вы хотите изменить элемент, список определенно будет быстрее, так как вам нужно будет создать целый новый кортеж, чтобы изменить один его элемент (так как кортежи неизменны).

дР.
источник
3
С какой версией python были ваши тесты!
Мэтт Джойнер
2
Есть еще один интересный тест - python -m timeit "x=tuple(xrange(999999))"против python -m timeit "x=list(xrange(999999))". Как и следовало ожидать, для создания кортежа требуется немного больше времени, чем для списка.
Хэмиш Грубиджан
3
Кажется странным, что доступ к кортежу медленнее, чем доступ к списку. Однако, пытаясь это сделать в Python 2.7 на моем ПК с Windows 7, разница составляет всего 10%, поэтому неважно.
ToolmakerSteve
51
FWIW, доступ к спискам быстрее, чем доступ к кортежам в Python 2, но только потому, что существует особый случай для списков в BINARY_SUBSCR в Python / ceval.c. В Python 3 эта оптимизация исчезла, и доступ к кортежам становится немного быстрее, чем доступ к списку.
Рэймонд Хеттингер
3
@yoopoo, первый тест создает список миллион раз, а второй создает список один раз и обращается к нему миллион раз. -s "SETUP_CODE"Выполняются до фактического таймерного кода.
Leewz
203

Резюме

Кортежи имеют тенденцию работать лучше, чем списки почти в каждой категории:

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

Кортежи не перераспределяют

Поскольку размер кортежа фиксирован, он может храниться более компактно, чем списки, которые необходимо перераспределить, чтобы сделать операции append () эффективными.

Это дает кортежам хорошее космическое преимущество:

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

Вот комментарий от Objects / 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;

Обратите внимание, что объект кортежа включает два указателя данных напрямую, в то время как объект списка имеет дополнительный уровень косвенности к внешнему массиву, содержащему два указателя данных.

Раймонд Хеттингер
источник
19
Наконец, кто-то ставит C-структуры!
Осман
1
Internally, tuples are stored a little more efficiently than lists, and also tuples can be accessed slightly faster. Как вы можете объяснить результаты ответа Д.Ф.?
DRz
5
При работе со списками ~ 50 тыс. Из ~ 100 списков элементов перемещение этой структуры в кортежи сократило время поиска на несколько порядков для нескольких поисков. Я полагаю, что это связано с большей локальностью кэша кортежа после того, как вы начнете использовать кортеж из-за удаления второго уровня косвенности, который вы демонстрируете.
Орта
tuple(some_tuple)возвращает some_tupleсебя, только если some_tupleявляется хэшируемым - когда его содержимое является рекурсивно неизменным и хэшируемым. В противном случае tuple(some_tuple)возвращает новый кортеж. Например, когда some_tupleсодержит изменяемые элементы.
Лучано Рамальо
Кортежи не всегда быстрее. Рассмотрим `` `t = () для i в диапазоне (1100): t + = il = [] для i в диапазоне (11000): a.append (i)` `` Второй быстрее
Мельвиль Джеймс
32

Кортежи, будучи неизменными, более эффективны для памяти; списки, для эффективности, перераспределяют память, чтобы разрешить добавления без константы reallocs. Итак, если вы хотите перебирать постоянную последовательность значений в вашем коде (например for direction in 'up', 'right', 'down', 'left':), кортежи предпочтительнее, так как такие кортежи предварительно рассчитываются во время компиляции.

Скорости доступа должны быть одинаковыми (они оба хранятся в памяти в виде смежных массивов).

Но alist.append(item)гораздо предпочтительнее, atuple+= (item,)когда вы имеете дело с изменчивыми данными. Помните, что кортежи должны рассматриваться как записи без имен полей.

tzot
источник
1
что такое время компиляции в python?
Балки
1
@balki: время, когда исходный код Python компилируется в байт-код (этот байт-код может быть сохранен в виде файла .py [co]).
tzot
Цитата будет здорово, если это возможно.
Грижеш Чаухан
9

Вы также должны рассмотреть arrayмодуль в стандартной библиотеке, если все элементы в вашем списке или кортеже относятся к одному и тому же типу C. Это займет меньше памяти и может быть быстрее.

Одноименный
источник
15
Это займет меньше памяти, но время доступа, вероятно, будет немного медленнее, чем быстрее. Доступ к элементу требует, чтобы упакованное значение было распаковано в реальное целое число, что замедлит процесс.
Брайан
5

Вот еще один маленький ориентир, просто ради этого ..

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%дополнительное время, чтобы выполнить работу по сравнению со списками.

Дев Аггарвал
источник
4

Кортежи должны быть немного более эффективными и поэтому быстрее, чем списки, потому что они неизменяемы.

ctcherry
источник
4
Почему вы говорите, что неизменность сама по себе повышает эффективность? Особенно эффективность создания и поиска?
Блэр Конрад
1
Кажется, что ответ Марка над моим охватил разобранные инструкции о том, что происходит внутри Python. Вы можете видеть, что создание экземпляров требует меньше инструкций, однако в этом случае поиск, по-видимому, идентичен.
ctcherry
неизменяемые кортежи имеют более быстрый доступ, чем изменяемые списки
noobninja
-6

Основная причина высокой эффективности чтения Tuple заключается в том, что он неизменен.

Почему неизменяемые объекты легко читать?

Причина в том, что кортежи могут храниться в кеш-памяти, в отличие от списков. Программа всегда считывает из памяти ячейки списков, так как она изменчива (может измениться в любое время).

Divakar
источник