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 valor<self.valor:
            self.addmenor(valor)
        else:
            self.conta=self.conta+1

    def addmenor(self,valor):
        if self.Menor:
            self.Menor.add(valor)
        else:
            self.Menor=arvbin(valor)

    def addmaior(self,valor):
        if self.Maior:
            self.Maior.add(valor)
        else:
            self.Maior=arvbin(valor)

    def busca(self,valor):
        if valor>self.valor:
            if self.Maior:
                return self.Maior.busca(valor)
            else :
                return None
        elif valor<self.valor:
            if self.Menor:
                return self.Menor.busca(valor)
            else :
                return None
        else:
            return self

    def ordena(self, perna=1 ):
        listamenor=[]
        listamaior=[]
        if self.Menor:
            listamenor=self.Menor.ordena(perna+1 )
        if self.Maior:
            listamaior=self.Maior.ordena(perna+1 )
        return listamenor + [ (self.valor, self.conta, perna) ] + listamaior

O método arvbin.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 n<self.quantos:
            self.arv.add(gerapalavra.gerapalavra())
            n+=1
        print 'terminei'

if __name__ == '__main__':
    arv=arvore.arvbin(gerapalavra.gerapalavra())

    thr=minhathread(arv)
    thr.set_quantos(6500000)
    thr.start()
    while 1:
        nome=raw_input( 'digite uma palavra: ' )
        result = arv.busca(nome)
        if result:
            print result.valor  + '  ,  ' +  str(result.conta)  + ' ocorrências'
            print str(arv.contanode) +  ' nós na arvore'
        else:
            print 'nao achou em ' + str(arv.contanode)

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