Sorteios e Aniversários

No fim de semana passado eu participei do IV ENSL: o Encontro Nordestino de Software Livre, que nessa última edição foi realizado em Natal, no Rio Grande do Norte. Eu achei bastante apropriado, dado que Natal sempre foi um pólo de inovação tecnólogica! Citando alguns exemplos:

• Natal é a sede do Instituto de Neurociências do Miguel Nicolelis, pioneiro das interfaces cérebro-máquina e um dos maiores cientistas vivos.
• Alex Kipman, diretor de incubação da Microsoft, se inspirou na cidade para criar o Xbox Kinect (que, vocês devem lembrar, tinha o nome-código de Project Natal).
• Na década de 80, era onde estudava Tadeu Curinga da Silva, pioneiro dos videogames nacionais e autor do jogo Em Busca dos Tesouros, o melhor jogo da plataforma ZX-81.
• Além disso, Natal também é onde mora o Karlisson Bezerra, autor das tirinhas do Nerdson!

Embora o turismo nerd tenha sido excelente, eu fiquei um pouco frustrado de não ter aproveitado tanto o turismo tradicional. Eu consegui ir à praia e provar a deliciosa manteiga de garrafa, mas não deu tempo de fazer o típico passeio de buggy pelas dunas. Por outro lado, posso não ter feito o passeio de buggy, mas presenciei um outro tipo de bug!

Tradicionalmente, todo encontro de software livre termina com um sorteio de brindes. Como é um evento de programadores, naturalmente não se usou um saco plástico cheio de papéis com os nomes de cada um. Ao invés disso, o povo programou uma solução na hora mesmo, usando só três linhas de python:

import random
x = open("participantes.txt").readlines()
print x[random.randint(0, len(x))]

Como isso foi feito no modo interativo, então basta repetir a última linha para realizar um novo sorteio. Mas enquanto eles digitavam isso no telão, eu pensei: putz, esse código tem dois bugs. Você consegue achá-los?

Primeiro Bug

O primeiro bug, na real, não é do programa e sim da API do Python. Quando você projeta uma API, precisa ter muito cuidado para que as interfaces sejam consistentes, e o randint() é um dos raros casos onde o Python pisa no tomate.

O problema é que quase todas as definições de intervalo do Python usam intervalos semi-abertos, mas o randint usa um intervalo fechado (se você não lembra o que é um intervalo aberto ou fechado, pergunte ao professor Joe). Na notação de list slices, ou mesmo no range(), o último número não faz parte da lista; mas no randint() o último número conta.

Por isso, se você tentar sortear com randint(0, len(x)), ele pode sortear um número além do fim da lista, e você vai ter um erro do tipo list index out of range. Murphy sendo Murphy, é claro que isso aconteceu ao vivo lá no telão :)

Depois que uma API já está publicada e sendo usada, é muito difícil consertar um bug assim. Num mundo ideal você consertaria a interface, mas isso poderia quebrar todos os códigos legacy que a usam. Por isso, o melhor que dá pra fazer é depreciar a função original e propor uma interface nova, que no nosso caso é a randrange():

print x[random.randrange(0, len(x))]

Nesse problema em específico tem uma outra solução até mais elegante, que é usar o choice():

print random.choice(x)

Mas nenhuma dessas soluções conserta o outro bug do programa...

Segundo bug

Esse é mais sutil. No começo o programa estava funcionando bem, mas em um certo ponto, eis que o programa sorteia uma pessoa que já tinha sido sorteada antes! Eram mais ou menos 700 participantes, então a chance disso acontecer deveria ser bem pequena né? Mas algum tempo depois dessa pessoa, teve mais uma que foi sorteada duas vezes, e depois dessa ainda mais uma. Como pode um evento tão raro acontecer tantas vezes?

Marmelada não era, porque todo mundo viu o código, então o erro deve estar no gerador de números aleatórios do Python, certo? Surpreendentemente, a resposta é não! Esse é um caso clássico onde a nossa intuição falha. A análise ingênua é que a chance de um número ser sorteado duas vezes é 1/700 vezes 1/700, ou seja, 0.0002%. Mas esta é a análise correta do problema errado.

Se eu tivesse feito só dois sorteios, entre 700 participantes, e perguntasse qual era a chance do Ricbit ganhar nos dois, aí sim a chance seria 0.0002%. Mas o nosso problema é diferente. Nós temos um número p=700 de participantes, e vamos fazer s=70 sorteios (de olho eu acho que foram uns 70 sorteios: tinha brinde pra caramba no evento, e alguns sorteados eram descartados porque não estavam na sala).

O enunciado correto então é: qual o valor esperado do número de pessoas que é sorteada duas vezes? Esse valor é bem mais alto do que a intuição imagina!

Vamos calcular passo a passo quanto dá isso. Primeiro, vamos calcular qual é a probabilidade do Ricbit ser sorteado no primeiro evento. Isso é fácil né, a chance é 1/p. A chance oposta, ou seja, do Ricbit não ser sorteado no primeiro evento, é de (1-1/p). Continuando, a chance do Ricbit não ser sorteado em nenhum evento, é a abaixo:



Qual é a chance do Ricbit ser sorteado no primeiro evento e não ser sorteado em nenhum outro? Pelo mesmo raciocínio acima, ela é:



E qual a chance do Ricbit ser sorteado uma única vez durante toda a série de sorteios? Ora, é a chance de ser sorteado só no primeiro sorteio, mais a chance de ser sorteado só no segundo, e assim por diante. Como essas chances são todas iguais, então a chance do Ricbit ser sorteado uma única vez é:



Uma outra maneira de pensar a fórmula acima é que ela representa a chance de ser sorteado uma única vez numa posição qualquer, vezes o número de posições possíveis.

Agora chegamos onde queríamos, qual a chance do Ricbit ser sorteado exatamente duas vezes na série toda? Analogamente, é a chance de ser sorteado duas vezes, multiplicada pelo número de combinações possíveis dos dois sorteios ao longo da série. Logo, ela vale:



Por fim, qual o valor esperado do número de repetições? Uma repetição é quando uma pessoa é sorteada duas vezes: então basta, para cada pessoa, somar a probabilidade de ser sorteado duas vezes. Daí, o valor esperado final é:



Substituindo os parâmetros, descobrimos que o valor esperado é 3.1, o que realmente é bem próximo das três repetições que eu presenciei (nos cálculos eu desprezei sorteios triplos, quádruplos, etc, porque esses são realmente raros). Eu fiz uma simulação de Monte Carlo para quem só acredita vendo:

Simulação de Monte Carlo em Python

Na verdade, esse resultado contra-intuitivo é bem conhecido na literatura, o povo chama de Paradoxo do Aniversário. Numa festa com 30 pessoas, qual a chance de haver duas pessoas com o mesmo aniversário? A intuição é que isso deve ser raro, mas a probabilidade, na verdade, é de 70%. A argumentação é exatamente a mesma anterior, e, de fato, se você usar a nossa fórmula com s=30 e p=365, vai descobrir que o valor esperado é 1.1. Ou seja, em média, festas com 30 pessoas costumam ter um par de pessoas com o mesmo aniversário.

Se você trabalha com computação, então isso tem uma aplicação prática. A chance de repetição em um sorteio é exatamente a mesma chance de uma colisão em uma hash table, assumindo que sua função de hash tem distribuição uniforme. Por isso, quando você for dimensionar o tamanho de uma hash, pode usar nossa fórmula para saber o número esperado de colisões (por exemplo, em 70 inserções numa hash de tamanho 700, você vai ter em média 3 colisões).

E como resolver o problema original do sorteio? Basta tirar da lista os números que já foram sorteados! Uma implementação curta em python é a abaixo:

import random
x = open("participantes.txt").readlines()
random.shuffle(x)

print x.pop()

Ao invés de sortear nomes de maneira independente, você simplesmente faz uma permutação aleatória da lista com o shuffle() e vai tirando os elementos de um em um usando o pop(). Esse programa é bem curto e não tem os problemas do original. Mas, no fim das contas, se o programa original não tivesse nenhum bug, o sorteio não teria sido engraçado como foi :)

Se você é veterano do FISL, considere no ano que vem ir também ao ENSL. O povo é divertido, a comida local é excelente, e nada supera ir a uma praia do Nordeste entre uma palestra e outra :)

O Altar de Apolo

Quando pensamos na influência da religião na ciência, usualmente o que vem à mente é o obscurantismo medieval, como o julgamento do Galileu, ou então as cruzadas modernas contra a evolução e a pesquisa com as células-tronco. Mas também houve episódios onde a religião ajudou a ciência, e deles o meu preferido é o do Altar de Apolo.

Consta que, por volta de 400 aC, uma grande peste se espalhou pela cidade grega de Delos. Ela foi tão intensa, que estima-se que um quarto da população local tenha morrido. Preocupados com a saúde da população, os governantes resolveram consultar a única pessoa que poderia saber a causa da peste: o Oráculo de Delphi.

No Oráculo, as perguntas eram feitas para a sacerdotisa de Apolo, que entrava em contato diretamente com o Deus para solicitar a resposta. Diz-se que o Oráculo era construído sobre uma fenda que exalava gases alucinógenos, e isso ajudava no contato com o divino.

A sacerdotisa disse que a peste era causada pelo descontentamento de Apolo, e o único jeito de deixá-lo alegrinho novamente era com uma oferenda: eles deveriam duplicar o altar de Apolo, que era um grande cubo de mármore.

Os governantes então mediram as dimensões do cubo, duplicaram as arestas e fizeram o novo altar. Porém, mesmo seguindo à risca a orientação, a oferenda não funcionou, e a peste continuou matando todo mundo! Revoltados, eles foram tirar satisfação com o Oráculo: como assim a gente segue sua recomendação e não dá certo?

O Oráculo, que de bobo não tinha nada, explicou o que aconteceu: quando eles duplicaram cada aresta, o volume do altar cresceu oito vezes! Na verdade, o que eles deveriam ter feito era duplicado o volume, e não a aresta.

Isso deixou os matemáticos da época perplexos. Para duplicar o volume do cubo mantendo as proporções, a aresta precisa ser maior que a original por um fator igual à raiz cúbica de dois. Agora, se o Apolo é tão chato a ponto de não aceitar duplicar a aresta, ele também não iria aceitar uma aproximação como 1,26. Teria que ser o valor exato.

Mas como construir o valor exato usando as ferramentas disponíveis na época, ou seja, régua e compasso? Esse foi um dos grandes problemas da antiguidade, e a resposta correta só foi aparecer quase 2200 anos depois: na verdade, é impossível construir esse número só com régua e compasso.

Mas não pense que os gregos desistiram! Quando viram que esse caminho da régua e compasso não estava dando frutos, resolveram apelar para outros métodos. O mais impressionante deles foi criado por Arquitas, um general grego que era amigo pessoal de Platão.

O raciocínio de Arquitas foi o seguinte: régua e compasso são ferramentas para resolver problemas no plano; como nosso problema é espacial, provavelmente precisamos de ferramentas que operem no espaço. Arquitas tinha uma visão espacial assombrosa, e conseguiu construir a raiz cúbica de dois usando a intersecção de três sólidos.

Para entender a solução de Arquitas, vamos precisar de computação gráfica e geometria analítica. O primeiro passo é construir o segmento com o lado do cubo (digamos que o comprimento seja a). Centrados em um dos vértices do segmento, nós desenhamos três círculos perpendiculares de raio a, paralelos a cada um dos eixos coordenados:

Nós vamos usar cada um dos círculos para construir um sólido diferente. Primeiro, pelo círculo perpendicular ao Ox nós traçamos um cone que parte da origem:

A equação desse cone é a abaixo (se não é óbvio pra você que isso é a equação do cone, eu coloquei no final do post um quadro azul com as demonstrações).

O próximo sólido é um cilindro, construído estendendo o círculo perpendicular ao eixo Oz:

A equação desse cilindro é a abaixo:

Por fim, nós pegamos o círculo restante e o rotacionamos em torno do eixo Oz, criando um toróide:

A equação desse toróide é a abaixo:

O insight do Arquitas é que essas três superfícies se encontram exatamente no ponto que queríamos!

Vamos verificar que isso é verdade, usando as equações das superfícies:

Tal como queríamos! A parte impressionante disso é pensar que o Arquitas concebeu essa solução sem usar computação gráfica e sem saber geometria analítica. Na verdade, ele nem sabia escrever equações: mesmo uma coisa simples como o sinal de igual só foi inventado 1900 anos depois!

Se você quiser renderizar em casa a solução do Arquitas, pode usar os meus scripts de povray abaixo (para renderizar equações implícitas é só usar o comando isosurface):

Scripts povray com a solução do Arquitas

Por fim, o quadro azul para quem não sabe como derivar as equações implícitas. Enjoy!

Cone

O cone é formado por um contínuo de círculos no plano yz. Portanto, a equação de cada círculo deve ser da forma:

Mas o círculo em x=0 tem raio 0, e em x=a tem raio a. Logo o raio é igual a x.

Cilindro

O cilindro é um contínuo de círculos no plano xy, todos com o mesmo raio a, e centrados no ponto (a,0,0). O z nesse caso é qualquer, então a equação é:

Toróide

Eu não achei jeito fácil de derivar o toróide, então vai o difícil mesmo. Vamos construir a superfície como a soma de dois vetores, um que gira no plano xy, e um que gira nos planos perpendiculares a esse. A equação paramétrica do círculo base do toróide (visto de cima), é:

Cada ponto desse círculo é o centro de um outro círculo, no plano perpendicular formado pelo y e por esse mesmo vetor que aponta pro centro. Daí, a equação desse segundo círculo é:

A equação paramétrica final é a soma dos dois vetores. Já separando em coordenadas:

Agora nós elevamos ao quadrado e somamos x e y:

Podemos elevar z ao quadrado e somar com o anterior:

Opa, agora é só elevar ao quadrado de novo e substituir:

QED. Se alguém souber de algum jeito mais fácil, me ensine :)

Aritmética com Regexp

Dia desses eu descobri que o SPOJ agora tem uma seção só para problemas pontuados por shortest code, e fiquei super animado! Mas não demorou muito até eu notar a maior constante desse tipo de concurso: você pode até participar usando Python e Haskell, mas, para competir, só usando Perl.

Então lá fui eu aprender Perl. Apanhei um pouco no começo, mas acabei descobrindo o segredo para conseguir uma boa colocação: basta resolver todos os problemas usando regexp. Os regexps originais do Posix são apenas autômatos finitos, mas a engine do Perl é bem mais poderosa que isso.

Naturalmente, eu fiquei tentado a ver quais são os limites do regexps do Perl. Por exemplo, dá pra fazer aritmética com eles? Depois de pensar um pouco, acabei concluindo que dá sim!

Antes de mostrar como eu fiz, uma revisão de Perl. O único comando que eu vou usar é o s///g (substituição com regexp). O primeiro argumento é uma regexp que será procurada na sua string de input, e o segundo é um string, possivelmente interpolada, que vai substituir o match. A opção g permite múltiplas substituições, recomeçando do ponto onde a última terminou. Por exemplo:

input: "kkkkkk Restart kkkk sacanagem"
regexp: s/k+/LOL/g
output: "LOL Restart LOL sacanagem"

Antes de fazer qualquer conta, precisamos também definir a representação numérica. Na escola nós aprendemos a fazer contas em decimal, que tem dez símbolos, de 0 a 9. Mais tarde, computeiros aprendem binário, que tem só dois símbolos: 0 e 1. Eu vou agora fazer contas em unário, que tem um símbolo só: I (eu escolhi o símbolo I para ficar parecido com os números romanos).

No sistema unário, o número é representado por repetições do símbolo único. Por exemplo:

1  = I
4  = IIII
10 = IIIIIIIIII

Por fim, para as regexps não ficarem muito grandes, eu vou me restringir apenas às operações definidas nos inteiros positivos (ou seja, tanto os argumentos quanto os resultados precisam ser inteiros positivos). Vamos lá então:

Adição

s/\+(I+)=/$1/g

A adição é a operação mais simples, basta tirar os sinais de mais e igual. O resultado é a concatenação dos operandos. Vamos ver, por exemplo, como ficaria 4+7.

"IIII+IIIIIII="
s/\+(I+)=/$1/g

"IIIIIIIIIII"

Como esperado, o resultado é 11.

Subtração

s/(I+)-\1=//g

Para fazer a subtração, nós usamos o recurso de backreference. Se ele achar um conjunto no lado direito, pode apagar esse conjunto e um outro igual no lado esquerdo. Sobram só os caracteres que estavam no primeiro mas não estavam no segundo, ou seja, a subtração deles. Vejamos o exemplo de 7-4:

"IIIIIII-IIII="
s/(I+)-\1=//g

"III"

Multiplicação

s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

A multiplicação é um pouco mais complexa, agora precisamos usar o operador (?=), que serve para fazer positive lookahead, ou seja, ele faz o match, mas não consome o input. Como resultado, o operador /g pode passar várias vezes pela mesma string, e cada I que ele encontra no lado esquerdo é trocado pela string inteira do lado direito. Vejamos um exemplo passo-a-passo de 3*6 (mas note que o Perl faz isso num passo só, eu estou fazendo em vários passos só pra ficar mais claro).

"III*IIIIIII="
s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

"IIIIII""II*IIIIIII="
s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

"IIIIIIIIIIII""I*IIIIIII="
s/(I)(?=I*\*(I+))(\*I+=)?/$2/g

"IIIIIIIIIIIIIIIIII"

Divisão

s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

A divisão é similar à multiplicação, mas, ao invés de somas sucessivas, nós usamos subtrações sucessivas. Vejamos o exemplo de 12/4:

"IIIIIIIIIIII/IIII="
s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

"I""IIIIIIII/IIII="
s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

"II""IIII/IIII="
s/(I+)(?=I*\/\1\=)(\/I+=)?/I/g

"III"

GCD

s/gcd\((I+)\1*,\1+\)=/$1/g

Por que parar nas quatro operações? É bem simples fazer também o gcd (máximo divisor comum). Nesse caso basta mandar repetir a backreference, o resultado é que os matches sempre vão ser múltiplos do tamanho dela. Como o primeiro grupo é greedy, ele vai tentar fazer o maior match possível, e daí temos como resultado o gcd. Vejamos para 15 e 9:

"gcd(IIIIIIIIIIIIIII,IIIIIIIII)="
s/gcd\((I+)\1*,\1+\)=/$1/g

"III"

Embora brincar com regexps desse jeito seja divertido, vale a recomendação de sempre: faça isso apenas acompanhado de adulto responsável :)

O algoritmo mais lento do oeste

Por que as pessoas aprendem complexidade computacional? Para achar os algoritmos mais rápidos, é claro. Dada uma lista de algoritmos equivalentes, você pode ordená-los pela complexidade, e o primeiro da lista é o mais eficiente.

Uma brincadeira divertida é fazer isso ao contrário: dada uma especificação, qual o algoritmo determinístico mais lento que a resolve? Por exemplo, qual o algoritmo mais lento para decompor um número em fatores primos?

O algoritmo mais rápido que resolve esse problema é o algoritmo de Shor, que roda em O((log n)³) e requer um computador quântico. Meu candidato a algoritmo mais lento é o abaixo, que na falta de nome melhor eu chamei de Fatoração Bozo:

import itertools

def factor(n):
 solutions = []
 for f in itertools.product(range(1,1+n),repeat=n):
   if reduce(lambda x,y: x*y, f) == n:
     solutions.append(filter(lambda x:x>1, list(f)))
 solutions.sort(key=len, reverse=True)
 return solutions[0]

Parece complexo, mas o funcionamento é bem simples. Vamos pensar no nosso objetivo: queremos achar uma lista de fatores primos, que multiplicados resultam no número desejado (vamos chamá-lo de N).

Nós sabemos que os primos dessa lista são menores ou iguais a N, e sabemos também que essa lista nunca vai ter mais que N elementos. A primeira coisa que fazemos no algoritmo é gerar todas as possíveis listas candidatas, que são o produto cartesiano do intervalo de 1 a N com N repetições. Por exemplo, para N=3, teríamos 27 combinações:

111 112 113 121 122 123 131 132 133
211 212 213 221 222 223 231 232 233
311 312 313 321 322 323 331 332 333

Em python o jeito mais fácil de gerar essa lista é usando itertools.product(), que faz o serviço sozinho. Mas, dessas listas, só interessam aquelas cujo produto seja igual a N. Por exemplo, se N=4, então as listas interessantes são:

1114 1122 1141 1212 1221
1411 2112 2121 2211 4111

Python não tem um operador para multiplicação de listas como tem o sum() para adições, mas pra isso que serve o reduce() né. As listas selecionadas até agora estão boas, mas elas têm um monte de elementos 1 que não contribuem em nada. Usando o filter() podemos jogar fora os uns. Para N=4:

4 22 4 22 22 4 22 22 22 4

Várias listas repetidas, mas tudo bem. O truque agora é notar que, de todas essas listas, a fatoração em primos é a lista de comprimento máximo. É fácil provar isso: se a lista máxima tivesse um elemento composto, então você poderia fatorá-lo, e trocar o número composto pela sua fatoração. Logo, você estaria gerando uma lista maior que a lista máxima, o que é uma contradição.

Pedindo para que o Python ordene as listas por tamanho, basta pegar a primeira lista da seqüência e temos então a nossa fatoração!

E qual a complexidade dessa solução? Ela é dominada pelo número de listas que geramos no primeiro passo, então a complexidade da Fatoração Bozo é maior que O(nⁿ). Se você não tem noção de como isso é lento, veja o tempo que esse código leva para fatorar alguns números:

N=6 - 0.2 segundos
N=7 - 2.1 segundos
N=8 - 45.8 segundos
N=9 - 20 minutos

A função cresce tão rapidamente que, para fatorar N=18, você levaria mais tempo que a idade do universo até agora! Como exercício para o leitor, tente calcular quanto tempo levaria para fatorar o RSA-704, que em decimal tem 212 dígitos :)

Batman e a escalabilidade

Dia desses eu resolvi colocar os meus gibis em ordem (tarefa bem difícil, dada a quantidade deles). Mas logo no começo eu já apanhei pra conseguir ordenar dois deles. Ambos eram Punisher #1, ambos do Garth Ennis, mas qual veio antes?

Normalmente esse tipo de dúvida eu resolvo consultando o Grand Comics Database, um repositório imenso de informações sobre gibis. Porém, após usar um pouco a busca do site, eu notei que ela, hm, não funciona tão bem.

Por exemplo, um dos meus gibis é o Sergio Aragonés' Groo: Mightier than the Sword. Se você buscar no site por "mightier than sword", ele não acha, porque só faz match exato. Se você buscar por "Groo", também não acha. O nome foi indexado como "Groo:", e sem os dois pontos no final ele não acha. Por fim, se você buscar por "Aragones" ele também não acha, porque você não colocou o acento.

A primeira coisa em que pensei foi "poxa, é simples fazer melhor que isso". Mas falar é fácil né? O jeito é arregaçar as mangas e fazer um search que funcione!

Design

Vamos então aos requisitos: eu quero fazer um buscador que me retorne todas as séries que constem no database do GCD. O buscador precisa ser web-based, escalável e de latência baixa.

Para conseguir latência baixa, o jeito mais fácil é fazer alguma coisa que seja AJAX-like. E pra isso, minha ferramenta predileta é o Google Web Toolkit. Eu até gosto de programar em javascript, acho a linguagem legal, mas o problema é que cada browser implementa javascript de um jeito, e na prática você precisa perder um tempão com as peculiaridades de cada browser.

Com o GWT você escreve a aplicação uma vez só, em Java, e ele então compila seu código, gerando um javascript customizado para cada browser. Quando você faz o request, ele faz o download só do javascript correspondente, assim você não precisa gastar banda baixando código do Firefox se está rodando o Chrome. Daí em em diante é tudo AJAX, ou melhor, AJAJ (por default ele usa JSON ao invés de XML).

Para que a aplicação fosse escalável, eu usei o Google App Engine. Com ele, você pode rodar seu servidor direto na infraestrutura do Google, com todas as vantagens que isso implica. Por exemplo, você não precisa se preocupar em ficar dimensionando quantas máquinas são necessárias, ele faz isso sozinho pra você, adicionando máquinas conforme a carga no servidor começa a subir.

O App Engine ainda tem outra vantagem: ele é gratuito! Quer dizer, é gratuito até um certo limite, mas um buscador de gibis é uma aplicação de nicho, e na prática eu não vou ter tráfego suficiente para precisar passar desses limites. Por exemplo, o limite do database gratuito é 1GB, mais que suficiente pra guardar todos os dados que vão ser buscados.

Implementação

Definida a plataforma, vamos à implementação. O jeito mais fácil de fazer um buscador é usando uma lista invertida. Por exemplo, suponha que o database contém os gibis abaixo:

1 - Green Arrow
2 - Green Lantern
3 - Iron Lantern
4 - Green Lantern: Rebirth

A lista invertida correspondente fica assim:

arrow: 1

green: 1,2,4

iron: 3

lantern: 2,3,4
rebirth: 4

Tendo a lista invertida é fácil fazer a busca: basta procurar na lista invertida cada palavra da minha query, e fazer a intersecção dos conjuntos resultantes. Por exemplo, "Green Lantern" retorna {1,2,4} e {2,3,4}, cuja intersecção é {2,4}, que são os dois gibis que vamos retornar. Se as listas estiverem ordenadas, você pode calcular essa intersecção em O(n), e se não estiverem ordenadas, você ainda pode fazer em O(n) usando um pouco de espaço extra (como?)

Dentro do App Engine, as listas invertidas vão ficar guardadas no Datastore, que é um database escalável construído em cima da BigTable. Vale notar que o Datastore não é um database convencional: ao invés da analogia comum de uma tabela com linhas e colunas, o mais apropriado é pensar nele como se fosse um dicionário de dicionários: cada "linha" agora é a chave do dicionário mais externo, e as "colunas" são as chaves dos dicionários internos. Dessa maneira, não é obrigatório que cada "linha" tenha sempre as mesmas "colunas".

Adicionalmente à lista invertida, nós vamos guardar também uma lista direta. Assim, quando eu descobrir que os gibis a mostrar são o 2 e o 4, eu posso ir na lista direta e pegar mais dados sobre eles, como nome, editora, ano de lançamento, etc.

Depois disso, nós ainda precisamos fazer alguma espécie de ranking pra descobrir em qual ordem vamos mostrar os resultados. Em geral essa é uma das partes mais difíceis de uma search engine, mas eu resolvi simplificar e ordenar por número de edições (então Action Comics, que tem quase 900 edições, vai aparecer antes de Slave Girl Comics, que tem só duas).

Por fim, todo esse trabalho de lista invertida, intersecção, lista direta e ranking pode eventualmente ficar meio pesado, então nós vamos colocar um cache no caminho para guardar todas as queries já feitas, sem precisar repetir trabalho. O App Engine fornece um módulo de Memcache que é ideal para isso.

Preparando os dados

Antes de começar a usar o buscador, precisamos gerar as listas e colocá-las dentro do Datastore. O GCD fornece um arquivão com o dump do MySQL deles (que na verdade é um arquivo texto com 330MB de INSERTs). Com os dados em mãos, eu escrevi um script python que lê esses dados, cria a lista invertida e a lista direta, e faz o bulk upload desses dados para o Datastore.

O único cuidado extra nessa etapa é tomar cuidado com o unicode, já que eu quero que buscas por "mônica" e "monica" retornem o mesmo resultado. Uma maneira seria tirando os acentos no cliente, mas pra que fazer isso online se você pode fazer offline né? Mais fácil, na hora de criar a lista invertida, gerar duas entradas iguais, uma com "mônica" e outra com "monica".

Outra idéia que tive foi retornar as capas dos gibis, e não apenas os nomes deles. Nesse caso o processo foi um pouco mais complicado, porque o GCD não fornece um arquivão com todas as capas, assim como eles fazem com o dump do MySQL. Eles acham que fornecer esse arquivão para download poderia ser uma violação do fair use, então a recomendação é "se você quer as capas, faça um crawling você mesmo".

Bora fazer um crawler então! Usando várias threads em python foi tranquilo, eu baixei os 500MB de capas em poucas horas. Como o Datastore não foi feito para guardar imagens, eu optei por hospedar as capas no meu próprio servidor (www.ricbit.com).

O cliente

Escrever o cliente usando o GWT foi a parte mais difícil. Não que programar em GWT seja difícil, pelo contrário, usando UiBinder é bastante fácil. O problema mesmo é que eu manjo de CSS menos do que gostaria, então demorei um tempão até conseguir o layout desejado. Mas, como esperado, o resultado funciona em tudo quanto é browser, até mesmo no IE!

E para dar um toque especial no layout, eu pedi para a minha esposa fazer umas ilustrações para o logo e para a tela de loading do site, que ficaram bem bacanas (se você precisa de ilustrações para o seu site, fale com a Ila Fox!)

Por fim, eu ainda precisava de um jeito de fazer profiling do site, então fiz com que o servidor me retornasse o tempo gasto em cada etapa do processamento, e usei o Google Chart Tools para apresentar esses dados de uma maneira fácil de interpretar.

Segurança

Você não pode fazer uma aplicação web-based sem pensar na segurança, certo? Mas, felizmente, esse buscador não tem muitos pontos vulneráveis. O único ponto onde o usuário malicioso pode tentar fazer alguma coisa é no campo da query, mas eu não preciso nem sequer sanitizar, porque tudo que a aplicação retorna são os nomes dos gibis que já estão no datastore.

Na verdade, só de rodar a aplicação no App Engine você ainda ganha na faixa um monte de vantagens, entre elas detecção de ataques de DoS. Ele sabe sozinho filtrar ips que estão te bombardeando sem nem precisar configurar nada.

Juntando as peças

No final, o sistema completo ficou assim:

Se você quiser testar a aplicação, basta clicar no screenshot abaixo:

Agora finalmente dá para achar aquele gibi do Groo :)

Profiling

Com o sistema completo e funcionando já dá pra fazer o profiling. Para isso, basta digitar "debug:" antes de uma query qualquer. Por exemplo, se você fizer "debug: Groo" logo após o deploy do servidor, o resultado vai ser esse:

O App Engine faz resource management de maneira bem agressiva, se você não tiver nenhuma query em 10min, ele derruba sua instância. Daí, a primeira query que você fizer tem o overhead de levantar o serviço novamente, que nesse caso foi de quase 5 segundos. Mas se você fizer em seguida a mesma query, ela vai ser bem mais rápida:

Bem melhor né? Alguns poucos milisegundos no memcache, o resto é só o tempo de trafegar o resultado do servidor pro seu cliente. No total, pouco menos de 350ms de roundtrip, o que é bastante rápido.

Mas essa é uma query fácil. Uma das queries mais difíceis é "debug: Batman", porque existem muitos, muitos gibis do Batman. Vejamos:

O tempo é praticamente todo gasto baixando os dados dos gibis da lista direta, quase 3 segundos. Mesmo considerando que é um batch request de 824 gibis, três segundos é meio lento. Mas ao usar o Datastore, o importante é notar que esse tempo é independente da carga. Você até consegue uma solução customizada mais rápida que isso, mas sem tomar muito cuidado, o tempo de cada request vai aumentar se o número de usuários simultâneos crescer. Com o Datastore, o tempo é sempre o mesmo, e você está imune a baleiadas.

Naturalmente, isso só vale para a primeira vez. Se outro usuário buscar por Batman logo em seguida, ele vai pegar o resultado do memcache:

Agora deu só 500ms, e o tempo todo é praticamente só o overhead do download dos 824 gibis.

Outra query curiosa é "debug: Captain America Comics". Existem inúmeros gibis com captain (Captain America, Captain Marvel, etc), inúmeros com america (Captain America, Justice League of America, etc), e um outro sem número de Comics, então o tempo agora não é dominado pela lista direta:

Dessa vez dá pra ver o tempo que ele gasta fazendo a intersecção das listas invertidas (e note que até agora nós nem vimos tempo algum com ranking, é desprezível). O tempo total foi de 800ms, mesmo sem o memcache.

O source

É claro que isso tudo foi uma visão bem high-level do Gibit, tem um monte de detalhes curiosos que eu omiti para não deixar o post muito grande. Se você quiser ver a implementação, o código é open source e está disponível no Google Code:

Source code do Gibit

Se você tiver alguma dúvida específica, é só deixá-la nos comentários que eu tento responder. Enjoy :)

ZenoReduce

"O movimento é uma ilusão", dizia o sábio grego Ζήνων (que translitera para Zeno, Zenon ou Zenão). Ele tinha várias demonstrações dessa afirmação, e uma delas começava com uma tartaruga desafiando o ligeiro Aquiles: "duvido que você chegue aqui onde eu estou". Ora, Aquiles só precisa de uma rápida corrida para chegar onde a tartaruga está. Ou não?

Para ajudar, a tartaruga colocou no caminho um monte de bandeirinhas. A primeira bandeirinha está na metade do caminho entre Aquiles e a chegada. A segunda bandeirinha está na metade do caminho entre a primeira bandeirinha e a chegada, e assim por diante.

Olha só que curioso: quando o Aquiles estiver na primeira bandeirinha, ele ainda vai precisar passar pela segunda, que está no meio do caminho que falta. Quando ele chegar na segunda, ainda precisa passar pela terceira, e assim por diante. Não importa em qual bandeirinha ele esteja, sempre tem mais uma no meio do caminho restante. E se sempre falta uma bandeirinha, então ele nunca vai chegar na tartaruga! Daí a conclusão do Zeno, de que o movimento do Aquiles é só uma ilusão.

Para os gregos isso era um paradoxo, mas isso é porque eles desconheciam limites e séries convergentes. Hoje em dia nós sabemos que o tempo entre uma bandeirinha e outra sempre diminui, e eventualmente tende a zero. Nesse caso o paradoxo se dissolve, e a nossa intuição de que o Aquiles consegue chegar na tartaruga volta a ser verdadeira.

Agora imagine como seria divertido se tivéssemos na computação um conceito análogo! Por exemplo, para percorrer uma lista, um computador leva sempre o mesmo tempo em cada elemento. Mas em algum universo paralelo poderíamos ter um computador que, a cada elemento da lista, leva só metade do tempo do passo anterior. Ao invés de serem máquinas de Turing, nesse universo paralelo os computadores seriam máquinas de Zeno.

Na verdade, eu fiquei tão curioso em saber como seriam esses computadores que escrevi um emulador deles pra brincar:

Emulador de máquina de Zeno, escrito em python
Unit tests do emulador, usando pyunit e mox

A api do emulador fornece uma única operação: o ZenoReduce. Ele funciona como se fosse um reduce normal do python, mas o tempo que ele leva em cada iteração da lista é metade do tempo da iteração anterior. A complexidade do ZenoReduce é curiosa: ela é igual à complexidade da operação binária que você usa, e independente do tamanho da lista. A demonstração é simples e está na caixa azul:

Livros clássicos de complexidade, como o do Papadimitriou, calculam complexidade contando o número de passos que o algoritmo executa. Mas isso só vale para máquinas de Turing, onde os passos tem sempre a mesma duração. Na máquina de Zeno, temos que medir complexidade usando o tempo de execução, ao invés do número de passos.

Suponha que o ZenoReduce vai executar uma operação binária qualquer em cada elemento da lista, e essa operação tem uma complexidade O(f(x)). Logo, o primeiro passo do ZenoReduce leva O(f(x)), o segundo leva O(f(x))/2 e assim por diante. Assim, se a lista tem n elementos, então a complexidade total é:



Mas 2.O(f(x)) é o próprio O(f(x)), logo provamos que o valor de n realmente não importa.

Escrever programas usando o ZenoReduce é divertido, porque os melhores algoritmos para ele usualmente são os piores na máquina de Turing. Por exemplo, para verificar se um número é primo, podemos usar a versão abaixo:

import zeno

def is_prime(n):
  return zeno.zenoreduce(
    lambda x,y: x and (n%y!=0), 
    xrange(2,n), True)

Para rodar esse ZenoReduce, você precisa usar a função run da api, que liga o módulo de emulação. O run requer uma função sem parâmetros que será executada na máquina de Zeno:

>>> zeno.run(lambda:is_prime(10001))
(False, 0.15625, 0.0)

A saída é uma tupla: o primeiro elemento é o resultado (False, ou seja, 10001 não é primo), o segundo elemento é o tempo que ele levou pra rodar na sua máquina (wall time, 0.15s), e o terceiro é quanto tempo ele teria levado se tivesse rodado em uma máquina de Zeno (zero, ou melhor, um tempo tão pequeno que é menor que a precisão do python).

A complexidade desse algoritmo é O(mod), ou seja, quem domina é o tempo para calcular o resto de uma divisão. Nossos computadores modernos fazem divisão por hardware, então esse tempo é O(1), porém só até um certo limite. Quando o número é grande, você precisa usar uma lib de bignum, e a complexidade aumenta. Mas aí é só usar o ZenoReduce novamente!

def mod(x, n):
  return zeno.zenoreduce(
    lambda x,y: x-n if x>=n else x, 
    xrange(x), x)

Agora nós reduzimos o O(mod) para O(subtração), e podemos continuar até bater em alguma operação que seja O(1) para qualquer entrada!

(Leitores atentos podem achar que usar um ZenoReduce dentro de outro é trapaça, mas não é. Sempre que você consegue achar um limite superior para o tamanho de todas as listas envolvidas, você também consegue reescrever os ZenoReduces encadeados como um único ZenoReduce rodando sobre o produto cartesiano das listas. Provar isso fica como exercício para o leitor atento.)

Quão poderosas são as máquinas de Zeno? Certamente mais que as máquinas de Turing! Na verdade, para elas é facinho provar que P=NP. Vamos fazer isso mostrando uma solução em O(1) para o problema do Subset Sum: dado uma lista qualquer de inteiros, queremos saber se existe um subconjunto dela cuja soma seja zero (esse problema é NP-completo).

Uma estratégia seria gerar uma lista com todos os subconjuntos possíveis, e testar cada um deles em um ZenoReduce. Mas isso não é muito bom porque você precisaria armazenar os 2ⁿ subconjuntos, ocupando assim espaço exponencial.

Ao invés disso, nós podemos simplesmente contar de 0 até 2ⁿ-1, onde, para cada número, os bits dele indicam se o elemento correspondente deve ser somado ou não. Assim nós podemos iterar pelos subconjuntos sem precisar armazená-los.

Antes de começar, duas funções auxiliares. Em python, o built-in len() é O(1), mas se não fosse poderíamos usar isso aqui:

def list_length(x):
  return zeno.zenoreduce(
    lambda x,y: x+1, x, 0)

Podemos também fazer um função O(1) para potenciação:

def power(n, x):
  return zeno.zenoreduce(
    lambda x,y: x*n, xrange(x), 1)

Dados uma lista e um número, cujos bits representam os elementos da lista a serem somados, podemos fazer essa soma condicional em O(1):

def conditional_sum(elements, n):
  return zeno.zenoreduce(
    lambda x,y: 
      x + (y[1] if (n & power(2, y[0]) > 0) else 0), 
    enumerate(elements), 0)

Por fim, é só testar todos os subconjuntos possíveis, novamente em O(1):

def subset_sum(elements):
  return zeno.zenoreduce(
    lambda x,y: x or (conditional_sum(elements, y) == 0), 
    xrange(1, power(2, list_length(elements))), False)

Vamos testar:

>>> zeno.run(lambda:subset_sum([-7, -3, -2, 5, 8]))
(True, 0.015625, 0.0)
>>> zeno.run(lambda:subset_sum(range(1,15)))
(False, 16.75, 1.89e-09)

Veja como esse algoritmo é horrível na máquina de Turing e quase instantâneo na máquina de Zeno!

Outra coisa que não seria possível nesse universo paralelo é a criptografia RSA. De fato, dá pra fatorar um número em O(1) usando ZenoReduces!

def greatest_factor(value, n):
  return zeno.zenoreduce(
    lambda x,y: 
      max(x, y if value % power(n, y)==0 else x), 
    xrange(value), 0)

def factorize(n):
  return zeno.zenoreduce(
    lambda x,y: (x + [(y, greatest_factor(n, y))]) 
      if is_prime(y) and n%y==0 else x, 
    xrange(2, 1+n), [])

Testando:

>>> zeno.run(lambda:factorize(300))
([(2, 2), (3, 1), (5, 2)], 12.65625, 1.77e-15)

Nesse universo paralelo onde facilmente se prova que P=NP e fatoração é O(1), certamente a computação seria bem diferente! Mas o que você me diria se eu te falasse que podemos fazer algo parecido aqui no nosso universo mesmo?

Imagine que você tem algum cálculo qualquer que demoraria um milhão de anos pra rodar, mas que numa máquina de Zeno demoraria apenas um dia. Você pode fazer esse cálculo usando uma máquina de Turing também, e o truque não é nenhuma magia: é relatividade!

Basta deixar seu computador executando o cálculo, e pegar uma nave espacial que viaje a uma velocidade próxima da luz (qualquer coisa mais veloz que 0.999999999999999997c serve). Para você, vai passar apenas um dia, mas para o computador que ficou na Terra, vai passar um milhão de anos, graças ao efeito de dilatação do tempo. Fica como exercício para o leitor fazer uma nave tão rápida, e garantir que o computador ainda vai estar lá funcionando depois de um milhão de anos :)

Bônus: Ricbit Jam #2

Nós vimos como usar o ZenoReduce para testar primalidade, resolver o subset sum e fatorar um número em O(1). Você consegue fazer algo semelhante para ordenar uma lista? Se você topa o desafio, é só participar do Ricbit Jam #2:

Regras do Ricbit Jam #2

Dessa vez o Ricbit Jam vai dar um prêmio para o primeiro colocado: um Cubo de Rubik oficial do Google!

Participe para ganhar!