Operação Python “int * list”: a ilusão de segurança

Hoje resolvi um problema usando programação dinâmica: isso significa que tive que construir, inicializar e preencher uma matriz, de acordo com uma fórmula de recorrência.

O problema era, grosso modo, “calcular o número mínimo de substituições de caracteres necessárias para fazer uma string ‘válida’ da string de entrada”.

Meu algoritmo e código eram bons, mas quando executei o código, as respostas que obtive estavam obviamente incorretas. Para todas as entradas, obtive 0 como resposta. Eu sabia, a partir de casos de entrada triviais, que a resposta não era 0 para a maioria dos meus casos de teste.

Felizmente, tive o reflexo de imprimir a matriz inicial e final. E o que vi foi surpreendente: a matriz inicial estava errada !!!

Aqui está o código de inicialização que estava usando para a dpmatriz:

dp = (N+1)*[ 5*[N] ]
dp[0][0] = 0

onde Né um inteiro estritamente positivo, o comprimento da string de entrada. A partir desse código de inicialização, eu esperava uma matriz onde todos os valores fossem iguais ao valor de N, exceto para o valor na entrada [0][0]. Por favor, pare aqui e dê seu melhor palpite sobre o que eu realmente tenho.

Tem um palpite? Bem, a seguinte sessão Python apresenta o problema:

>>> N = 2
>>> dp = (N+1)*[ 5*[N] ]
>>> dp
[[2, 2, 2, 2, 2], [2, 2, 2, 2, 2], [2, 2, 2, 2, 2]]
>>> dp[0][0] = 0 
>>> dp
[[0, 2, 2, 2, 2], [0, 2, 2, 2, 2], [0, 2, 2, 2, 2]]

Como você pode ver, existem 0s na primeira entrada de cada linha da matriz !! O que aconteceu?

Bem, neste ponto, você entendeu: o operador binário *, que se aplica a um número inteiro, digamos k, à esquerda, e uma lista, digamos L, à direita, cria uma nova lista que consiste na kconcatenação de L, e este nova lista contém referências aos mesmos objetos apontados pelas entradas da lista original.

Como você vê, a linha

>>> dp[0][0] = 0

acima está na verdade modificando o objeto apontado por , e , e isso explica o comportamento estranho do meu programa.dp[0]dp[1]dp[2]

Bem, à medida que o protocolo chega ao fim, apresento algumas conclusões. Estou muito feliz por ter impresso os dados no início do processo de depuração. Isso lançou muita luz sobre o que realmente estava acontecendo.

Agora, no que diz respeito ao próprio operador, minha conclusão é a seguinte: o operador ‘int * list’ só deve ser usado quando todos os elementos da lista são imutáveis, ou pelo menos somente leitura .

A propósito, finalmente usei a linha

dp = [ 5*[N] for _ in xrange(N+1) ]
dp[0][0] = 0

para inicializar minha matriz.