maio 30th, 2006 by elm
Numa aula eu estava explicando a técnica de programação “Divisão e Conquista”, que consiste em dividir um problema grande em pequenos subproblemas e resolvê-los separadamente de forma que o resultado deles seja o resultado do problema original. Um exemplo de algoritmo desenvolvido nessa técnica é o de busca binária, onde o espaço de busca é sempre dividido pela metade, diminuindo o tempo de pesquisa. Para ilustrar a diferença desenvolvi dois scripts em Python para mostrar o tempo de execução de um algoritmo de pesquisa usando “força bruta” e a pesquisa binária. Para isso usei o módulo timeit do Python. Com este módulo é possível medir o tempo de execução de pequenos trechos de código. Abaixo os códigos usados:
Pesquisa por Força Bruta
Pesquisa Binária (Divisão e Conquista)
Comparação dos tempos de execução
Como neste caso são poucos dados a serem pesquisados a diferença de tempo não é tão grande, mas é visível o suficiente para ilustrar aos alunos a diferença.
maio 23rd, 2006 by elm
O site PortableApps fornece uma lista de aplicativos que podem ser usados direto de um dispositivo portátil como um pendrive. Montei um kit de primeiros socorros para windows
no meu pendrive de 128mb:
Xampp Lite – com o apache, php5, mysql, phpmyadmin, etc. O básico para testar e desenvolver para web – 104MB
Portable Firefox – navegador – 17MB
Portable FileZilla – cliente de ftp – 3.4MB
putty – cliente de ssh – 400K
pscp – cliente de cópia segura – 200K
Ainda me sobrou uns 3MB para armezenar alguns logs do apache e alguns arquivos pequenos. Com um pendrive maior dá para instalar outras coisas legais como o Portable OpenOffice ou algumas distros Linux.
maio 19th, 2006 by elm
No site da Oracle encontrei esse artigo sobre como usar o Python em conjunto com o Oracle.
Um trecho legal, que resume bem o Python:
“[..] não é apenas fácil de usar, mas também facil de usar bem, produzindo códigos legíveis e bem organizados. Assim, quando você retornar a um pedaço de código meses depois de ter escrito, você poderá endendê-lo, modificá-lo e e reusá-lo. A elegância e limpeza da sintaxe de Python é chamada algumas vezes de “pseudo-código executável”, por sua aparência próxima da auto-documentação. Ele é altamente orientado a objetos e torna fácil aprender e seguir um bom estilo de programação, mesmo para aqueles entre nós sem treinamento formal de engenharia de software. Sua curva de aprendizagem leve torna-o interessante tanto para novatos quanto para experts. “
maio 17th, 2006 by elm
Um dos conteúdos que estou trabalhando na disciplina de Algoritmos e Estruturas de Dados III é Padrões Algoritmicos.
Dentre estes padrões existem os chamados “Algoritmos de Força Bruta (brute force algorithms)” e os “Algoritmos Gulosos (greedy algorithms)”.
Segundo [1], “um algoritmo de força bruta resolve um problema da maneira mais simples, direta e óbvia. Como resultado esse algoritmo terminar realizando muito mais trabalho para resolver um certo problema do que um algoritmo mais sofisticado. Por outro lado, um algoritmo de força bruta é em geral mais fácil de implementar do que um outro mais sofisticado e, por causa da sua simplicidade, às vezes ele é mais eficiente.”
O mesmo autor sugere um exemplo de problema a ser resolvido usando essa abordagem, o problema da Contagem de Dinheiro. “Considere o problema que um caixa de banco resolve sempre que ele ou ela precisa dar ao cliente uma certa quantidade de dinheiro. O caixa tem à sua disposição um conjunto de várias notas e moedas de valores diferentes e precisa contar uma certa quantia usando o menor número possível de peças.”
Um algoritmo usando a abordagem de força bruta iria testar todas as combinações possíveis até encontrar a melhor combinação. Fiz um código em Python para ilustrar esse algoritmo:
forca_bruta.py
Executando o script:
bash-3.00$ python forca_bruta.py
Digite o valor a encontrar
20
Solucoes encontradas
Solucao [1, 1, 1, 1, 1, 15]
Solucao [10, 10]
A melhor solucao eh
[10, 10]
O algoritmo encontrou duas soluções e sugeriu como a melhor a que usou menos moedas. Nesta abordagem ele testa todas as possibilidades até encontrar a melhor.
Já com a abordadem de algoritmos gulosos uma lógica mais sofisticada é utilizada. O caixa de um banco não iria testar todas as possibilidades até encontrar a melhor. Ele iria pegar as moedas com maior valor primeiro e iria encontrar uma solução para o problema. A idéia dos algoritmos gulosos é encontrar uma resposta não sabendo se é a melhor delas, mas torcendo para que seja. O algoritmo abaixo resolve o mesmo problema usando esta abordagem:
guloso.py
Sua execução retorna o seguinte:
bash-3.00$ python guloso.py
Digite o valor a encontrar
20
Solucao
[15, 1, 1, 1, 1, 1]
Ele mostra a primeira solução que encontrou. É mais rápido do que o força bruta e é uma solução correta, mas não é a melhor solução, que neste caso seria [10,10].
Mais um exemplo de python com ferramenta didática.
[1] http://www.brpreiss.com/books/opus7/
maio 12th, 2006 by elm
Mais uma aplicação Web2.0 interessante. O site last.fm permite que você ouça as músicas que gosta, participe de comunidades das bandas, compartilhe seus gostos musicais com outros usuários, coloque tags nas músicas, etc.
A nova versão do banshee que vem com o Dapper possui um plugin que permite que as músicas que você ouve usando o player sejam listadas na sua lista de músicas preferidas.
Outra feature legal é a possibilidade de exportar via rss as músicas ou artistas que você mais ouve. Coloquei na barra ao lado a lista das últimas 10 músicas que estou ouvindo via rss.
maio 12th, 2006 by elm
Em uma das disciplinas que ministro, Algotimos e Estruturas de Dados III, consta o conteúdo de Teoria de Conjuntos aplicada em computação e Estruturas de Dados para Conjuntos. A primeira é a aplicação das teorias matemáticas de conjuntos nas linguagens de programação. O livro que utilizo [1] traz exemplos em Pascal. Pesquisando um pouco na internet encontrei exemplos em Python:
conj.py
A outra matéria trata sobre conjuntos disjuntos [2]. Segundo [3] “algumas aplicações envolvem o agrupamento de n elementos distintos em uma coleção de conjuntos disjuntos. Duas operações importantes são encontrar o conjunto a que pertence um dado elemento e unir dois conjuntos.” Em C é possível desenvolver estas estruturas de dados utilizando listas ou usando árvores. O código da versão em C usando listas é
conjuntos_disjuntos.c
Além disso, fiz uma pesquisa na internet para encontrar uma implementação em Python. Encontrei a classe Grouper [4]. Um exemplo do uso da classe é:
distset.py
Uma das aplicações dos conjuntos disjuntos é a determinação dos componentes conectados em um grafo não orientado.
A implementação deste algoritmo usando C e listas é:
connected_components.c
E a implementação usando Python:
connected_components.py
[1] http://www.temporeal.com.br/produtos.php?id=169855
[2] http://en.wikipedia.org/wiki/Disjoint-set_data_structure
[3] http://www.livrariasaraiva.com.br/produto/produto.dll/detalhe?pro_id=466688&ID=C8F434217D5051E1012260358
[4] http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/387776
maio 11th, 2006 by elm
Nas últimas semanas fiz uma pesquisa para encontrar um framework PHP que eu pudesse usar em meus aplicativos/sites. Encontrei vários frameworks interessantes como:
- Symphony
- Prado
- Code Igniter
- Zend Framework
Depois de ver vários deles uma pergunta me ocorreu: “realmente preciso de um framework?”. Realmente utilizar um destes frameworks auxilia bastante o desenvolvimento, evitando que você refaça coisas que já existem. Mas muitas vezes estes frameworks possuem alguns problemas:
- são muito maiores do que você precisa;
- a documentação é confusa;
- poucos estão suficientemente maduros;
- é preciso aprender uma nova sintaxe ou maneira de se desenvolver;
- você fica “engessado”, é difícil fazer coisas mais avançadas ou que saem do padrão CRUD;
Então pensei que o que eu preciso é somente uma maneira de separar a lógica da apresentação, uma maneira de facilitar o acesso a bancos de dados e algo que me ajude a trabalhar com AJAX. Assim, peguei algumas idéias que vi nas documentações que li e algumas coisas que já utilizava e uni tudo para suprir minhas necessidades.
Modelo de aplicação
MVC Architecture?
Segundo Rasmus Lerdorf, criador da linguagem PHP, “MVC é palavra do momento em arquiteturas de aplicação web. Ela vem do design de aplicações para desktop orientadas a eventos e não se aplica muito bem no design de aplicações web. Mas felizmente ninguém sabe exatamente o que MVC significa, então você pode chamar seu mecanismo de separação de camada de apresentação de MVC e seguir em frente.”
Então, o que estou usando aqui é somente um mecanismo de separar o layout (html+css) do código PHP. Ao invés de usar as três camadas do MVC eu resumi para duas, Visão e Controle.
A parte da visão é representada por templates. Seguindo outra tendência que percebi em outros frameworks a parte de visão é representada por simples scripts PHP ao invés de utilizar uma das ferramentas de Templates como Fast Template, Smarty, etc. É mais simples de trabalhar e não é necessário aprender uma nova sintaxe.
Para a parte do controle eu desenvolvi uma classe chamada app. Nesta classe eu controlo as ações do usuário. Ela age como o controlador das aplicações testando qual ação o usuário escolheu e invocando o método correto (que deverá ser reescrito nas suas subclasses, as novas aplicações). A idéia é que cada aplicação seja uma subclasse da classe app.
Este é o código da classe app:
Classe app
Outra classe desenvolvida é a classe tabela. Esta classe é responsável por abstrair e facilitar a manipulação de tabelas de bancos de dados. Seu código fonte é descrito abaixo.
Classe tabela
Exemplo de aplicação
Para ilustrar o funcionamento eu criei uma pequena aplicação com as classes. A aplicação é um sistema de blog, com posts e comentários.
A estrutura de diretórios ficou assim:
classes/ – diretório com as classes
classes/app.php – classe app
classes/tabela.php – classe tabela para tratamento de tabelas no banco de dados
classes/adodb – classes adodb para abstração de bancos de dados. necessário para a classe tabela.
classes/JSON.php – para utilizar JSON, usado por algumas páginas que usam AJAX
blog/ – diretório da aplicação
blog/index.php – subclasse da classe app
blog/view/ – diretório com as visões
blog/view/index_view.php – visão inicial
blog/view/login_view.php – visão da página de login
blog/view/comentario_view.php – visão dos comentários
blog/view/admin_view.php – visão da página de administração
blog/view/estilo.css – arquivo com as definições de CSS para as visões
blog.sql – arquivo sql com os comandos para criar as tabelas da aplicação
A primeira tarefa é criar a base de dados e as tabelas que serão utilizadas no exemplo. Para isso foram executados os seguintes comandos sql (gravados no arquivo blog.sql):
create database blog;
use blog;
create table post (id_post int primary key auto_increment, tit_post varchar(255), ds_post text, dt_post date);
create table comentario(id_com int primary key auto_increment,ds_com text, email_com varchar(100), id_post int);
A base de dados usada neste exemplo é o MySQL.
O código do arquivo index.php do diretório blog deve ser uma subclasse da classe app. O código inicial ficou desta forma:
index.php – inicial
O primeiro método a ser escrito é o método index(). Este método é o método inicial da aplicação. O construtor da classe app sempre vai invocar este método caso não tenha sido escolhida outra opção.
Complementando o código:
index.php – metodo index()
O código do arquivo view/index_view.php é o seguinte:
index_view.php
O método showView da classe app vai transformar cada índice do vetor $dados em uma variável ou
em um novo vetor. Então o script index_view.php vai simplesmente imprimir seus valores.
Uma nova linha deve ser adicionada no final do arquivo index.php :
$blog = new blog(“mysql://root:@localhost/blog”);
Nesta linha é instanciado um novo objeto da classe blog criada. Como parâmetro para o construtor da classe é enviado a string de conexão com a base dados. Esta string é no formato usado pelo ADODB e a sintaxe para diversos bancos de dados podem ser encontradas no site da ferramenta.
Executando-se a aplicação deve-se obter o seguinte resultado:
Todas as definições de cores, fontes e estilos foram adicionadas no arquivo estilo.css utilizando-se as técnicas de CSS. Desta forma, os arquivos de visão não possuem formatações de estilo e sim somente informações dos dados que devem ser gerados. A parte de formatação fica em separado, o que facilitaria caso fosse necessário alterar as definições de layout da aplicação. O código do arquivo estilo.css é o seguinte:
estilo.css
O próximo passo é criar as outras ações da aplicação. Por exemplo, quando o usuário clicar no link comentários ele será direcionado para:
http://localhost/blog/index.php?op=comentarios&id_post=15
Como a variável op controla a ação que o usuário escolheu precisamos definir um novo método na classe blog para atender a esta requisição. Então o seguinte código deve ser adicionado aos métodos da classe blog (arquivo index.php):
index.php – método comentario()
O método comentarios() faz uso da visão comentario_view.php. Seu código é:
comentario_view.php
Assim, quando o usuário clicar no link “Adicionar comentário” na página inicial serão apresentados os comentários existentes e um formulário para adição de um novo comentário, conforme a imagem abaixo ilustra:
Quando o usuário submeter os dados do novo comentário a ação “addComentario” será executada, como indicado pelo input hidden chamado op na linha 26 do comentario_view.php. Para que esta ação seja executada o seguinte código deve ser adicionado no arquivo index.php.
index.php – método addComentario()
Quando o usuário clica no link Admin da página inicial ele é redirecionado para a visão que mostra o formulário de login. O método da classe blog que realiza esta ação é:
index.php – método mostraLogin()
E o código fonte do arquivo login_view.php pode ser visualizado abaixo:
login_view.php
O método login da classe blog é responsável pela validação do usuário e por mostrar a visão de administração. Neste exemplo não é feito nenhuma validação específica, isso é deixado a cargo do leitor, podendo implementar algum método de autenticação que seja pertinente.
index.php – método login()
A visão de administração é a mais complexa de todas. Além de mostrar os posts já cadastrados na tabela ela fornece opções de exclusão e de alteração dos mesmos. Para melhorar a interação com o usuário é usado técnicas de AJAX para buscar os dados do post antes do usuário realizar a alteração.
O código do arquivo admin_view.php é mostrado abaixo, com seus comentários.
admin_view.php
Quando o usuário clica no link “Alterar” uma conexão assíncrona é aberta com o servidor via AJAX solicitando os dados do post. Os dados são codificados no formato JSON. JSON é “um formato leve para troca de informações. É facil para humanos lerem e escreverem. E é fácil para as máquinas processar e gerar.” Uma espécie de XML ligth. É baseado na notação de objetos do JavaScript, o que cai como uma luva para usar com o XMLHttpRequest. A classe blog utiliza o include JSON.php para gerar os dados neste formato. Este script pode ser encontrado no repositório PEAR, no endereço http://pear.php.net/pepr/pepr-proposal-show.php?id=198 e mais informações sobre o JSON podem ser encontrados no http://www.json.org.
Um exemplo da visão de administração é mostrado na figura abaixo:
Abaixo é mostrado o código final da classe blog com todos os métodos comentados acima e os métodos restantes, addPost(), del(), altPost() e buscaPost().
index.php – arquivo final
Tenho usado estas classes em alguns novos projetos que estou desenvolvendo e o ganho de produtividade tem sido interessante. Se ajudar para alguém fica aí minha contribuição.
maio 8th, 2006 by elm
Aderindo a campanha, aí vai a lista de feeds que leio diariamente, no formato OPML
