As tuplas são mais eficientes que as listas em Python?

Respostas:

172

O dismódulo desmonta o código de bytes para uma função e é útil para ver a diferença entre tuplas e listas.

Nesse caso, você pode ver que acessar um elemento gera código idêntico, mas que atribuir uma tupla é muito mais rápido do que atribuir uma lista.

>>> 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
fonte
66
Err, apenas o fato de o mesmo bytecode ser gerado absolutamente não significa que as mesmas operações ocorram no nível C (e, portanto, na CPU). Tente criar uma classe ListLikecom uma __getitem__que faça algo terrivelmente lento e depois desmonte x = ListLike((1, 2, 3, 4, 5)); y = x[2]. O bytecode será mais parecido com o exemplo da tupla acima do que o exemplo da lista, mas você realmente acredita que isso significa que o desempenho será semelhante?
mzz
2
Parece que você está dizendo que alguns tipos são mais eficientes que outros. Isso faz sentido, mas a sobrecarga das gerações de lista e tupla parece ser ortogonal ao tipo de dados envolvido, com a ressalva de que são listas e tuplas do mesmo tipo de dados.
Mark-Harrison #
11
O número de códigos de bytes, como o número de linhas de código, tem pouca relação com a velocidade de execução (e, portanto, com eficiência e desempenho).
martineau
18
Embora a sugestão de que você possa concluir qualquer coisa da contagem de operações seja equivocada, isso mostra a principal diferença: tuplas constantes são armazenadas como tal no bytecode e apenas referenciadas quando usadas, enquanto as listas precisam ser criadas em tempo de execução.
Pool #
6
Essa resposta nos mostra que o Python reconhece constantes de tupla. Isso é bom de saber! Mas o que acontece ao tentar criar uma tupla ou uma lista a partir de valores variáveis?
Tom
211

Em geral, você pode esperar que as tuplas sejam um pouco mais rápidas. No entanto, você definitivamente deve testar seu caso específico (se a diferença puder afetar o desempenho do seu programa - lembre-se de que "a otimização prematura é a raiz de todo mal").

O Python facilita isso: o timeit é seu amigo.

$ 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

e...

$ 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

Portanto, nesse caso, a instanciação é quase uma ordem de magnitude mais rápida para a tupla, mas o acesso ao item é realmente um pouco mais rápido para a lista! Portanto, se você estiver criando algumas tuplas e acessando-as muitas vezes, pode ser mais rápido usar as listas.

Obviamente, se você quiser alterar um item, a lista será definitivamente mais rápida, pois você precisará criar uma nova tupla inteira para alterar um item (já que as tuplas são imutáveis).

dF.
fonte
3
Com qual versão do python foram seus testes!
Matt Joiner
2
Há um outro teste interessante - python -m timeit "x=tuple(xrange(999999))"vs python -m timeit "x=list(xrange(999999))". Como seria de esperar, leva um pouco mais de tempo para materializar uma tupla do que uma lista.
Hamish Grubijan
3
Parece estranho que o acesso à tupla seja mais lento que o acesso à lista. No entanto, tentando isso no Python 2.7 no meu PC com Windows 7, a diferença é de apenas 10%, o que não é importante.
Home
51
FWIW, o acesso à lista é mais rápido que o acesso à tupla no Python 2, mas apenas porque existe um caso especial para listas no BINARY_SUBSCR no Python / ceval.c. No Python 3, essa otimização desapareceu e o acesso às tuplas se torna um pouco mais rápido que o acesso à lista.
Raymond Hettinger
3
@yoopoo, o primeiro teste cria uma lista um milhão de vezes, mas o segundo cria uma lista uma vez e a acessa um milhão de vezes. O -s "SETUP_CODE"é executado antes do código cronometrado real.
leewz
203

Resumo

As tuplas tendem a ter um desempenho melhor do que as listas em quase todas as categorias:

1) As tuplas podem ser dobradas constantemente .

2) As tuplas podem ser reutilizadas em vez de copiadas.

3) As tuplas são compactas e não superalocam.

4) Tuplas referenciam diretamente seus elementos.

As tuplas podem ser dobradas constantemente

Tuplas de constantes podem ser pré-computadas pelo otimizador de olho mágico do Python ou pelo otimizador AST. As listas, por outro lado, são criadas do zero:

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

Tuplas não precisam ser copiadas

A execução tuple(some_tuple)retorna imediatamente a si mesma. Como as tuplas são imutáveis, elas não precisam ser copiadas:

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

Por outro lado, list(some_list)exige que todos os dados sejam copiados para uma nova lista:

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

Tuplas não superalocam

Como o tamanho de uma tupla é fixo, ele pode ser armazenado de forma mais compacta do que as listas que precisam ser superalocadas para tornar eficientes as operações append () .

Isso dá às tuplas uma boa vantagem de espaço:

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

Aqui está o comentário de Objects / listobject.c que explica o que as listas estão fazendo:

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

Tuplas se referem diretamente a seus elementos

Referências a objetos são incorporadas diretamente em um objeto de tupla. Por outro lado, as listas têm uma camada extra de indireção para uma matriz externa de ponteiros.

Isso fornece às tuplas uma pequena vantagem de velocidade para pesquisas indexadas e descompactação:

$ 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

Aqui está como a tupla (10, 20)é armazenada:

    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;

Aqui está como a lista [10, 20]é armazenada:

    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;

Observe que o objeto tupla incorpora os dois ponteiros de dados diretamente, enquanto o objeto de lista possui uma camada adicional de indireção a uma matriz externa que contém os dois ponteiros de dados.

Raymond Hettinger
fonte
19
Finalmente, alguém coloca as estruturas C!
Osman
1
Internally, tuples are stored a little more efficiently than lists, and also tuples can be accessed slightly faster. Como você poderia explicar os resultados da resposta da dF.
DR5
5
Ao trabalhar com ~ 50k listas de ~ 100 listas de elementos, mover essa estrutura para tuplas diminui o tempo de pesquisa em várias ordens de magnitude para várias pesquisas. Acredito que isso se deva à maior localidade de cache da tupla quando você começar a usá-la devido à remoção da segunda camada de indireção que você demonstra.
horta
tuple(some_tuple)somente retorna a some_tuplesi próprio se some_tuplefor lavável - quando seu conteúdo for recursivamente imutável e lavável. Caso contrário, tuple(some_tuple)retorna uma nova tupla. Por exemplo, quando some_tuplecontém itens mutáveis.
Luciano Ramalho
As tuplas nem sempre são mais rápidas. Considere `` t = () para i no intervalo (1.100): t + = il = [] para i no intervalo (1.100): a.append (i) `` O segundo é mais rápido
melvil james
32

As tuplas, sendo imutáveis, são mais eficientes em termos de memória; lista, por eficiência, atribui um total de memória à memória para permitir anexos sem reallocs constante . Portanto, se você deseja percorrer uma sequência constante de valores em seu código (por exemplo for direction in 'up', 'right', 'down', 'left':), as tuplas são preferidas, pois essas tuplas são pré-calculadas em tempo de compilação.

As velocidades de acesso devem ser as mesmas (ambas são armazenadas como matrizes contíguas na memória).

Mas, alist.append(item)é muito preferido atuple+= (item,)quando você lida com dados mutáveis. Lembre-se de que as tuplas devem ser tratadas como registros sem nomes de campos.

tzot
fonte
1
o que é tempo de compilação em python?
balki
1
@balki: o momento em que a fonte python é compilada no bytecode (que bytecode pode ser salvo como um arquivo .py [co]).
tzot 23/07/12
Uma citação seria ótima se possível.
Grijesh Chauhan
9

Você também deve considerar o arraymódulo na biblioteca padrão se todos os itens em sua lista ou tupla forem do mesmo tipo C. Vai demorar menos memória e pode ser mais rápido.

Epônimo
fonte
15
Vai demorar menos memória, mas o tempo de acesso provavelmente será um pouco mais lento, e não mais rápido. O acesso a um elemento requer que o valor compactado seja unboxed para um número inteiro real, o que atrasará o processo.
27768 Brian
5

Aqui está outra pequena referência, apenas por uma questão ..

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)

Vamos calcular a média:

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

Você pode chamar isso de quase inconclusivo.

Mas, com certeza, as tuplas gastaram 101.239%tempo ou 1.239%tempo extra para fazer o trabalho em comparação com as listas.

Dev Aggarwal
fonte
4

As tuplas devem ser um pouco mais eficientes e, por isso, mais rápidas do que as listas, porque são imutáveis.

ctcherry
fonte
4
Por que você diz que a imutabilidade, por si só, aumenta a eficiência? Especialmente a eficiência da instanciação e recuperação?
Blair Conrad
1
Parece que a resposta de Mark acima da minha cobriu as instruções desmontadas do que acontece dentro do Python. Você pode ver que a instanciação requer menos instruções; no entanto, nesse caso, a recuperação é aparentemente idêntica.
Ctcherry
tuplas imutáveis ​​têm acesso mais rápido que listas mutáveis
noobninja
-6

A principal razão para a Tuple ser muito eficiente na leitura é porque é imutável.

Por que objetos imutáveis ​​são fáceis de ler?

O motivo é que as tuplas podem ser armazenadas no cache da memória, ao contrário das listas. O programa sempre lê a partir da localização da memória da lista, pois é mutável (pode mudar a qualquer momento).

Divakar
fonte