A ver a categoria “C#”

Categoria sobre a linguagem de programação C#. Truques e dicas, snippets úteis, resmungos. Minha linguagem de formação e aquela onde ataco os problemas mais interessantes.

Finalmente tive algum tempo para concluir a implementação básica das tries, na sua variante em caracteres. As duas funções que faltavam implementar foram relativamente simples – a eliminação, que eu contava que me desse alguns solavancos durante o percurso, acabou por ser trivial e demorei mais tempo a testar do que a implementar; nem queria acreditar que tivesse ficado a funcionar à primeira…

Tanto o método de contagem como de eliminação são alterações do método de listagem, pelo que conseguirão navegar pelo novo código facilmente. Foram feitas algumas correcções ao nível do coding style, para respeitar o upper camel case, habitual em C#.

Os ficheiros mais recentes estão, como é habitual, na página do projecto.

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

Para finalizar a primeira fase desta minha incursão pelas tries, vamos agora colocá-la a fazer alguma coisa de útil. Convenhamos que verificar se uma palavra existe ou não é trabalho fraquinho, tendo em consideração as potencialidades desta estrutura de dados. E uma dessas potencialidades é precisamente construir listagens a partir de verificações parciais. Estas podem servir para auto-completar palavras (como nos telemóveis, motores de busca) e para sistemas de correcção ortográfica, com listas de palavras semelhantes a palavras erradas, isto é, não constantes da lista. A implementação específica deste tipo de sistema está fora do âmbito desta posta, visto que não é trabalho específico da trie; esta, apenas devolve uma lista de palavras partindo de uma incompleta, usando wildcards1.

Começando pelo caso do wildcard ‘?’, correspondente a um caracter naquela posição, uma aproximação naïve seria iterar por todas as letras do alfabeto, incluindo as acentuadas, colocá-las na posição correcta e verificar a existência das palavras resultantes na trie. Salta à vista a inocência deste processo: em primeiro lugar, iterar por todos os caracteres possíveis para a posição incluiria muito mais do que os 26 normais do alfabeto – só em caracteres com diacríticos, seria bem mais do dobro; em segundo lugar, a ocorrência de palavras que obviamente não existem, com quatro consoantes seguidas, por exemplo; em terceiro e último lugar, quando quiséssemos implementar a pesquisa com o wildcard ‘*’, representando vários caracteres, os nossos problemas aumentariam exponencialmente.

Ao reler esta minha posta de ontem, lembrei-me das embedded resources, que costumam ser usadas para a localização de aplicações, mas que nada impede que sejam usadas para transportar o que quer que seja. Embeber um ficheiro de texto seria trivial, e as vantagens seriam potencialmente animadoras – ao arrancar a aplicação, a framework carrega muito mais depressa as resources junto com o executável do que o StreamReader consegue ler um ficheiro externo.

Embeber um ficheiro no Visual Studio é do mais simples que há: no menu de contexto do projecto, escolher a opção Properties, depois a aba Resources. Se não existirem resources, clicar no link que estará bem visível no meio da página, e escolher Add New Text File do dropdown Add Resource.

Visual Studio 2008 - Resources

À 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.

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:

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