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!
Tags: complexidade · exercícios · mungeword · otimização · programação · python · regular expressions
