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

Apesar de estar morrendo de cansaço, não consigo dormir. Já li, já escutei música, já fiquei no escuro. Nada. Então resolvi vir para o computador, esperar o sono chegar e enquanto navegava por aí, encontrei este post, do Walter Cruz, falando sobre o exercício Text Munger, postado aqui.

Primeiro, resolvi fazer uma solução “simples”, sem muita sofisticação, lendo os dados de um arquivo de texto para uma unicode string e correndo dois ponteiros sobre esta, indicando o início e o final de cada palavra - basta então chamar a função que “bagunça” os caracteres entre os dois ponteiros.

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

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
  return result

A segunda idéia é praticamente igual a primeira, mas, ao invés de utilizar dois índices, vou utilizar o método pop das listas para ler os caracteres.

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

def MungeFile(all_data):
  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)
  return result

A terceira e a quarta idéias já utilizam regular-expressions - como o Walter queria. No entanto, vale ressaltar um detalhe: \w, em Python, considera números e underscores como sendo partes válidas de uma palavra, o que não era desejado no exercício. No entanto, como o próprio Matthew Moss escreveu, muitos escolhem usar \w então consideraremos estas soluções aceitáveis.

A terceira implementação utiliza o conceito de split ou, quebra, da string em diversos elementos de uma lista, de acordo com a expressão regular separadora.

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

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))
  return result

Já a quarta implementação utiliza o método sub das expressões regulares em Python, para executar uma função de substituição sobre cada uma das ocorrências da expressão em si.

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

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

Vamos comparar então. Primeiro com um texto pequeno, 1KB:

         226 function calls in 0.003 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.003    0.003 /home/rodolpho/text_munger.py:19(MungeFile)

         225 function calls in 0.004 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    0.004    0.004 /home/rodolpho/text_munger2.py:19(MungeFile)

         424 function calls (418 primitive calls) in 0.003 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.003    0.003 /home/rodolpho/text_munger3.py:20(MungeFile)

         272 function calls (270 primitive calls) in 0.003 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.003    0.003 /home/rodolpho/text_munger4.py:19(MungeFile)

Aparentemente, com arquivos pequenos, a diferença em tempo de execução é mínima entre as implementações. Vamos agora jogar um arquivo maior: 3,9MB.

         1389493 function calls in 10.116 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    3.990    3.990   10.116   10.116 /home/rodolpho/text_munger.py:19(MungeFile)

         1389492 function calls in 15296.867 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1 15269.408 15269.408 15296.867 15296.867 /home/rodolpho/text_munger2.py:19(MungeFile)

         2157415 function calls (2157409 primitive calls) in 1301.620 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1 1282.561 1282.561 1301.620 1301.620 /home/rodolpho/text_munger3.py:18(MungeFile)

         1389538 function calls (1389536 primitive calls) in 8.105 CPU seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    1.530    1.530    8.105    8.105 /home/rodolpho/text_munger4.py:19(MungeFile)

Opa! Agora sim vários resultados interessantes. De cara vemos que solução de usar substitution com expressões regulares apresentou os melhores resultados (oito segundos e pouco, para quase 4MB de texto é um bom resultado). Além disso, vemos que a primeira solução (com os índices) também não ficou tão atrás assim.

A surpresa vem com a segunda idéia: certa de 15297 segundos??? Sim, demorou mais de 4 horas para executar na minha máquina e parece ser uma implementação tão simples, senão mais, que a primeira. Nem tudo que parece simples, é.

A terceira idéia apresentou um resultado tão bom quanto a primeira, o que é uma certa surpresa - eu esperava ver os resultados com regular expressions serem bem melhores do que os demais.

Eu preciso correr para uma consulta médica que tenho e não posso explicar agora os motivos de tais resultados. Prometo que escreverei um post ainda mais longo sobre isso, com gráficos e tudo mais, estudando tanto a função MungeWord como a MungeFile. (Para quem tem muita pressa, uma dica).

Beijos e Abraços! Bom dia!