À pala desta discussão no P@P, fui relembrado, dos confins da memória, desta estrutura: trie. Isto é daquelas coisas que se aprende em Algoritmos e Estruturas de Dados e depois, se não se trabalhar especificamente em motores de busca, gestão documental ou coisa que o valha, nunca mais se vai usar. E assim se perde nos interstícios da memória uma excelente estrutura.

O problema em causa - que não é exactamente o motivo pelo qual me reinteressei pelas tries, mas isso fica para outro dia - era a criação dum sistema que "sugira soluções para palavras cruzadas ou problemas equivalentes". Um dos primeiros passos é, como é lógico, criar um dicionário de palavras passível de ser pesquisado. A Universidade do Minho tem disponível um ficheiro de texto com quase 700.000 palavras (link inválido, neste momento), só faltava mesmo carregá-las e usá-las.

As primeiras respostas a esse tópico foram precisamente no sentido das tries, mas a minha primeira reacção foi trocar a dificuldade de implementação e debugging por uma certa penalidade em tempo de execução na pesquisa, usando um simples array com as palavras e pesquisa binária. Força do hábito.

Depois de levar nas beiças de alguns membros, cá fiz uns testes; acontece que "certa penalidade na pesquisa" era bem mais do que eu tinha previsto ao início - cerca de 9 vezes mais lento, e nem sequer estava a contemplar pesquisas parciais (e também não vai ser nesta posta que me debruçarei sobre isso). Seja então uma trie.

Quando em ambiente web, são várias as soluções para persistência de dados em bases de dados relacionais: desde os mais famosos MySQL, PostgreSQL, SQL Server até verdadeiros monstros poderosíssimos, como Oracle. Mas quando nos viramos para aplicações desktop, já não é bem assim.

Há várias soluções: o supra citado SQL Server, ficheiros MDB do Access… Mas todas têm certos requisitos no sistema onde correm; no mínimo dos mínimos, precisarão da biblioteca de acesso correspondente. Mesmo neste último caso, que já não é mau (SQL Server, por exemplo, requer mesmo a instalação do dito na máquina onde corre – uma versão lite, é certo, mas tem que se instalar), a biblioteca atinge, normalmente, vários  MB.

Na sequência deste post, várias pessoas1 chamaram-me a atenção de algo básico: faltava o valor das apostas na estrutura. Básico, básico, básico.

Podia ter cedido ao caminho mais fácil: apenas uma entidade, com o preço das apostas simples, devidamente localizado. Depois, calculava o valor das apostas múltiplas desdobrando cada múltipla nas suas componentes simples. Mas, quanto mais pensava no assunto, menos correcta me parecia a abordagem. Já ouvi falar de concursos – e não sei se é verdade – em que há vários tipos de apostas simples. Por exemplo, um concurso com três jogos, em que as pessoas escolhem (imaginemos) cinco números de um pote e um número de apenas um dos outros dois potes; há aqui duas apostas simples distintas: cinco do pote A mais um do pote B e cinco do pote A mais um do pote C. Outra razão que me surgiu depois, esta de ordem bem mais prática, seria o acesso directo, sem cálculos, aos preços das múltiplas, com o bónus de poder controlar que apostas são válidas, entre simples e múltiplas, para um dado concurso.

Como tal, o diagrama entidade-associação foi modificado e colocado no respectivo projecto da categoria Jogos de Loto. A imagem que acompanhava o post precedente a este foi retirada, para não existirem confusões e passa a estar só no projecto, que é bem melhor de gerir.

1 a razão pela qual as pessoas – pelo menos, estas quatro – preferem mandar um e-mail ao invés de comentar aqui no blog é algo que me ultrapassa…

Comentários Nenhum comentário Continuar a ler Continuar a ler »

Modelo de processo de desenvolvimento RAD (Rapid Application Development), fase 2: Modelagem dos Dados. É isto que nos ensinam na escola, desde o primeiro momento. E é isto que tantas vezes esquecemos no nosso dia-a-dia de programadores. Not this time.

Quando comecei a desenvolver aplicações para jogos de loto, estas eram extremamente restritivas, apenas para o Euromilhões ou apenas para o Totoloto… Qualquer outro concurso obrigaria a uma reestruturação do código e a uma nova release do software, exclusiva para esse concurso. Como é bom de ver, isso é um bocadinho estúpido – a menos que se tenha em mente uma estratégia de venda ou de branding: continua a ser estúpido dum ponto de vista de desenvolvimento, mas é uma excelente ideia a nível de marketing, sempre são mais produtos para vender. Como não é o meu caso, esqueçam: é só estúpido.

O código, passo a passo, foi sendo melhorado para ser escalável, como deveria ter sido desde o início. O mesmo foi acontecendo à estrutura de dados, abstraindo cada vez mais a mesma duma visão centrada num dado concurso, primeiro, e nos concursos portugueses, depois. Se do Euromilhões para o Totoloto, por exemplo, já há diferenças de estruturação (o Euromilhões é, na realidade, constituído por dois jogos, por exemplo), para totolotarias de outros países havia diferenças abismais. Por exemplo, há uma totolotaria nos Estados Unidos cuja última bola sorteada tem um significado especial e deve ser tratada como um jogo à parte, à semelhança das estrelas no nosso conhecido Euromilhões. Mas há um catch: essa bola é do mesmo pote de onde saíram as outras (cinco ou seis… ou sete, não sei bem). E isto, ainda a procissão vai no adro…

Como já falei aqui, o Wordpress não é a peça central do DreamsInCode. Isso, na altura, levantou alguns problemas de integração. Resolvidos que foram, não me preocupei mais.

À pala da brincadeira com os endereços “humanos” (aqui e aqui), que são usados nos projectos aqui no DreamsInCode, andei a monitorizar-lhes o comportamento no sitemap via Google Webmaster Tools. Qual não é a minha surpresa ao verificar que todas as páginas eram reportadas como 404 Not Found, excepto as do blog. Como é que era possível, se eu via as páginas perfeitamente, em vários browsers e em várias ligações. Olhando para o painel Net do Firebug, certinho, direitinho: lá estava o 404 a olhar para mim, em conjunto com todos os dados da página. WTF?!

No seguimento deste post, relembro o exemplo que dei do jornal Público: http://www.publico.clix.pt/Sociedade/divulgacao-de-escutas-na-internet-punivel-pela-lei-do-cibercrime_1419063. Acho que é claro para todos que não existe, no site do jornal Público, nenhum directório “Sociedade” e muito menos um directório para cada notícia que eles colocam.

Na realidade, o que acontece é um redireccionamento invisível do pedido para um script central que, neste caso, trata das notícias. Esse redireccionamento é feito com a extensão mod_rewrite do Apache. O mod_rewrite é uma espécie de pau para toda a obra dos redireccionamentos, desde visíveis a invisíveis, com inúmeras aplicações.

Já devem ter reparado, em centenas de sites por essa ‘Net fora – aqui no DreamsInCode, por exemplo – em endereços cujo caminho é semelhante ao título da página; nalguns casos, inclui mesmo categorias. O caso em que me baseei foi o do site do jornal Público, por ter exactamente a característica que eu queria, e que o WordPress não tem. Se repararem neste URL, por exemplo, http://www.publico.clix.pt/Sociedade/divulgacao-de-escutas-na-internet-punivel-pela-lei-do-cibercrime_1419063, verificam que os caracteres acentuados constam do mesmo, o que não acontece com o WordPress, por exemplo.

Posto isto, o problema tem duas fases: converter os títulos ou os nomes dos registos para uma versão compatível com URL’s e depois redireccionar os novos URL’s para os scripts correspondentes ao tratamento do pedido. No entanto, converter os títulos, que parecia tarefa simples, foi, na verdade, bastante complicado; para isso contribuiu a codificação dos registos na base de dados, que está em UTF-8 (e se não tiverem em UTF-8, deviam ter).

Quem der uma vista de olhos por código meu, em especial em situações onde é necessária alta velocidade de execução – como no caso dos Jogos de Loto – encontrará, várias vezes, duas instruções que dão imenso jeito, unsafe e fixed.

A instrução unsafe é a mais simples e serve para marcar uma zona de código como não segura. Isto serve imensos propósitos, em particular o nosso amigo fixed.

Mas antes de irmos à explicação do fixed, é preciso explicar porque é que precisamos dele quando a velocidade de execução é fundamental.

As linguagens .NET são linguagens de compilação JIT (Just In Time), o que quer dizer que o código em que são feitas (C#, VB.NET, F#, etc.) são assembladas para um formato intermédio (CIL – Common Intermediate Language), que forma os executáveis e librarias normais (exe e dll). Ao serem executadas, o compilador JIT – inserido na máquina virtual, que é a framework .NET, de instalação obrigatória – transforma esse formato intermédio na linguagem máquina mais apropriada para o ambiente (sistema operativo, especificações de hardware) em que está a correr.

A máquina virtual .NET (e, na realidade, todas as máquinas virtuais, desde o Java até ao Flash Player) têm também um mecanismo chamado garbage colection (GC) (recolha de lixo, na tradução literal). O GC foi uma excelente ideia, quando apareceu pela primeira vez em 1959 (John McCarthy): retira das mãos do programador a responsabilidade de eliminar objectos, variáveis e ponteiros que já não estão em uso. Quem vem dum background em C ou C++ conhece bem o sintoma de se usar um ponteiro para uma área de memória vazia ou com dados inválidos (normalmente, segmentation fault e respectivo core dump; na pior das hipóteses, crash do sistema). Hoje em dia, já começa a ser difícil encontrar linguagens sem GC (com a honrosa excepção do C++ não-.NET) o que é, em quase todas as circunstâncias, óptimo!

Para além das funções discutidas aqui e aqui, a classe estática CombTools ainda contém mais algumas funções para manipular combinações ou conjuntos de combinações. Relembro, mais uma vez, que a classe é estática (assim como todos os seus métodos).

Os métodos são os seguintes:

Este post é uma reedição de um post meu no euromilhoes.com.

Em primeiro lugar, o que é o CSN? O CSN é o Número Sequencial Combinatório (Combinatorial Sequence Number) de uma dada combinação, quando estas se encontram ordenadas lexicograficamente, isto é, tendo como exemplo C(50,5), da [1, 2, 3, 4, 5] até à [46, 47, 48, 49, 50]. Neste caso, os CSN’s seriam o 1 e o 2.118.760.

Uma forma de calcular os CSN’s, e vice-versa, seria simplesmente construir todo o desdobramento até ao CSN pretendido, ou até à chave pretendida. Don’t. É estúpido, é um desperdício de ciclos de processamento e é péssima programação. Sobretudo, se já alguém pensou no assunto e se os algoritmos são do domínio público. Mesmo que não saibam, pesquisem antes de cometer uma barbaridade deste tamanho.

Vamos então aos ditos…

 Categorias
 Arquivo
 Projectos em Destaque
 Últimas Postas no Blog
 Últimos Comentários do Blog