O perigo da ingenuidade

Em meu post anterior sobre shuffling, deixei passar algo muito importante. A primeira coisa que me veio à mente para um algoritmo de embaralhamento é a seguinte:

for (int i = 0; i < cards.Length; i++)
{
  int n = rand.Next(cards.Length);
  Swap(ref cards[i], ref cards[n]);
}

É uma solução simples e agradável para o problema de embaralhamento:

1. Percorrer cada carta do baralho.
2. Trocar a carta atual por outra carta escolhida aleatoriamente.

À primeira vista, essa parece ser uma maneira perfeitamente razoável de embaralhar. É simples, direto e o resultado parece correto. É a própria definição de um algoritmo ingênuo:

Um algoritmo ingênuo é uma solução muito simples para um problema. O objetivo é descrever um algoritmo abaixo do ideal em comparação com um algoritmo “inteligente” (mas menos simples). Os algoritmos ingênuos geralmente consomem grandes quantidades de recursos (tempo, espaço, acessos à memória, …), mas são simples de conceber e implementar.

Um exemplo de algoritmo ingênuo é o bubble sort, que tem apenas algumas linhas e é fácil de entender, mas tem um custo de O(n²) de complexidade de tempo. Um algoritmo mais “inteligente” é o quicksort, que, embora seja consideravelmente mais complicado do que o bubble sort, tem uma complexidade média de O(n log n).

Mas há um problema profundo e obscuro com esse algoritmo ingênuo de embaralhamento, um problema que a maioria dos programadores não enxerga. O senhor o vê? Caramba, me explicaram o problema e eu ainda não o viu.

Veja o que acontece quando uso esse algoritmo ingênuo de embaralhamento para embaralhar um baralho de três cartas 600.000 vezes. Há 3! ou 6 combinações possíveis nesse baralho. Se o embaralhamento estiver funcionando corretamente, devemos ver cada combinação representada cerca de 100.000 vezes.

Como o senhor pode ver, 231, 213 e 132 estão super-representados, e as outras três possibilidades estão sub-representadas. O algoritmo de embaralhamento ingênuo é tendencioso e fundamentalmente quebrado. Além disso, a tendência não é imediatamente óbvia; o senhor teria que embaralhar pelo menos alguns milhares de vezes para ver evidências estatísticas reais de que as coisas não estão funcionando corretamente. É algo sutil.

Normalmente, os algoritmos ingênuos não são errados — apenas simplificado demais e ineficiente. O perigo, nesse caso, é bastante grave. Um programador casual implementaria o shuffle ingênuo, o executaria algumas vezes, veria resultados razoavelmente corretos e passaria para outras coisas. Depois de ser verificado, esse código é uma mina terrestre esperando para explodir.

Vamos dar uma olhada no código correto do Algoritmo de embaralhamento Knuth-Fisher-Yates.

for (int i = cards.Length - 1; i > 0; i--)
{
  int n = rand.Next(i + 1);
  Swap(ref cards[i], ref cards[n]);
}

O senhor vê a diferença? Não vi da primeira vez. Compare as trocas para um baralho de 3 cartas:

rand.Next(3);
rand.Next(3);
rand.Next(3);

rand.Next(3);
rand.Next(2);

O embaralhamento ingênuo resulta em 3³ (27) combinações possíveis de baralho. Isso é estranho, pois a matemática nos diz que, na verdade, existem apenas 3! ou 6 combinações possíveis de um baralho de 3 cartas. No embaralhamento KFY, começamos com uma ordem inicial, trocamos a partir da terceira posição com qualquer uma das três cartas e, em seguida, trocamos novamente a partir da segunda posição com as duas cartas restantes.

O embaralhamento KFY produz exatamente 3 * 2 = 6 combinações, conforme ilustrado acima. Com base na sua experiência em embaralhar cartas físicas, o senhor pode pensar que quanto mais embaralhar, mais aleatório será o baralho. Mas mais embaralhamento resulta em piore não melhores, resultados. É aí que o algoritmo ingênuo dá terrivelmente errado. Vamos comparar todas as permutações possíveis de um baralho de 3 cartas para cada algoritmo:

O senhor pode ver claramente como algumas das combinações de baralho aparecem de forma desigual nos 27 resultados do algoritmo ingênuo. Em termos matemáticos, 27 não é divisível uniformemente por seis.

Chega de teoria. Vamos ver mais resultados. Que tal um baralho de quatro cartas, embaralhado 600.000 vezes?

600.000 dividido por 24 é 25.000; isso é quase exatamente o que vemos logo abaixo da linha para cada combinação possível de cartas com o algoritmo de embaralhamento KFY. O algoritmo ingênuo, em comparação, está em todo o mapa.

Isso piora com baralhos maiores. Aqui está a mesma comparação para um baralho de seis cartas.

Com um baralho de 6 cartas, as diferenças entre os dois algoritmos aumentam ainda mais. A matemática, mais uma vez, explica o motivo.

6! = 720
66 = 46,656

Com 46.656 caminhos para apenas 720 resultados do mundo real, é inevitável que alguns desses caminhos sejam muito super-representados ou sub-representados no resultado. E eles estão sempre presentes. Se o senhor enviasse um jogo de cartas real com um embaralhamento ingênuo, teria que lidar com algumas explorações sérias.

Sei que isso pode parecer matemática básica para alguns dos senhores, mas achei esse resultado surpreendentemente contraintuitivo. Tive muita dificuldade em entender por que o algoritmo de embaralhamento ingênuo, que é pouco diferente do algoritmo de embaralhamento KFY, produz resultados tão terrivelmente incorretos na prática. É uma diferença mínima no código, mas uma diferença profunda nos resultados. O rastreamento de todas as permutações e o processamento das estatísticas me ajudaram a entender o porquê estava errado.

As implementações ingênuas geralmente são preferidas às complexas. A simplicidade é uma virtude. É melhor ser simples, lento e compreensível do que complexo, rápido e difícil de entender. Ou, pelo menos, é geralmente é. Às vezes, como vimos aqui com nosso exemplo de embaralhamento, a simplicidade da implementação ingênua pode induzir ao erro. É possível que o código seja simples e errado ao mesmo tempo. Acho que a verdadeira lição está nos testes. Não importa o quão simples seja o seu código, não há substituto para testá-lo para ter certeza de que ele está realmente fazendo o que o senhor pensa.