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!

O algoritmo mais rápido do oeste

Dia desses um amigo me passou um probleminha bem divertido. O enunciado é simples: dado um vetor ordenado, construa uma binary search tree, balanceada, com os mesmos elementos do vetor. Esse problema tem uma solução trivial em O(n log n) e uma solução esperta em O(n), mas eu acabei achando uma terceira solução, com o algoritmo mais rápido do oeste: ele roda em O(0)!

Vamos revisar as respostas tradicionais antes. A solução trivial é usar uma árvore binária auto-balanceante, como a AVL ou a Red-Black, e inserir os elementos nela, um por um. Como você vai inserir n elementos e o custo de inserção é O(log n), então o total desse algoritmo é O(n log n).

Mas fazendo dessa maneira, você não está usando a informação de que o vetor estava ordenado. Com uma recursão simples você consegue aproveitar esse fato, e construir a árvore em apenas O(n). Um exemplo em python é assim:

def build_tree(vector):
  def partition(start, end):
    if (end < start):
      return None
    middle = start + (end-start) / 2
    return (vector[middle], 
            partition(start, middle-1), 
            partition(middle+1, end))
  return partition(0, len(vector) - 1)

Aparentemente, essa solução é ótima. Se você vai criar uma estrutura de dados nova usando os dados da antiga, o mínimo de trabalho que você precisa é copiar os elementos de uma pra outra, e isso limita em O(n) certo? Quase! Você pode contornar essa limitação se usar uma estrutura de dados implícita, e é isso que vamos tentar fazer.

Para usar o vetor ordenado original como uma estrutura implícita, nós precisamos criar um isomorfismo entre o vetor ordenado e a binary search tree. Se for possivel criar esse isomorfismo, então na verdade eu não preciso fazer nada pra converter o vetor, ele já é equivalente à árvore. E um algoritmo que não faz nada é um algoritmo O(0)! Eu poderia chamar essa estrutura de dados nova de Implicit Balanced Binary Search Tree, mas é muito comprido, então vou chamá-la de Cactus Binário (apropriado, daqui em diante as coisas vão ficar espinhosas).

Mas vamos ao isomorfismo então. Como o vetor está ordenado, então os valores dos elementos em si não importam muito, e nós podemos trabalhar só com os índices, sem perda de generalidade. Além disso, para as demonstrações ficarem mais simples, vamos dividir em dois casos. Digamos que o tamanho do vetor é N, então o primeiro caso que vamos tratar é quando N pode ser escrito como 2^h-1 para algum h>0. Nesse caso, o Cactus Binário é uma árvore perfeita (todas as folhas estão no mesmo nível e todos os nós internos tem dois filhos):

Para criar o isomorfismo, eu preciso fornecer duas funções que, para um dado índice, me retornem o índice do filho à esquerda e do filho à direita. Depois de pensar um pouco, acabei chegando nas funções abaixo:

left(x) = x - (x & (-x)) / 2
right(x) = x + (x & (-x)) / 2

Isso é mágica? Não, é matemática! Para entender porque as expressões funcionam, é só olhar para a árvore anterior usando a visão além do alcance:

Olha só que bacana, quando você olha para os índices da árvore em binário, parece que o nível em que está o índice é igual ao número de zeros no final da representação binária dele. Na verdade, nós podemos provar isso, usando indução na altura da árvore.

Vejamos: para uma árvore de altura unitária, o único elemento é o 1, que está no nível zero e tem 0 bits zero no final, então a base de indução está ok. Se a árvore tem altura h, então ela tem 2^h-1 elementos. O elemento central é o 2^h-1, que tem h-1 zeros no final e está no nível h-1. A sub-árvore da esquerda é uma árvore balanceada de tamanho 2^h-1-1, que funciona pela hipótese de indução. A sub-árvore da direita é igual à da esquerda, se você ligar o bit mais significativo de cada índice. Setar o bit mais à esquerda não muda a quantidade de bits zero à direita, então podemos usar a hipótese de indução novamente, e pronto: QED.

Agora ficou fácil achar a fórmula né? Se você tem um índice x no nivel h, então o filho à esquerda é o maior número com h-1 zeros à direita que seja menor que x, e o análogo vale para o filho à direita. Ou seja, pra descer do nível h para o nível h-1 pela esquerda, basta subtrair 2^h-1  (ou somar, se for pela direita).

E computacionalmente como eu faço isso? Basta achar o bit 1 mais à direita do número, dividir isso por dois e subtrair do número original. Para achar o primeiro bit 1, o truque é calcular x & (-x). Vamos provar: pela definição de complemento de dois, negar é o mesmo que inverter e somar um. Se o número em binário for algo do tipo xxxx10000, negado ele fica yyyy01111, e quando você soma um, o carry propaga até bater no zero, ficando yyyy10000. Quando você faz o AND, os primeiros bits dão zero porque o AND de um bit e seu complemento é sempre zero, e os últimos bits dão zero porque o AND de qualquer bit com zero dá zero. Sobra só o primeiro bit 1 à direita, QED.

Juntando tudo agora as duas fórmulas são evidentes. Mas pra completar o isomorfismo eu ainda preciso de uma fórmula que me indique onde está a raiz da árvore. A fórmula em si é simples: a raiz é a maior potência de dois menor ou igual ao tamanho do vetor, ou seja, basta achar o primeiro bit 1 à esquerda do tamanho.

Para achar o primeiro bit 1 à esquerda não tem nenhum truque tão simples quanto à direita, mas felizmente existe uma alternativa: os processadores x86 possuem um opcode meio desconhecido chamado BSR (bit scan reverse), que retorna exatamente onde está esse bit à esquerda. Em processadores bons, como o Core 2 Duo, o BSR é uma operação O(1), mas isso não é verdade em todos os processadores (por exemplo, não é verdade nos AMDs). Se você não tiver o BSR por hardware, pode fazer uma busca binária nos bits do número, que é uma operação O(log log n).

Isso conclui o primeiro caso. Vamos ver agora o que acontece quando o tamanho é um número qualquer. O pior caso do algoritmo é quando o tamanho é uma potência de dois, e o Cactus Binário fica assim:

Uepa! Essa árvore está balanceada? Bem, depende da sua definição de balanceada. Nessa árvore, o maior caminho entre a raiz e uma folha é 4, o que parece muito. Mas, na verdade, não dá criar uma árvore que tenha um caminho máximo menor. Se o caminho máximo fosse 3, então a árvore poderia ter no máximo 7 elementos, e pelo princípio da casa dos pombos a árvore de tamanho 8 com caminho máximo 3 é impossível. De fato, se você tentar balancear mais a árvore, o melhor que você consegue é algo assim:

Logo, o caminho máximo do Cactus Binário é o mesmo caminho máximo da árvore balanceada. Note, entretanto, que isso é melhor que as árvores auto-balanceantes! O caminho máximo da AVL, no pior caso, é 1.44log(n), e o da Red-Black é 2log(n), ambos maiores que o Cactus Binário.

Com isso, nós provamos o isomorfismo para os dois casos, e o algoritmo O(0) realmente funciona! Mas a grande dúvida agora é: ele serve pra alguma coisa? Na verdade, a grande vantagem da árvore binária é que ela faz inserções em O(log n), enquanto que uma inserção no Cactus Binário é apenas O(n). Por isso, nas aplicações práticas da vida real a árvore binária ganha. Aparentemente, a única utilidade do Cactus Binário é para escrever blog posts :)