Listas, referências e cópias em Python
Um erro bem comum (pelo menos pra mim), lidando com listas em Python
Uma ideia linda mas com resultados adversos
Eu, me sentindo o gênio do Python, resolvo usar uma forma de inicialização de matriz bem bonitinha:
➜ ipython
Python 3.6.2 (default, Aug 5 2017, 23:01:38)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.1.0 -- An enhanced Interactive Python. Type '?' for help.
In [1]: matrix = [['O'] * 3] * 4
In [2]: matrix
Out[2]: [['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O']]
In [3]: matrix[3][2] = 'A'
In [4]: matrix
Out[4]: [['O', 'O', 'A'], ['O', 'O', 'A'], ['O', 'O', 'A'], ['O', 'O', 'A']]
Perceberam? As quatro linhas da matriz tiveram seu terceiro elemento alterado. Eu descobri isso numa prova que estava fazendo, cansado já, implementando os últimos requisitos, num teste de unidade. E, claro, demorou para eu perceber essa obviedade.
Lendo o comando que cria a matriz, poderia-se traduzi-lo para português, mais ou menos assim:
Crie uma lista de três elementos "O", e armazene quatro cópias dela em outra lista.
Aí que está o problema. O Python, obediente, fez o que mandei. Vamos dar uma inspecionada no resultado:
In [5]: [id(x) for x in matrix]
Out[5]: [140365740409672, 140365740409672, 140365740409672, 140365740409672]
Está aí a prova. Criada uma lista, a referência a ela foi repetida.
Uma forma de resolver? Ah, eu já tinha lido sobre isso, mas claro, ficou perdido na memória. O texto Tuplas mutantes em Python, do Luciano Ramalho, explica bem isso.
Então, o nosso problema é criar uma lista 4 vezes, ou melhor dito, criar quatro listas, o que podemos traduzir em python como:
In [12]: matrix = [['O'] * 3 for x in range(4)]
In [13]: matrix
Out[13]: [['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O']]
In [14]: [id(x) for x in matrix]
Out[14]: [140365740472520, 140365751981000, 140365740750408, 140365740637064]
In [15]: matrix[3][2] = 'A'
In [16]: matrix
Out[16]: [['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'A']]
Ou, otimizando um pouco:
In [17]: line = ['O'] * 3
In [18]: matrix = [list(line) for x in range(4)]
In [19]: [id(x) for x in matrix]
Out[19]: [140365752100936, 140365752653384, 140365752654664, 140365752655240]
Usei list aqui, porque ele inicializa um novo objeto a cada chamada, garantindo que não lidaremos com referências a um único.
E pra finalizar, será que isso é mesmo uma otimização?
Primeiro, organizemos melhor o código para as experiências seguintes:
In [50]: def pre_line(): return [list(line) for x in range(4)]
In [51]: def in_line(): return [['O'] * 3 for x in range(4)]
In [52]: pre_line()
Out[52]: [['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O']]
In [53]: in_line()
Out[53]: [['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O']]
Vamos ver com o módulo timeit:
In [29]: from timeit import timeit
In [30]: times = 1000000
In [54]: timeit(in_line, number=times)
Out[54]: 1.8307351850089617
In [55]: timeit(pre_line, number=times)
Out[55]: 2.4262633040198125
Eu pensei que fosse, mas pelo visto não é. Mas qual a razão? Vejamos.
Primeiro com a otimização:
In [68]: cProfile.run('pre_line()')
5 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <ipython-input-66-4ae8eb4f3808>:1(<listcomp>)
1 0.000 0.000 0.000 0.000 <ipython-input-66-4ae8eb4f3808>:1(pre_line)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Agora sem a otimização:
In [69]: cProfile.run('in_line()')
5 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <ipython-input-67-b4163c10d5c0>:1(<listcomp>)
1 0.000 0.000 0.000 0.000 <ipython-input-67-b4163c10d5c0>:1(in_line)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Putz, nenhuma informação...
Então, vamos ver se o problema é mesmo o uso do list:
In [70]: def run_line(): return list(line)
In [71]: def run_mult(): return ['O'] * 3
In [72]: timeit(run_line, number=times)
Out[72]: 0.4813398620171938
In [73]: timeit(run_mult, number=times)
Out[73]: 0.3437652220018208
De fato, o uso do list é a forma mais lenta. Alguém aí ajuda a encontrar uma resposta?