viernes, 10 de febrero de 2012

TDSL continuacion

Habiamos quedado en una bonita implementación [1]. Bonita, veloz pero muy demandante.

leet(Word)->
  lists:foldl(
    fun (Elem, List) ->
    [ string:concat(X,E) || X <- List, E <-Elem ] end,
    hd(preleet(Word)), tl(preleet(Word) )). 



Con las siguientes palabras, comienza con un parpadeo, pasa a un segundo, cuatro segundos y continua con un thrashing  infernal que paraliza la máquina.

22> transform:leet("abcdefghijk").
ok
23> transform:leet("abcdefghijkl").
ok
24> transform:leet("abcdefghijklm").
ok
25> transform:printLeet("abcdefghijklmn").


Según comprendo, leet/1 está recorriendo por nivel [2], produciendo un crecimiento inaceptable del stack de llamadas. Lo correcto sería hacer preorder. Asi que tras un momento de fuerte concentración, gracias a haber dejado que el conocimiento decante y haber traducido la versión de php a ruby, olvidate de TDD, salió esto.

explode(Word) ->
  explode("","",preleet(Word)).

explode(Char,Buffer,[]) ->
  io:format("~s~n",[lists:reverse(Char ++Buffer)]);
explode(Char,Buffer,[H|T]) ->
  [explode(X,Char ++ Buffer, T) || X <- H].


Esto es bastante más lento con las palabras cortas, pero sigue funcionando con palabras largas. El problema es el siguiente:


transform:printExplode("abcdefghijklmn"). 45 segundos 105 MB

./generate.rb abcdefghijklmn: 2 segundos, poca memoria

./generate.php abcdefghijklmn: 2 segundos, poca memoria


Ya descarté lists:foldl y ahora sigue quitar la list comprehension y usar binary.

[1] http://seguridad-agile.blogspot.com/2012/01/tdsl-segunda-semana.html
[2] http://rosettacode.org/wiki/Tree_traversal

No hay comentarios:

Publicar un comentario