:root…blog:

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