Siempre habíamos sospechado que el tío del pelo canoso, largo y grasiento miraba las soluciones a la prueba de las letras en el ordenador, pero ¿cómo es el programa que busca todos los anagramas de los subconjuntos de las letras dadas?
Pues ayer
* me dio por programarlo y es una gilipollez. La parte más complicada es obtener el lemario, que manda cojones que para el inglés, que no tiene ningún organismo normativo, sea extremadamente fácil encontrar una
lista muy completa de palabras inglesas y para el español lo más parecido que hay sea el
COES que, sin ánimo de ofender a sus autores (según me dijo uno de ellos pringaron como unos campeones sin recibir ninguna ayuda de la RAE), es bastante deficiente.
Volviendo al asunto principal, aquí os dejo el programilla en Python que no es muy eficiente en memoria (para un fichero con 109230 palabras, de 1.2MB, la imagen del proceso son 36MB), pero que una vez cargado (el archivo de 1.2MB tarda unos 9 segundos en
mi ordenador nuevo) las consultas son prácticamente instantáneas (¡olé mi rigurosidad midiendo tiempos! la verdad es que estoy bastante hasta los huevos de hacer experimentos cambiando parámetros y luego sacar gráficas, así que si yo digo que son instantáneas, es que lo son xD).
import time
import sys
alpha_chars = filter(lambda x: x.isalpha(), map(chr, range(256)))
"""
quita los elementos con multiplicidad cero de la lista l, cuyos
elementos son tuplas del tipo (n, k)
"""
def remove_zeros(l): return filter(lambda x: x[0] > 0, l)
"""
l es una lista de tuplas del tipo (n, k) donde n es el numero de veces
que aparece el elemento k
"""
def subsets(l):
if l:
(n, k), t = l[0], l[1:]
for i in range(n+1):
for j in subsets(t):
yield remove_zeros( [(i,k)] + j )
else:
yield []
"""
ordena las combinaciones, de menor a mayor numero de elementos
"""
def sort_subsets(cl):
def put_size(nkl): return sum(map(lambda x: x[0], nkl)), nkl
keylist = map(put_size, cl)
keylist.sort()
return map(lambda x: x[1], keylist)
"""
devuelve el string s como una lista de tuplas (n, k), siendo k las
letras por orden alfabetico y n el numero de veces que aparecen
"""
def normalize(s):
s = s.lower()
return remove_zeros(map(lambda x: (s.count(x), x), alpha_chars))
"""
crea un diccionario inverso, con las claves las palabras normalizada y
los valores una lista de las palabras validas
"""
def make_dict(f):
d = {}
for i in f:
i = i.strip()
norm = str(normalize(i)) #la clave no puede ser una lista
if norm not in d:
d[norm] = []
d[norm].append(i)
return d
"""
devuelve todos los anagramas y subanagramas de la palabra s que haya en el diccionaro d
"""
def get_anagrams(d, s):
sssns = sort_subsets(subsets(normalize(s)))
def getif(x):
if x in d:
return d[x]
else:
return []
return filter(None, reduce(lambda x, y: x+y, map(lambda x: getif(str(x)), sssns), []))
"""
El primer argumento es el nombre del fichero con la lista de palabras, despues lee las letras por la entrada estandar
"""
def main():
fdict= file(sys.argv[1])
t1 = time.time()
print "making dictionary..."
d = make_dict(fdict)
print "ready!"
t2 = time.time()
print "took", t2-t1, "seconds"
dict_stats(d)
print ">>" ,
line = sys.stdin.readline()
while line:
print ", ".join(get_anagrams(d, line.strip()))
print ">>",
line = sys.stdin.readline()
main()
Pues eso, regocijaos con la elegancia y el poder de Python. ¡Te alabamos, oh, Guido Van Rossum!
De todos modos, el tema del rendimiento al construir el diccionario me tenía algo preocupado, no lucía nada... así que me puse a optimizar. Primera opción: meter el optimizador JIT para Python
Pysco. En teoría es la repolla, para código algorítmico tienes incrementos del rendimiento de hasta un 100x, aunque lo normal está en torno a 4x. Pues ĺa primera decepción es que no funciona para AMD64 (si es que todavía no estámos preparados :-s). Después lo probé en el ordenador de mi despacho y me llevé la segunda decepción: iba más lento. Bastante más lento.
Había que optimizar a mano, así que me lancé a por la tercera opción: paralelizar con threads. Estos son los cambios que introduje (el resto igual):
import threading
def split_seq(seq, size):
newseq = []
splitsize = 1.0/size*len(seq)
for i in range(size):
newseq.append(seq[int(round(i*splitsize)):int(round((i+1)*splitsize))])
return newseq
def merge_dicts(dlist):
d = {}
for i in dlist:
for k in i:
if k not in d:
d[k] = []
d[k] += i[k]
return d
def get_nprocs():
count = 0
try:
lines = file("/proc/cpuinfo").readlines() #solo funciona en unixes
except:
lines = []
for i in lines:
if "processor" in i:
count += 1
return count
class ParallelMakeDict (threading.Thread):
def __init__(self, lines):
threading.Thread.__init__(self)
self.lines = lines
def run(self):
self.d = make_dict(lines)
"""
El primer argumento es el nombre del fichero con la lista de palabras, despues lee las letras
por la entrada estandar
"""
def main():
fdict= file(sys.argv[1])
nthreads= get_nprocs()
t1 = time.time()
print "making dictionary..."
lines = fdict.readlines()
print "words loaded"
print "splitting list and creating threads"
threadlist = map(ParallelMakeDict, split_seq(lines, nthreads))
print "threads created"
for i in threadlist:
i.start()
print "thread running"
for i in threadlist:
i.join()
print "thread joined"
print "merging"
d = merge_dicts(map(lambda x: x.d, threadlist))
print "ready!"
t2 = time.time()
print "took", t2-t1, "seconds"
print ">>" ,
line = sys.stdin.readline()
while line:
print ", ".join(get_anagrams(d, line.strip()))
print ">>",
line = sys.stdin.readline()
main()
¿Mejoraba el rendimiento? Qué va, también iba más lento que la versión secuencial... le eché un vistazo al monitor del sistema mientras construía el diccionario y las barritas iban alternando el 100% de ocupación entre un procesador y el otro, pero nunca se ponían al 100% los dos a la vez. Algo me decía que los threads de Python tenían un problemilla... hice alguna búsqueda y efectivamente, no van muy bien para paralelizar cómputo por cuestiones de cómo están programados los cerrojos del intérprete, así que su mayor utilidad es para hacer servidores que puedan despachar multiples peticiones mientras otras esperan a la E/S en sistemas monoprocesador.
Ya sí que estaba a punto mosquearme... la siguiente opción era buscar algo más serio, como MPI, pero por suerte encontré exactamente lo que estaba buscando, una librería muy "pythónica" para hacer computación paralela con memoria compartida y clusters:
Parallel Python.
Le eché un vistazo al tutorial y en seguida tenía la nueva versión, que consistía en introducir los siguientes cambios (sobre la de threads, quitando la clase del thread):
import pp
"""
def normalize_no_globals(s, chars):
s = s.lower()
return remove_zeros(map(lambda x: (s.count(x), x), chars))
def make_dict_no_globals(f, chars):
d = {}
for i in f:
i = i.strip()
norm = str(normalize_no_globals(i, chars)) #la clave no puede ser una lista
if norm not in d:
d[norm] = []
d[norm].append(i)
return d
def main():
fdict= file(sys.argv[1])
nthreads= get_nprocs()
t1 = time.time()
print "making dictionary..."
lines = fdict.readlines()
print "words loaded"
print "splitting list and creating threads"
job_server = pp.Server()
fdeps = (normalize_no_globals, remove_zeros)
jobs = [job_server.submit(make_dict_no_globals, (x, alpha_chars),fdeps,tuple()) for x in split_seq(lines, nthreads)]
print "threads created"
d = merge_dicts(map(lambda x: x(), jobs))
print "ready!"
t2 = time.time()
print "took", t2-t1, "seconds"
print ">>" ,
line = sys.stdin.readline()
while line:
print ", ".join(get_anagrams(d, line.strip()))
print ">>",
line = sys.stdin.readline()
main()
¡Ahora sí que se notaba el speedup! El diccionario que antes tardaba unos 9 segundos en construirse ahora tardaba sólo 6, un 33% de aceleración, no estaba mal. La verdad es que me he quedado con las ganas de probarlo en los dos nodos con 16 cores cada uno que tenemos en la Universidad, pero es que el Parallel Python no tiene opción de instalar en local para un único usuario y no me apetecía molestar al administrador y ni ponerme a instalar yo los módulos a mano...
Mientras investigaba con la versión paralela, me dio por reimplementarlo en Java a ver si iba más rapidillo o más lento. Después de escribir 4 o 5 clases (una para las tuplas caracter-número de veces que aparece; otra para las palabras normalizadas, un par más anónimas para los Iterator de subconjuntos, otra para el Main...) me di cuenta de una cosa: Java se ha vuelto para mí un coñazo insoportable.
Así que tras la frustración inicial de intentar portar el elegante y conciso código en Python al tedioso y aburrido Java, decidí hacer un poco de gimnasia mental y pasarlo a un lenguaje del que ya había hablado en los comentarios del post sobre
lenguajes para listos y lenguajes para tontos:
OCaml.
He intentado mantener el estilo puramente funcional en todo lo que me ha sido posible (excepto en la tabla del diccionario y en la entrada/salida, claro) y la verdad es que se me escapa alguna sonrisita al recordar a mi profesor Paradigmas de Programación diciendo que la programación funcional es la hostia de legible (sobre todo en LISP :-p), como Joyce, no te jode xD. Tampoco quiero desmerecer, creo que
programar este tipo de algoritmos es mucho más fácil en un lenguaje con características funcionales que en uno totalmente imperativo; y también es más fácil verificar formalmente que hace lo que se supone que tiene que hacer, pero si no sabes de antemano qué es, resulta bastante complicadillo hacer ingeniería inversa sobre el código. Yo ahora mismo sería incapaz de descifrar qué hacen algunas funciones que escribí ayer si no fuese porque he puesto comentarios.
El código resultante tras una tarde y un ratillo de una noche estrujándome un poco las neuronas (traducir de un lenguaje a otro no siempre es tan directo como nos gustaría, echadle un vistazo las 3 funciones necesarias para generar los subconjuntos), el código resultante en OCaml es este:
(* de una lista de tuplas (c,n) quita las que tienen n = 0 *)
let remove_zeros l =
let f x =
match x with
_, 0 -> false
|_,_ -> true
in
List.filter f l
(* devuelve una lista que contiene listas formadas a partir de la
concatenacion de todos los elementos de la primera lista con la segunda *)
let cat_lh_l a b =
let rec priv_cat_lh_l acc rest_a =
match rest_a with
[] -> acc
| h::t -> priv_cat_lh_l ((h::b)::acc) t
in
priv_cat_lh_l [] a
(* devuelve una lista que contiene las listas formadas a partir de la
concatenacion de todos los elementos de la primera lista con todas las
listas contenidas en la segunda*)
let cat_lh_llh a b =
let rec priv_cat_lh_llh acc rest_b =
match rest_b with
[] -> acc
| h::t -> priv_cat_lh_llh ((cat_lh_l a h)@acc) t
in
priv_cat_lh_llh [] b
(* genera todo el rango de tuplas (c,n) con multiplicidad de c desde n hasta 0 *)
let make_range (c, n) =
let rec priv_make_range acc m =
match m with
-1 -> acc
| _ -> priv_make_range ((c,m)::acc) (m - 1)
in
priv_make_range [] n
(* devuelve true si la lista no esta vacia, false de lo contrario *)
let not_empty x =
match x with
[] -> false
| _ -> true
(* devuelve todos los subconjuntos validos de una lista de tuplas (c, n) *)
let subsets l =
let rec priv_subsets l =
match l with
[] -> [[]]
| h::t -> cat_lh_llh (make_range h) (priv_subsets t)
in
List.filter not_empty (List.map remove_zeros (priv_subsets l))
(* devuelve una lista de letras desde first hasta last *)
let make_charlist first last =
let rec priv_make_charlist l c =
match c with
d when d == first -> (c,0)::l
| _ -> priv_make_charlist ((c,0)::l) (Char.chr ((Char.code c)-1))
in
priv_make_charlist [] last
(* devuelve una nueva lista de tuplas (c,n) en la que las tuplas con c
== k tienen n incrementado en 1 *)
let inc_charlist lcn k =
let f (c, n) =
match c with
d when d == k -> (c, n+1)
| _ -> (c, n)
in
List.map f lcn
let lowletters = make_charlist 'a' 'z'
(* devuelve la forma normalizada, como lista de tuplas (c,n) en minusculas, de un string *)
let normalize s =
let slc = String.lowercase s
in
let rec priv_normalize l i =
match i with
-1 -> l
| _ -> priv_normalize (inc_charlist l slc.[i]) (i-1)
in
remove_zeros (priv_normalize lowletters ((String.length s)-1))
(* devuelve el diccionario construido con las palabras del fichero *)
let make_dict fname =
let dict = Hashtbl.create 262144
in
let cin = open_in fname
in
let freadline _ =
try Some (input_line cin)
with End_of_file -> None
in
let lines = Stream.from freadline
in
let add_entry s =
Hashtbl.add dict (normalize s) s
in
Stream.iter add_entry lines;
close_in cin;
dict
(* devuelve todos los anagramas y subanagramas que hay en el
diccionario para la palabra pasada por parametro*)
let get_anagrams dict word =
let rec priv_get_anagrams acc rest =
match rest with
[] -> acc
| h::t -> priv_get_anagrams (acc @ (Hashtbl.find_all dict h)) t
in
let cmp a b =
(List.length a) - (List.length b)
in
priv_get_anagrams [] (List.sort cmp (subsets (normalize word)))
(* El argumento por parametros es el nombre del fichero de palabras,
luego lee de la entrada estandar *)
let main =
print_endline "making_dictionary";
let dict = make_dict Sys.argv.(1)
in
let rec loop _ =
try
print_string ">>";
print_endline (String.concat ", " (get_anagrams dict (read_line ())));
loop ()
with
End_of_file -> true
in
loop ()
let _ = main
Cosas que me han gustado de OCaml después de este programilla de tamaño pequeño y complejidad media:
- El pattern matching mola, aunque no lo he llegado a explotar al máximo porque en este programa no era necesario (combinarlo con los tipos variantes es ya la leche).
- La inferencia de tipos es como ir a una playa nudista, al principio te sientes incómodo e inseguro, pero luego te das cuenta de que es de lo más natural y te hace sentir más ligero.
- Escribir funciones grandes es bastante feo, así que te fuerza a hacer el código muy modular.
El principal problema que le veo es que he tardado demasiado (el doble que en Python, y eso que tenía el otro como plantilla), pero claro, es normal teniendo en cuenta que es el segundo programa en OCaml que escribo (y el primero fue una gilipollez enorme y encima hace casi un año). La sensación de ser un pez fuera del agua tampoco me la he conseguido quitar del todo, todavía no me siento suficientemente suelto con OCaml y siento que hay algo perverso en él que está esperando para joderme en cuanto decida usarlo para algún proyecto mediano-grande. Este artículo confirma en parte mis miedos:
OCaml Sucks.
Bueno, vamos al tema del rendimiento, que era al fin y al cabo por lo que me puse a transcribir el código de Python a OCaml (que dicen que es casi tan rápido como C bien escrito).
Primero lo probé con el intérprete y el compilador a bytecode (ocamlc) y cargando el diccionario de siempre (de 1.2MB) tardaba lo mismo que Python, unos 9 segundos. Pues vaya mierda de optimización para tanto curro.
Después me acordé de que hay un compilador optimizador que genera código nativo (ocamlopt), así que me decidí a probarlo. Resultado: tarda en cargar el diccionario cerca de 1 segundo. Ahora sí, ni Python en paralelo ni pollas.
Pero como con todo, recibí una de cal y otra de arena; en el tiempo de consulta la situación se invierte. En las palabras cortas es despreciable tanto en Python como en OCaml, pero cuando crece la longitud, se nota mucho que el programa en Python usa generadores perezosos y que el que está escrito en OCaml está construyendo y aplanando un árbol en memoria. Para la palabra "
ljegogjfglafsdshak" el programa en Python tarda unos 2 segundos en mostrar todos los anagramas y subanamgramas y el de OCaml tarda la friolera de unos 35 segundos (seguro que también se puede usar evaluación perezosa en OCaml y que los tiempos se igualarían, pero ya me parecía que tardaría demasiado mirándolo).
Conclusión: yo qué sé, si había empezado antesdeayer hablando del
melenas de Cifras y Letras y he terminado con 4 versiones del mismo programa. Bueno, voy a intentar decir algo coherente. Lo más interesante ha sido poner a prueba un par de lenguajes que desde el punto de vista de diseño y funcionamento son bastante antagónicos (tipado estático vs tipado dinámico, interpretado vs compilado), pero ambos son de muy alto nivel (gestión automática de memoria, multiparadigma).
El resultado en ambos ha sido que el tiempo de desarrollo ha sido rápido (más en Python por mi trasfondo pythonero), tanto que ahora mismo no me veo capaz de aguantar el coñazo que supondría hacerlo en un lenguaje que no tuviese como tipos
built-in listas, diccionarios, funciones de orden superior y gestión automática de memoria. Otros posibles candidatos para implentar un código parecido serían Erlang (creo que este programa se podría traducir literalmente desde OCaml), Lisp o a lo mejor Ruby, si es que un día consigo quitarme la aversión que siento hacia él.
En cuanto al rendimiento, está contenido dentro de unos límites prácticos, si bien el programa en OCaml era mucho más rápido inicialmente, no escala demasiado bien para consultas grandes, lo cuál nos lleva a una máxima que muchos "entendidillos" se empeñan en ignorar (esos que dicen que ciertos
lenguajes son lentos y que hay que programar siempre en C y C++): lo que importa es la idoneidad del algoritmo y de las estructuras de datos utilizadas. Utilizar un "lenguaje eficiente" normalmente lo que hace es enmascarar ineficiencias en el diseño (p.e. "como tardo demasiado en programar una tabla hash, pues me hago un array de estructuras clave-valor y busco secuencialmente, que total, como C es muy rápido, no pasa nada.").
¿Quién se anima a hacer su versión en algún otro lenguaje? Si alguien tiene huevos a hacerlo en Java, C o similar, que me diga cuántas líneas le ha ocupado (con un estilo normal, sin hacer el marrullero) y cuánto tiempo le ha llevado programarlo. Probablemente más que todas las versiones que he hecho yo aquí.
Los freaks de Perl estoy seguro de que pueden hacerlo en una sola línea.
*Ese ayer se refiere al día antes de empezar a escribir el post, no de cuando lo he publicado.
y esto 
ahora llego yo y les hago creer que en España vivimos en los árboles. De todos modos, al final el chaval no consiguió atrapar a la ardilla.
