As tuplas são mais eficientes que as listas em Python?
-
09-06-2019 - |
Pergunta
Existe alguma diferença de desempenho entre tuplas e listas quando se trata de instanciação e recuperação de elementos?
Solução
O dis
O módulo desmonta o código de bytes de uma função e é útil para ver a diferença entre tuplas e listas.
Neste caso, você pode ver que acessar um elemento gera código idêntico, mas 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
Outras dicas
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 todos os males").
Python torna isso muito fácil: tempo é 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, neste caso, a instanciação é quase uma ordem de magnitude mais rápida para a tupla, mas o acesso ao item é, na verdade, 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 listas.
Claro que se você quiser mudar um item, a lista será definitivamente mais rápida, pois você precisará criar uma tupla totalmente nova para alterar um item dela (já que as tuplas são imutáveis).
Resumo
Tuplas tendem a ter melhor desempenho que listas em quase todas as categorias:
1) Tuplas podem ser constante dobrado.
2) As tuplas podem ser reutilizadas em vez de copiadas.
3) As tuplas são compactas e não alocam demais.
4) As tuplas fazem referência direta aos seus elementos.
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 construídas 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
Correndo tuple(some_tuple)
retorna imediatamente.Como as tuplas são imutáveis, elas não precisam ser copiadas:
>>> a = (10, 20, 30)
>>> b = tuple(a)
>>> a is b
True
Em contraste, list(some_list)
requer que todos os dados sejam copiados para uma nova lista:
>>> a = [10, 20, 30]
>>> b = list(a)
>>> a is b
False
Tuplas não alocam demais
Como o tamanho de uma tupla é fixo, ela pode ser armazenada de forma mais compacta do que listas que precisam ser superalocadas para fazer acrescentar() operações eficientes.
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 Objetos/listobject.c isso 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 referem-se diretamente aos seus elementos
As referências a objetos são incorporadas diretamente em um objeto tupla.Em contraste, as listas possuem uma camada extra de indireção para uma matriz externa de ponteiros.
Isso dá à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 é como a tupla (10, 20)
está armazenado:
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 é como a lista [10, 20]
está armazenado:
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 lista possui uma camada adicional de indireção para uma matriz externa que contém os dois ponteiros de dados.
As tuplas, sendo imutáveis, são mais eficientes em termos de memória;listas, para eficiência, superalocam memória para permitir acréscimos sem constante realloc
S.Então, se você quiser iterar através de uma sequência constante de valores no seu código (por exemplo for direction in 'up', 'right', 'down', 'left':
), as tuplas são preferidas, uma vez que tais 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.
Você também deve considerar o array
módulo na biblioteca padrão se todos os itens em sua lista ou tupla forem do mesmo tipo C.Levará menos memória e pode ser mais rápido.
As tuplas devem ser um pouco mais eficientes e por isso mais rápidas que as listas porque são imutáveis.
Aqui está outro pequeno benchmark, só por fazer.
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 chamá-lo de quase inconclusivo.
Mas claro, as tuplas levaram 101.239%
a hora, ou 1.239%
tempo extra para fazer o trabalho em comparação com listas.
A principal razão para o Tuple ser muito eficiente na leitura é porque ele é 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, diferentemente das listas.O programa sempre lê a localização da memória das listas, pois é mutável (pode mudar a qualquer momento).