Exemplo de thread reaproveitando nossa árvore binária

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.

Vamos construir nosso programa, então. Repassando, dois componentes nossos são usados aqui: a árvore e o gerador de palavras. Criaremos um terceiro, que é uma classe filha de threading.Thread.

O gerador de palavras não é nada sofisticado – assim como os outros componentes aqui. Simplesmente ele gera seqüências de letras que alternam entre vogais e consoantes – uma vogal, uma consoante, uma vogal, etc. Se a consoante for um ‘q’, adiciona-se a ela um ‘u’ e adicionamos mais uma vogal.

gerapalavra.py:

#! /usr/bin/env python
import random
rand=random.random

consoantes='bcdfghjlmnpqrstvxz'
vogais='aeiou'

def pegaletra(tipo):
    if tipo==0:
        return consoantes[int(rand()*len(consoantes))]
    if tipo==1:
        return vogais[int(rand()*len(vogais))]

def gerapalavra():
    tamanho =int(rand()*4+3)
    atual=int(rand()*2)
    palavra=''
    for letr in range(tamanho+1):
        letra=pegaletra(atual)
        if letra=='q':
            letra='qu'
        palavra=palavra + letra
        if atual==0:
            atual=1
        else:
            atual=0
    return palavra

Usamos neste código a função random() do módulo random. Essa função gera um número aleatório entre 0 e 1.

A classe arvbin, que vimos num artigo anterior, foi ligeiramente modificada aqui, por capricho meu. Como estava já serviria o nosso propósito.

arvore.py

#! /usr/bin/env python
# -.- encoding: utf-8 -.-

class arvbin:
contanode=0
def __init__(self, Valor):
self.Menor=None
self.Maior=None
self.conta=1
self.valor=Valor
arvbin.contanode+=1

def add(self,valor):
if valor>self.valor:
self.addmaior(valor)
elif valorself.valor:
if self.Maior:
return self.Maior.busca(valor)
else :
return None
elif valorarvbin.ordena() não será usado pelo nosso programa.

Vamos finalmente à thread :

#! /usr/bin/env python
# -.- encoding: utf-8 -.-

import threading
import arvore
import gerapalavra
class minhathread(threading.Thread):
def __init__(self, arv):
threading.Thread.__init__(self)
self.arv=arv
self.quantos=1

def set_quantos(self, quantos):
self.quantos=quantos

def run(self):
n=0
while nNossa classe, class minhathread, herda de threading.Thread. Sobrescrevemos os métodos __init__ (o construtor da classe) e run, que é onde as coisas acontecem; incluímos dois atributos que são arv (um apontador para a raiz da nossa arvore binaria) e quantos; e adicionamos um método set_quantos. O atributo quantos determina quantas palavras aleatórias serão geradas; o método set_quantos modifica ou atribui um valor a quantos.

Quanto ao loop no método run(), cabe um comentário aqui: na minha infinita ignorância, sempre usei “for x in range(n)” para fazer um loop com n iterações. Não me ocorria que range(n) retorna uma lista com n elementos. Como nós queremos aqui fazer muitas e muitas iterações, a lista gerada num loop “for x in range(n)” iria ocupar muita memória e não teria utilidade nenhuma no nosso código.

Por fim, após if __name__ == '__main__': :

  • linha 24: criamos nossa árvore;
  • linhas 26,27 e 28 : iniciamos a thread, informamos que queremos 6500000 palavras e damos o ‘start’ na thread;
  • a partir da linha 29: um loop infinito entra para que possamos fazer pesquisa de palavras na árvore.

Se você for testar o programa, use na pesquisa palavras com quatro ou mais letras e que alternem vogais e consoantes. O gerador de palavras aleatórias gera palavras como as abaixo:

  • ezecavi
    imepu
    ofum
    bumequot
    udasaru
    avune
    mevepaf
    azicaqu
    camo
    mesito
    cuvolo
    equimef
    abafah
    razan
    umerec
    cegexe
    ejadoquu

Executando o programa com as 6500000 previstas, em pouco tempo começam a aparecer palavras existentes no nosso dicionário, como bola, faca, pedal,

Como ficou a execução do código aqui:

digite uma palavra: poder
nao achou em 227178
digite uma palavra: falar
nao achou em 238439
digite uma palavra: fazer
nao achou em 246752
digite uma palavra: ficar
ficar  ,  1 ocorrências
254725 nós na arvore
digite uma palavra: bola
bola  ,  4 ocorrências
266515 nós na arvore
digite uma palavra: tapete
nao achou em 309667
digite uma palavra:

Você deve ter reparado que não há nenhum modo de encerrar a execução do programa. Você pode esperar pelo fim da execução, implementar um modo de interromper a comando ou matar o processo usando os meios para isso do seu sistema operacional.

Anúncios

Uma resposta to “Exemplo de thread reaproveitando nossa árvore binária”

  1. Danilo Cabello Says:

    Muito interessante, gostei da implementação, a idéia é que já dê pra pesquisar na árvore mesmo com ela gerando/indexando as palavras, correto?

    Uma dica no uso que você fez do random, eu usario random.choice, a gente vem de outras linguagens e acaba naturalmente pensando complicado, com choice ficaria:

    def pegaletra(tipo):
    if tipo==0:
    return random.choice(consoantes)
    if tipo==1:
    return random.choice(vogais)

    O artigo está muito bom, abraço!

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: