Arquivo para arvore binaria

Exemplo de thread reaproveitando nossa árvore binária

Posted in Linux, Programação, Python with tags , , on 12 / julho / 2008 by medeubranco

No artigo sobre threads eu não coloquei nenhum exemplo “prático” de utilização de threads, então vou colocar aqui, misturando conteúdo dos artigos anteriores.

No artigo sobre árvores binárias, nossa classe era uma árvore binária que guardava palavras de um arquivo de texto, com um contador para a quantidade de ocorrências de cada palavra. O programa de teste para essa classe jogava o conteúdo de um arquivo na árvore, e depois de a ter carregado, mostrava todas as palavras em ordem alfabética. Vamos usar esta classe no nosso exemplo de thread.

Como eu queria montar uma árvore tão grande quanto possível, em vez de arrumar arquivos grandes para deles extrair palavras, resolvi fazer um gerador de palavras aleatórias. Vamos usar ele também.

A idéia: fazer um loop com um número muito grande de iterações. A cada iteração, uma palavra aleatória é criada e é adicionada à árvore. A classe da arvore tem um método para busca de palavras, arvbin.busca(), e ele será usado pelo nosso programa exemplo numa interface interativa. O usuário digita uma palavra e o programa diz se existe a palavra na árvore e a quantidade de ocorrências desta palavra.

O esquema do programa:

  • passo 1 – gerar muitas palavras aleatórias, adicionando-as à árvore;
  • passo 2 – apresentar um prompt para pesquisa de palavras na árvore.

Um problema se apresenta aqui: quantas palavras nós vamos gerar, e quanto tempo vai levar até que todas as palavras tenham sido geradas e a árvore esteja completa? Como o código é seqüencial, iniciamos o passo 1 e só após a sua conclusão é que entraremos no passo 2. A não ser que pudéssemos executar os dois ao mesmo tempo. É aí que entra a thread.

Continue lendo

Anúncios

Brincando de arvore binária com Python

Posted in Programação, Python with tags , , on 5 / julho / 2008 by medeubranco

De repente me deu vontade de fazer uma árvore binária em python. Não sei por que, nem para quê, mas deu vontade.

Usei um exemplo que creio ter visto no livro “C A linguagem de Programação” de Brian Kernighan e Dennis Ritchie : contagem de palavras em um texto.

O livro fala de árvores binárias como alternativa, neste problema de contagens de palavras, à pesquisa binária. Numa pesquisa binária, pressupomos que a lista de valores está previamente ordenada. Isso não deve ocorrer com as palavras de um texto qualquer. Não sabemos nem mesmo a quantidade de palavras que podem estar contidas nesse texto, de modo que pode não ser muito eficiente rodar previamente um algoritmo de ordenação. A salvação então é a tal árvore binária.

No meu código abaixo, criei uma classe (arvbin) para representar os nós da árvore. Os atributos da classe são: a palavra, o contador de ocorrências da palavra, um apontador para a palavra menor e outro para a maior:

class arvbin:
    def __init__(self, Valor):
        self.Menor=None  #apontador para a palavra menor
        self.Maior=None  #apontador para a palavra maior
        self.conta=1     #conttador de ocorrências
        self.valor=Valor #a palavra

Continue lendo