0votos

Palindromo en F#

por jmgomez hace 3 años

Poco que añadir

Realizar un programa con clases y objetos, donde el usuario ingresara una frase y el programa debera decirle al usuario si es palindromo o no es palindromo, ignorando el hecho de que el usuario ingrese espacios

1
2
3
let isPalindromo (text:string) =  
    let t = text.Replace(" ","").ToCharArray() 
    t |> Array.rev = t 
3 comentarios
0votos

Escrito por Fernando Pelliccioni hace 3 años

Hola jm,

Me gusta que el código es muy breve y fácil de leer, pero...
Salvo que el compilador sea tan inteligente para darse cuenta que solo basta con recorrer la mitad cada uno de los array’s, este algoritmo es ineficiente.
Si revisan el código intermedio generado por el compilador F# se pueden dar cuenta que de hecho no se realiza tal optimización.
En este caso (ya que es .Net), también podría llegar a ser optimizado por el JIT Compiler, pero lo dudo.

Así que en vez de hacer n operaciones, se hacen 2n operaciones.

Además, Array.Reverse es O(n).
Y por último, y quizás lo peor, es que Array.Reverse realiza alocación dinámica de memoria para el nuevo array.

Resumiendo:
Dynamic Allocation
Almacenamiento: O(n)
Tiempo: n asignaciones, 2n comparaciones

Un abrazo,
Fernando.
0votos

Escrito por jmgomez hace 3 años

Hola Fernando,
En general tienes razón. Se puede hacer de forma más eficiente. Aunque la complejidad asintótica sigue siendo O(n).

Algunos puntos de mejora para el algoritmo que expuse serían:
[1]]No asignar t (pierde legilibilidad)
[2]Paralelizar (trivial dada la naturaleza del algoritmo. Con un estilo más imperativo se complicaría más)
[3]Implementar una función específica para el problema en lugar de usar rev + replace.

Si extrapolamos para un problema real, ¿vale la pena? Depende en gran medida del contexto, en el que entre otras cosas está el tiempo del programador. En concreto este algoritmo me costó alrededor de 20 segundos. [1] y [2] dado el bajo coste (tiempo + impacto en la legilibilidad), puede que valga la pena. Para [3] necesitaría una buena excusa ya que el coste (tiempo) puede ser 10 o 20 veces más que utilizar una solución ya implementada (rev).

El problema no me pareció lo suficientemente interesante como para desarrollar una mejor solución.

Saludos,
0votos

Escrito por Fernando Pelliccioni hace 3 años

Hola Jm,

Hago algunos comentarios que, no están totalmente relacionados con tu solución, sino con las soluciones en general.

- Si bien la complejidad simplificada es O(n), es importante mirar todas las variantes que hacen un algoritmo más eficiente que otro.
A veces hay que mirar el detalle y cuestiones como heap-alocation, código cache-friendly, etc, que terminan siendo más importantes todavía.

- Creo que el algoritmo más simple de escribir (while donde se incrementa un extremo y se decrementa el otro) te hubiera llevado 40 segundos (y es eficiente). Considero que escribir un algoritmo en una línea no hace lo hace mejor ni más legible. Solo es "cool" :)

- Sobre si vale la pena dedicarle tiempo a este algoritmo, bueno, como bien decis, depende del contexto, y da para una charla que podría ser eterna. Según yo lo veo, siempre vale la pena, hasta al algoritmo aparentemente más inútil en algún momento se le puede encontrar un fin práctico. Para mi tendríamos que programar buscando la eficiencia, más allá del tiempo insumido en intentarlo. Considero que un algoritmo eficiente se perpetúa en el tiempo. Y esto no solo aplica a algoritmos, también está, por ejemplo, fijate el tiempo que los matemáticos (desde los egipcios y griegos hasta los más modernos) le han dedicado al estudio de los números, sobre todo los números primos. Y... ¿Cuantos usos prácticos de los números primos se pueden contar hasta antes del siglo XX?

Así que, como bien decís, depende del contexto, pero a veces, por más que no conozcamos los usos prácticos de algo, vale la pena hacer el mejor esfuerzo. Deberíamos imitar a los matemáticos.

- Sobre el costo en tiempo de programador, bueno, mi posición es casi totalmente contraria. Creo que muy pocas veces priorizo el tiempo del programador por sobre la eficiencia. Puede que escriba un algoritmo ineficiente, pero no por pensar en hacerlo en poco tiempo, sino, por error, o ignorancia.
Se me viene a la mente un video de Andrei Alexandrescu, de Facebook, donde han llegado a la conclusión que una mejora del 1% en su JIT compiler significa varios años del salario de sus programadores mejor pagados.

http://channel9.msdn.com/Events/GoingNative/2013/Writing-Quick-Code-in-Cpp-Quickly (minuto 3)

- Con respecto a paralelizar el algoritmo, tendría que analizarlo en detalle, pero dudo que paralelizar este algoritmo en particular lo haga más eficiente. Sería interesante hacerlo y comparar los resultados.

- Es respetable que un problema pueda parecer interesante, pero creo que sería bueno, cuando uno plantea una solución, especificar la complejidad, el costo y cuáles fueron las prioridades al desarrollarla (performance, tiempo de programador, legibilidad, etc...).
En caso de que uno opte por una solución menos eficiente a alguna conocida, sería bueno comentarlo, ya que considero que si escribimos una solución ineficiente puede ser por dos razones: ignorancia o por estrategia. Si es por ignorancia, otra persona podría ayudar a que aprendamos. Si es por estrategia, no hay mucho que hacer. Además, otra persona (quizás principiante), que quiere aprender mirando soluciones, podría elegir cual leer y cual no, en base a su forma de pensar.

- Y por último, con respecto a los palíndromos, son muy utilizados en genética.
http://en.wikipedia.org/wiki/Palindromic_sequence

Bueno, eso es todo, algunos pensamientos acerca de cómo creo que es conveniente expresar las soluciones.
Mil disculpas por la extensión del mensaje.

Saludos,
Fernando.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.