Arquivo de python

Funções com cache usando decorators

Posted in Scripts with tags , , on 15/04/2011 by felipessilveira

Opa. Muuuito tempo que não posto nada. Vou tentar postar mais coisas, juro =]

Estava discutindo esses dias com uns amigos sobre gerar sequência de
fibonnaci recursivamente e como programação dinâmica ajudaria a
diminuir a complexidade do programa.

Foi aí que veio a grande ideia: Fazer algo em python pra criar uma
cache de uma dada função.

Usei algumas coisas que aprendi nesse post do Guido e implementei uma cache pra uma função qualquer.

A ideia básica é a seguinte:
Quando a função é chamada, é necessário checar se ela já foi chamada anteriormente, se já foi chamada, basta simplesmente pegar o resultado guardado e retornar.
Se a função não foi chamada ainda, chamamos ela e guardamos em um mapeamento da forma (argumentos) -> retorno.

A primeira versão tinha uma cache de tamanho infinito (o que não é inviável pra coisas práticas). Depois resolvi implementar uma cache com tamanho finito (definido pela variável “size”) e política de substituição LRU. Para a implementação do LRU, devido à natureza desordenada do map, foi necessário adicionar uma lista pra manter a contagem de referências.

Quase esqueci de postar o código. dã.

Vocês podem encontrar ele no meu perfil do github.

Uma possível aplicação prática disso, pode ser implementar cache pra buscas em bancos de dados. Pra evitar fazer pesquisa em disco e também evitar deixar tudo em memória.

Bom, acho que é isso. Caso alguém tiver alguma dúvida, posta aí nos
comentários ou manda um email, ou qualquer coisa parecida =]

Análise de algoritmos cache conscientes

Posted in Scripts with tags , , , , on 28/11/2010 by felipessilveira

Há um tempo apresentei um seminário sobre algoritmos cache-conscientes, o meu objetivo era comparar algoritmos tradicionais e suas versões cache-conscientes.

A primeira coisa que decidi pra comparar os algoritmos foi os dados sobre misses em cache (dã), e me indicaram o valgrind. Com ele eu pude verificar os resultados dos algoritmos.

Mas a idéia do seminário era mostrar que existiam algoritmos assintoticamente melhores, logo seria necessário rodar várias vezes os algoritmos. E o pior ainda seria necessário comparar mais de um campo da saída do valgrind. Qual foi a solução pra essa tarefa chata, repetitiva e fácil? Um script! =D

O que eu fiz foi o seguinte:
Um script pra compilar e rodar os algoritmos com o tamanho especificado e salvar os dados em um arquivo. (Em shell)
Um script pra parsear o arquivo e transformar isso em dados trabalhavéis e gerar tabelas. (Em Python)
Plotar as tabelas geradas com o script python pra gerar gráficos (porque nenhum trabalho é válido se não tiver gráficos =]).

Todos os scripts e o código dos algoritmos vocês podem encontrar no meu svn.

PS: Se alguém quiser executar os testes, gostaria de informar que demora. Devido à compilação sem otimizações e com debug, e executar com o valgrind, a multiplicação de uma matriz 1024×1024 levou mais de meia hora =/

Script buscador dos 1001 discos para ouvir antes de morrer

Posted in Scripts with tags , , on 21/11/2010 by felipessilveira

Há um tempo, um amigo me mostrou o site http://nobrasil.org/1001-discos-para-ouvir-antes-de-morrer, e perguntou se eu conseguia pegar os links pra ele.

Então eu fiz um script em python pra pegar os links =D

Basicamente, o script pega por expressões regulares os links para a página de download de cada disco e depois pega o link de download de cada página
Só que essa abordagem é um pouco ruim porque a maior parte do tempo é perdida nas requisições de download da página, logo, surgiu a idéia de fazer com várias threads.

O que eu fiz foi passar um parâmetro pro script dizendo quantos links cada thread vai pegar, e disparo 1001/X threads pra pegar os links.
Na minha internet de 1MB eu consigo sobrecarregar a rede deixando cada thread responsável por 10 links

Se alguém se interessar e quiser os links: basta rodar o script do seguindo modo:

python downloader.py X | sort

O “| sort” só está ali pra deixar a saída em ordem cresce, porque cada thread pode acabar em um tempo diferente e eu fiquei com preguiça de fazer isso dentro do script =/

No script, eu usei as bibliotecas nativas do python: urllib e re

Download do script: downloader.py (tá comentado =])
Lembrando, não esqueça de mudar a extensão pra .py, o wordpress não me deixa colocar arquivos com extensões de verdade =/

Era isso. Até =]

Ps: Se alguém tiver alguma dúvida, posta aí =]