:root…blog:

Nos dias 6 e 7 de setembro (sábado e domingo) ocorrerá o DjangoCon (primeira conferência internacional sobre Django) na sede do Google em Mountain View, Califórnia. Corremos atrás e assistiremos no escritório do Google em São Paulo uma transmissão ao vivo da conferência.

As vagas são limitadas e as inscrições serão abertas amanhã, às 12h00, através do site www.djangocon.org/register/.

Vejo vocês lá!

Depois que analisamos a função MungeWord e chegamos à conclusão que todas as implementações apresentadas possuem desempenhos similares, voltamos nossa atenção para a função MungeFile, pois a diferença na performance geral do programa deve ser consequência dela.

Lembramos que as quatro implementações que sugeri foram:

A primeira - que utiliza índices e slices:

def MungeFile(all_data):
  result = []
  index = 0
  while index < len(all_data):
    while index < len(all_data) and not all_data[index].isalpha():
      result.append(all_data[index])
      index += 1
    end = index + 1
    while end < len(all_data) and all_data[end].isalpha():
      end += 1
    result.append(MungeWord(all_data[index:end]))
    index = end
  final = "".join(result)
  return final

A segunda - que utiliza pop:

all_data = list(all_data)
  result = []
  if len(all_data) <= 2:
    return result
  char = all_data.pop(0)
  while all_data:
    word = []
    while all_data and char.isalpha():
      word.append(char)
      char = all_data.pop(0)
    result.append(MungeWord(''.join(word)))
    while all_data and not char.isalpha():
      result.append(char)
      char = all_data.pop(0)
  final = "".join(result)
  return final

A terceira, que quebra o texto em palavras, utilizando expressão regular:

def MungeFile(all_data):
  regex = re.compile(r"(\W+)", re.UNICODE)
  words = regex.split(all_data)
  result = []
  while words:
    word = words.pop(0)
    result.append(MungeWord(word))
  final = "".join(result)
  return final

A quarta, que realiza uma função de substituição sobre os acertos de uma expressão regular:

def MungeFile(all_data):
  regex = re.compile(r"\w+", re.UNICODE)
  all_data = regex.sub(MungeWord, all_data)
  final = "".join(all_data)
  return final

E, além dessas, temos a implementação que o Walter desenvolveu e postou aqui. A principal diferença é que a solução dele utiliza o módulo shlex:

def munge(text):
  t = shlex.shlex(text, posix=False)
  t.quotes = "'"
  t.whitespace = ""
  s = (munge_word(word) for word in t)
  final = "".join(s)
  return final

Para testar as cinco funções, gerei dinamicamente um texto com quantidade de palavras variando de 1 a 5000. Cada palavra possui 9 letras.

Para textos com menos de 1300 palavras, os cinco algoritmos apresentaram tempo de execução inferior a 0,1 segundo. A partir daí, no entanto, já se nota que a segunda implementação apresenta um aumento razoável em relação às demais.

Abaixo está um gráfico dos resultados - infelizmente não consegui inserir a legenda na própria imagem, mas é:

• Azul: primeira solução
• Verde: segunda solução
• Vermelho: terceira solução
• Amarelo: quarta solução
• Azul claro: quinta solução (do Walter)

Não é difícil entender o porque do aumento maior da segunda implementação: enquanto as três últimas trabalham com a separação e tratamento de palavras, a segunda varre a entrada letra por letra, similar a primeira, mas utiliza pop na primeira posição de uma lista. Está aí a lição :P pop funciona muito bem para os últimos elementos de uma lista, mas quanto mais nos aproximamos do início, pior o desempenho.

Vamos verificar isso. Vou alterar a segunda implementação para o seguinte:

def MungeFile(all_data):
  all_data = list(all_data)
  all_data.reverse()
  result = []
  if len(all_data) <= 2:
    return result
  char = all_data.pop()
  while all_data:
    word = []
    while all_data and char.isalpha():
      word.append(char)
      char = all_data.pop()
    result.append(MungeWord(''.join(word)))
    while all_data and not char.isalpha():
      result.append(char)
      char = all_data.pop()
  final = "".join(result)
  return final

Notem que eu simplesmente inverti a ordem dos elementos da lista e utilizei pop nos últimos elementos (que eram os primeiros). Veja o resultado agora:

Impressionante! Saber como os métodos e as estruturas de dados funcionam, bem como os módulos disponíveis, é de extrema importância quando otimizando algoritmos. A simples inversão de uma lista representou ganhos de 89,5%, nos casos de textos com 5000 palavras.

O melhor método ainda parece ser utilizar substituição em caso de match por expressão regular. Durante meus testes encontrei um “fenômeno” interessante que ocorre com o shlex ao processar textos muito longos (>100M). Ainda estou investigando as causas e postarei os resultados em breve :)

Beijos e abraços!

ps: lembrando que as soluções que utilizam expressões regulares não são completamente válidas para o problema (estamos embaralhando pontuação e números, o que não seria aceito).

Primeiro vamos analisar então a função MungeWord que mencionamos no post anterior. Há diversas formas de implementar o que queremos (a primeira e última letras da palavra devem ficar intactas, mas as demais ser embaralhadas) e vou analisar os dois dos modos que testei e uma mistura de ambos. Utilizando índices e slices:

def MungeWord(word):
  if not word or not word[0].isalpha() or len(word) <= 2:
    return word
  middle = list(word[1:-1])
  random.shuffle(middle)
  return ''.join((word[0], ''.join(middle), word[-1]))

Utilizando pop:

def MungeWord(word):
  if len(word) <= 2:
    return word
  word = list(word)
  first = word.pop(0)
  last = word.pop()
  random.shuffle(word)
  return ''.join((first, ''.join(word), last))

E uma mistura de pop e slices:

def MungeWord(word):
  if len(word) <= 2:
    return word
  first = word[0]
  word = list(word)
  last = word.pop()
  middle = word[1:]
  random.shuffle(middle)
  return ''.join((first, ''.join(middle), last))

Comparando a performance das três funções para tamanhos reais de palavras (menos de 100 letras, por exemplo), a diferença entre elas fica em menos de 0,00001 segundo. Então não há motivos “reais” para dar preferência por uma específica - escolha a mais legível, se quiser; eu, pessoalmente, prefiro pop (a segunda implementação).

Mas por que parar por aí? Vamos levar ao extremo, considerando a existência de palavras com milhares de letras. Um gráfico para mostrar o resultado:

Bom, fica claro que, independente do gosto por uma ou outra implementação, o tempo de execução não é afetado, mesmo com palavras gigantes.

Depois retornarei ao assunto para tratar do consumo de memória e da MungeFile também. :)

Beijos e abraços!