¿Por qué la clase String de Java no implementa un indexOf () más eficiente?

Siguiendo la siguiente pregunta sobre desbordamiento de pila

/programming/5564610/fast-alernative-for-stringindexofstring-str

Me pregunto por qué es que Java (6 al menos) no usa una implementación más eficiente.

El siguiente es el código:

java.lang.String # indexOf (String str)

1762    static int indexOf(char[] source, int sourceOffset, int sourceCount,
1763                       char[] target, int targetOffset, int targetCount,
1764                       int fromIndex) {
1765        if (fromIndex >= sourceCount) {
1766            return (targetCount == 0 ? sourceCount : -1);
1767        }
1768        if (fromIndex < 0) {
1769            fromIndex = 0;
1770        }
1771        if (targetCount == 0) {
1772            return fromIndex;
1773        }
1774
1775        char first  = target[targetOffset];
1776        int max = sourceOffset + (sourceCount - targetCount);
1777
1778        for (int i = sourceOffset + fromIndex; i <= max; i++) {
1779            /* Look for first character. */
1780            if (source[i] != first) {
1781                while (++i <= max && source[i] != first);
1782            }
1783
1784            /* Found first character, now look at the rest of v2 */
1785            if (i <= max) {
1786                int j = i + 1;
1787                int end = j + targetCount - 1;
1788                for (int k = targetOffset + 1; j < end && source[j] ==
1789                         target[k]; j++, k++);
1790
1791                if (j == end) {
1792                    /* Found whole string. */
1793                    return i - sourceOffset;
1794                }
1795            }
1796        }
1797        return -1;
1798    }

La "eficiencia" se trata de compensaciones, y el "mejor" algoritmo dependerá de muchos factores. En el caso de indexOf(), uno de esos factores es el tamaño esperado de las cadenas.

El algoritmo del JDK se basa en una referencia indexada simple en matrices de caracteres existentes. El Knuth-Morris-Pratt al que hace referencia necesita crear un nuevo que tenga int[]el mismo tamaño que la cadena de entrada. Para Boyer-Moore , necesita varias tablas externas, al menos una de las cuales es bidimensional (creo; nunca he implementado BM).

Entonces, la pregunta es: ¿la asignación de los objetos adicionales y la creación de tablas de búsqueda están compensadas por el mayor rendimiento del algoritmo? Recuerde, no estamos hablando de un cambio de O (N ² ) a O (N), sino simplemente una reducción en el número de pasos dados para cada N.

Y esperaría que los diseñadores de JDK dijeran algo así como "para cadenas con menos de X caracteres, el enfoque simple es más rápido, no esperamos el uso regular de cadenas más largas que eso, y las personas que usan cadenas más largas sabrán cómo optimizar sus búsquedas ".

El algoritmo de búsqueda de cadenas eficiente estándar que todos conocen es Boyer-Moore . Entre otras cosas, requiere construir una tabla de transición que sea del mismo tamaño que su conjunto de caracteres. En el caso de ASCII, es una matriz con 256 entradas, que es una sobrecarga constante que vale la pena en cadenas largas y no ralentiza las cadenas pequeñas lo suficiente como para que a nadie le importe. Pero Java usa caracteres de 2 bytes, lo que hace que esa tabla tenga un tamaño de 64K. En uso normal, esta sobrecarga excede la aceleración esperada de Boyer-Moore, por lo que Boyer-Moore no vale la pena.

Por supuesto, la mayor parte de esa tabla tendrá la misma entrada, por lo que puede pensar que puede almacenar excepciones de manera eficiente y luego proporcionar valores predeterminados para cualquier cosa que no esté en sus excepciones. Desafortunadamente, las formas de hacerlo vienen con una sobrecarga de búsqueda que los hace demasiado caros para ser eficientes. (Para un problema, recuerde que si toma una rama inesperada, se produce un bloqueo de la tubería y tienden a ser costosos).

Tenga en cuenta que con Unicode este problema depende en gran medida de su codificación. Cuando se escribió Java, Unicode se ajustaba a 64 K, por lo que Java solo usaba 2 bytes por carácter y la longitud de la cadena era simplemente el número de bytes dividido por 2. (Esta codificación se llamaba UCS-2). saltar a cualquier carácter en particular o extraer cualquier subcadena en particular, y la ineficiencia paraindexOf()No fue un problema. Desafortunadamente, Unicode ha crecido desde entonces, por lo que un carácter Unicode no siempre cabe en un carácter Java. Esto llevó a Java a los problemas de tamaño que intentaban evitar. (Su codificación ahora es UTF-16.) Por compatibilidad con versiones anteriores, no podían cambiar el tamaño de un carácter Java, pero ahora hay un meme de que los caracteres Unicode y los caracteres Java son lo mismo. No lo son, pero pocos programadores de Java lo saben, y es probable que incluso menos lo encuentren en la vida diaria. (Tenga en cuenta que Windows y .NET siguieron la misma ruta, por los mismos motivos).

En otros idiomas y entornos, se utiliza UTF-8. Tiene las buenas propiedades de que ASCII es válido Unicode y Boyer-Moore es eficiente. La desventaja es que no prestar atención a los problemas de byte variable te afecta mucho más obviamente que en UTF-16.

Principalmente se reduce a esto: la mejora más obvia es de Boyer-Moore, o alguna variante de la misma. BM y variant, sin embargo, realmente quieren una interfaz completamente diferente.

En particular, Boyer-Moore y sus derivados realmente funcionan en dos pasos: primero se hace una inicialización. Esto construye una tabla basada puramente en la cadena que está buscando para . Eso crea una tabla que luego puede usar para buscar esa cadena con la frecuencia que desee.

Ciertamente, podría encajar esto en la interfaz existente al memorizar la tabla y usarla para búsquedas posteriores de la misma cadena de destino. No creo que encajaría muy bien con la intención original de Sun para esta función: que sea un componente básico de bajo nivel que no dependa de mucho más. Convertirlo en una función de nivel superior que dependa de una gran cantidad de otra infraestructura significaría (entre otras cosas) que tendría que asegurarse de que ninguna de las infraestructuras de memorización que utilizara pudiera utilizar la búsqueda de subcadenas.

Creo que el resultado más probable de esto sería simplemente volver a implementar algo como esto (es decir, una rutina de búsqueda independiente) con un nombre diferente, con una rutina de nivel superior bajo el nombre existente. A fin de cuentas, creo que probablemente tendría más sentido escribir una nueva rutina de nivel superior con un nuevo nombre.

La alternativa obvia a eso sería usar algún tipo de versión simplificada de memorización, que (por ejemplo) almacenó solo una tabla estáticamente y la reutilizó si la cadena de destino era idéntica a la utilizada para crear la tabla . Eso es ciertamente posible, pero sería muy inferior a lo óptimo para muchos casos de uso. Hacerlo seguro para subprocesos tampoco sería trivial.

Otra posibilidad sería exponer la naturaleza de dos pasos de la búsqueda de BM explícitamente. Sin embargo, dudo que a alguien realmente le guste esa idea: tiene un costo bastante alto (torpeza, falta de familiaridad) y poco o ningún beneficio para muchos casos de uso (la mayoría de los estudios sobre el tema indican que la longitud promedio de la cadena es algo así como 20 caracteres).