:root…blog:

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!

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!