Components Programming

☰

Palíndromos y algo más

Jun 06, 2016

Decidí escribir este artículo a partir de una pregunta que vi en Stackoverflow.

Aquí el enlace a la pregunta.

El autor de la pregunta intenta escribir un algoritmo que identifique si una “palabra” es un palíndromo o no lo es. El algoritmo está escrito usando el lenguaje de programación Java.

No me interesa analizar el algoritmo propuesto por el autor, sino que me interesa analizar el algoritmo propuesto en la respuesta más votada. Este último tiene 73 votos contra 65 votos que tiene la respuesta aceptada (a día de la fecha, 6 de Junio de 2016).

Aquí el enlace a la respuesta que me interesa.

Acá el código:

public static boolean isPalindrome(String str) {
    return str.equals(
       new StringBuilder(str)
       .reverse()
       .toString()
    );
}

El algoritmo funciona correctamente y la lógica es muy intuitiva. Básicamente compara por igualdad la palabra original contra el reverso de la palabra.

El problema con este algoritmo es que es muy ineficiente comparado con el algoritmo óptimo.

Hice un comentario al autor de esta respuesta en Stackoverflow: “Compare the complexity of your algorithm with respect to others.”
El usuario @aioobe me respondió: “I think it’s the same complexity as the other solutions, no?”

En parte tiene razón. No fui muy específico en mi comentario. Seguramente @aioobe asumió que yo me refería a la complejidad computacional asintótica y está bien que lo haya asumido de esa forma, ya que usualmente cuando decimos “complejidad” sin especificar nada más, se asume que nos estamos refiriendo a la complejidad computacional asintótica.

Complejidad Computacional Asintótica

Con complejidad computacional asintótica nos referimos a cómo responden los algoritmos en tiempo/espacio a medida que el input crece.
Usualmente está asociada a la O-notation introducida por Paul Bachmann en su libro Die Analytische Zahlentheorie en 1894. [1]

De esta forma podemos medir la escalabilidad de los algoritmos sin depender de la arquitectura de la máquina, de la velocidad del procesador, del lenguaje en el que está implementado el algoritmo, etc…

Si bien es muy útil en muchas circunstancias, el problema de esta forma de medición es que no es exacta, sino que es aproximada.

No quiero aquí extenderme en más detalles sobre O-notation ni complejidad asintótica, para información referirse a [2].

Complejidad Computacional Concreta

Otra forma de medir algoritmos es no usar aproximaciones sino cantidades concretas de operaciones, dependiendo de la entrada al algoritmo.

Por ejemplo, supongamos el algoritmo para encontrar el mínimo (o máximo) de \( n \) elementos. Podemos decir que dicho algoritmo tiene una complejidad (en tiempo) de \( O(n) \) o lineal. Pero específicamente se necesitan \( n - 1 \) comparaciones.

Volviendo a los Palíndromos

Repito el código que queremos analizar:

public static boolean isPalindrome(String str) {
    return str.equals(
       new StringBuilder(str)
       .reverse()
       .toString()
    );
}

Al código anterior lo vamos a denominar Algoritmo I (“I” de ineficiente).

Podríamos decir que Algoritmo I es \( O(n) \), pero, ¿Cómo podemos asegurarlo sin conocer la complejidad de los componentes en los que el algoritmo está basado?

Para ello, debemos revisar la documentación provista por Java. Por ejemplo, veamos la función String.equals(). [3]

Como habrán notado en la página anterior, la documentación de Java no incluye la complejidad en tiempo ni espacio de sus algoritmos y estructuras de datos.
Considero esto una gran falta ya que nos dificulta la especificación de la complejidad de nuestros algoritmos, al menos de los algoritmos que están basados en clases provistas por Java.

Para continuar tratando de especificar la complejidad del Algoritmo I, no nos queda otra que revisar directamente el código fuente de las clases Java.
Veamos el código fuente de String.equals() (presione sobre el link y busque la función equals).

Como ustedes pueden verificar, el código de String.equals() tiene complejidad lineal en tiempo, \( O(n) \).
Específicamente se realizan \( n \) comparaciones por desigualdad. (Más allá de todo el ruido impuesto por Java, como los casts, instanceof, etc…).

La complejidad en espacio de String.equals() es constante, o sea, \( O(1) \).
Esto quiere decir que se utiliza una cantidad de memoria constante más allá del input del algoritmo.

Determinando la complejidad

Vamos a determinar la complejidad del Algoritmo I, analizando uno a uno sus componentes.

String.equals(). Tiempo lineal, \( n \) comparaciones por desigualdad. Espacio constante.

StringBuilder.reverse(). Tiempo lineal, \( 2 \left\lfloor\dfrac{n}{2}\right\rfloor \) asignaciones. Espacio constante.

StringBuilder.toString(). Tiempo lineal, \( n \) asignaciones. Espacio lineal, \( n \) elementos.

StringBuilder constructor. Tiempo lineal, \( n + 16 \) asignaciones. Espacio lineal, \( n + 16 \) elementos.

Entonces, la complejidad total del Algoritmo I es:

Tiempo: En el peor caso, cuando la palabra es un palíndromo, este algoritmo realiza \( n \) comparaciones por desigualdad y \( 2n + 2 \left\lfloor\dfrac{n}{2}\right\rfloor + 16 \) asignaciones.
Espacio: \( 2n + 16 \) elementos.

Como pueden observar, este algoritmo es muy ineficiente, hace uso de memoria innecesariamente y como veremos más adelante, realiza más de \( 8x \) operaciones que el algoritmo óptimo.

Mejorando el algoritmo (versión naïve)

Llamemos al siguiente código Algoritmo N (de naïve). El Algoritmo N presenta una mejora sustancial con respecto al Algoritmo I.

public static boolean isPalindrome(String str) {
    int n = str.length();
    for (int i = 0; i < n; ++i) {
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;
}

Tiempo: En el peor caso, cuando la palabra es un palíndromo, este algoritmo realiza \( n \) comparaciones por desigualdad.
Espacio: constante

No se hace uso de memoria adicional y ejecuta aproximadamente \( \dfrac{1}{4} \) de las operaciones que el Algoritmo I. Si bien el código se hace un poco más complejo, es un código fácilmente entendible y el incremento en la complejidad es insignificante comparado a la mejora en eficiencia.

Algoritmo óptimo

Como podemos ver en la siguiente imagen, no hace falta hacer \( n \) comparaciones para determinar si una palabra es un palíndromo.

Optimal Algorithm

Con sólo hacer (aproximadamente) la mitad de las comparaciones nos basta:

El siguiente código será denominado Algoritmo O (de óptimo).

public static boolean isPalindrome(String str) {
    int n = str.length();
    for (int i = 0; i < n/2; ++i) {
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;    
}

Tiempo: En el peor caso, cuando la palabra es un palíndromo, este algoritmo realiza \( \left\lfloor\dfrac{n}{2}\right\rfloor \) comparaciones por desigualdad.
Espacio: constante

Análisis detallado del Algoritmo I

Como vimos anteriormente, el Algoritmo I es mucho más ineficiente que los algoritmos N y O.
Pero además del análisis de complejidad que vimos antes, tenemos que tener en cuenta otras cuestiones que afectan la eficiencia del Algoritmo I.

Cada componente usado en el Algoritmo I viene con ciertas penalidades en performance que pasan desapercibidas.
Analicémoslo en detalle.

Construcción de StringBuilder

reverse() (StringBuilder)

toString() (StringBuilder)

equals() (String)

Garbage Collection

Data Cache Misses

Consumo de memoria (memory footprint)

Para analizar el consumo de memoria del Algoritmo I, vamos a hacerlo con un ejemplo concreto. Vamos usar una palabra (de habla inglesa) de 9 caracteres, a palabra en este caso es “evitative” y es un palíndromo.

isPalindrome("evitative");

Si bien consumo de memoria del Algoritmo I depende de la Virtual Machine y del Runtime Environment que estemos usando, en este caso vamos a usar una plataforma específica que está detallada aquí.

Básicamente en nuestro ejemplo se crean dos objetos, uno de tipo StringBuilder y otro de tipo String.

StringBuilder:

Los objetos de tipo StringBuilder tienen la siguiente representación en memoria.

Java StringBuilder memory representation

Un objeto del tipo StringBuilder consiste de dos partes (no necesariamente contiguas en memoria):

En Java todos los objetos tienen un header (si conoce alguna implementación que no los tenga, me avisa), en nuestra plataforma el header es de 12 bytes. En otras plataformas populares puede ser de 8 o 16 bytes, cualquier cosa ver aquí [7].

Otra cosa a tener en cuenta es el padding, que básicamente es cierto espacio de memoria que se adiciona para satisfacer el alineamiento de los objetos. En nuestro caso, los objetos deben estar alineados en direcciones de memoria múltiplos de 8.

En resumen, nuestro objeto StringBuilder tiene el siguiente tamaño en memoria (en bytes):

Primera parte: \( 24 \)
Segunda parte: \( 16 + 2n + 32 + padding \) [8]

Total: \( 8(\left\lceil\dfrac{n}{4}\right\rceil + 9) \) bytes

String:

Los objetos de tipo String tienen la siguiente representación en memoria.

Java String memory representation

Un objeto del tipo String consiste de dos partes (no necesariamente contiguas en memoria):

El objeto String aquí descripto pertenece a la especificación de Java 8. En versiones anteriores de Java, la clase String contaba con más campos, por consiguiente su tamaño en memoria era mayor. [7]

En resumen, nuestro objeto String tiene el siguiente tamaño en memoria (en bytes):

Primera parte: \( 24 \)
Segunda parte: \( 16 + 2n + padding \) [8]

Total: \( 8(\left\lceil\dfrac{n}{4}\right\rceil + 5) \) bytes

Total de memoria consumida:

El total de memoria consumida por nuestros objetos StringBuilder y String es de \( 16(\left\lceil\dfrac{n}{4}\right\rceil + 7) \) bytes.

En nuestro ejemplo \( n = 9 \), así que la memoria consumida es \( 16(\left\lceil\dfrac{9}{4}\right\rceil + 7) \) bytes, que son 160 bytes adicionales de memoria, solo para determinar si “evitative” es un palíndromo o no.
Recuerden que estos 160 bytes es un consumo totalmente innecesario de memoria.

Benchmarks

Estuve haciendo algunas mediciones de performance de los algoritmos y en las mismas se percibe una penalidad en tiempo de ejecución promedio de 8.5x del Algoritmo I por sobre los Algoritmos O y N. O sea, el Algoritmo I es más de 8 veces más lento que los otros dos, en promedio.

En ese promedio no estoy considerando un benchmark que arroja 586x de penalidad, ya que el algoritmo usado en este benchmark no fue presentado en este artículo. Lo veremos en un futuro artículo.

Puede ver el código fuente de los benchmarks en GitHub.

La explicación del los benchmarks y el código quedará para un próximo artículo.

Algoritmo N vs Algoritmo O

Si bien anteriormente vimos que el Algoritmo O realiza la mitad de operaciones que el Algoritmo N, en el peor caso; el tiempo de ejecución de ambos algoritmos se ve afectado por diversos factores, como por ejemplo: el largo de la palabra, si la palabra es palíndromo o no y otros factores correspondientes a la plataforma.

En muchos casos el Algoritmo N es más rápido en tiempo de ejecución que el Algoritmo O.

Analizaremos esto en un futuro artículo.

¿Solución definitiva?

Considero que ninguno de los tres algoritmos presentados en este artículo representan una solución definitiva, ninguno es un Componente.

Un componente debe ser algo que se pueda reutilizar y en muchos casos los algoritmos aquí descriptos no son aptos para ser reutilizados.

Además, los tres algoritmos sólo aceptan un String como input. Un palíndromo no sólo es una secuencia de caracteres que se lee igual al derecho y al revés. Un palíndromo puede encontrarse en forma de notas musicales, números y también en la naturaleza.

No soy experto en genética, pero se que los palíndromos también pueden encontrarse en cadenas de ADN.
Los palíndromos en el ADN son tan importantes que algunos los consideran como responsables de evitar la extinción de la especie humana (y también otras especies) ya que de no existir los palíndromos en el ADN, se producirían mutaciones genéticas irreversibles e incorregibles, que con el paso del tiempo provocarían la extinción de la especie.
En algún futuro artículo charlaremos este tema.

Pendientes

Replicar el Algoritmo I en C# y analizar su eficiencia en tiempo de ejecución y consumo de memoria.

Conclusiones

El Algoritmo I es un excelente ejemplo de concisión y legibilidad, hace buen uso de abstracciones disponibles para lograr este objetivo. El problema con el Algoritmo I es que es un pésimo ejemplo de eficiencia.

Las abstracciones facilitan nuestra labor, nos permiten concentrarnos en el problema a resolver sin tener que pensar en el contexto, en nuestro caso la computadora.

Si bien las abstracciones son buenas, tienen una gran desventaja y es que nos hacen olvidar cómo funciona la máquina en la cual nuestro programa se ejecutará.
Los programadores modernos suelen abusar de las abstracciones y carecen de conocimiento o no le dan importancia a cuestiones importantes que afectan el comportamiento de nuestros programas, como: cache, load/store buffers, branch prediction, pipelines, modelos de memoria, instrucciones vectoriales (SIMD), etc…

Como programadores, debemos conocer en profundidad la computadora, el lenguaje de programación y la complejidad de los componentes que usamos. Pero, lamentablemente los programadores modernos se han olvidado de esto y están concentrados en otras cuestiones, como testing, agile, metaprogramming y frameworks/bibliotecas cuyo tiempo de vida no es mayor a dos años.

Volviendo a las abstracciones, la mejor de todas ellas fue descubierta por Leibniz en 1679. Esa abstracción es la que nos permite modelar el mundo real en una computadora. Esa abstracción es el Bit.

Por último, cabe destacar que el Algoritmo I podría ser útil como postcondición:

public static boolean isPalindrome(String str) {
    //postcondition: Result := reverse(str) = str
    int n = str.length();
    for (int i = 0; i < n/2; ++i) {
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;    
}

Agradecimientos

Quiero agradecer a Mario dal Lago y Javier Velilla por revisar el artículo y sugerir correcciones.
Y por último, ya que se puede decir que le debemos la vida a los palíndromos, un agradecimiento especial para ellos. :)

Notas

Byte = 8-bits.
Hay arquitecturas donde 1 byte no necesariamente equivale a 8 bits. Estas arquitecturas son inusuales hoy en día. No existe un estándar que especifique el tamaño de un byte, pero se puede decir que el estándar de facto es que 1 byte = 8 bits, es lo más común en arquitecturas de computadoras modernas.

Plataforma utilizada para el análisis en este artículo:

Para el análisis en otras plataformas, por favor referirse a [7].

Referencias

[1] Zahlen significa “Números”, en Alemán. De ahí que el conjunto de los números enteros se lo identifica con la letra \( \mathbb{Z} \).

[2] The Art of Computer Programming Volume 1, by Donald E. Knuth [3rd Edition, page 107].

[3] ¿Por qué llamo a String.equals() “función” y no “método”?. He aquí la respuesta.

[4] En Java los tipos integrales y los arrays de tipo integrales se inicializan en 0, garantizado por la especificación del lenguaje. 4.12.5 Initial Values of Variables

[5] Java String class

[6] Java Primitive Data Types

[7] Análisis de consumo de memoria en otras plataformas.

[8] La fórmula para calcular el padding de los arrays internos de StringBuilder y String son las siguientes (todo medido en bytes):
      StringBuilder internal array padding = \( 8\left\lceil\dfrac{2n + 48}{8}\right\rceil - (2n + 48) \)
      String internal array padding = \( 8\left\lceil\dfrac{2n + 16}{8}\right\rceil - (2n + 16) \)

(Estas fórmulas son específicas para la plataforma descripta en el artículo)

La fórmula general para calcular el padding de objetos es la siguiente:

\[alignment\left\lceil\dfrac{size}{alignment}\right\rceil - size\]