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

7

Siguiendo la siguiente pregunta sobre el desbordamiento de pila

enlace

Me pregunto por qué java (al menos 6) 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    }
    
pregunta Yaneeve 06.04.2011 - 12:47

3 respuestas

25

"Eficiencia" tiene que ver con 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 de JDK se basa en una simple referencia indexada en matrices de caracteres existentes. El Knuth-Morris-Pratt al que hace referencia debe crear un nuevo int[] que tenga 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; I ' Nunca he implementado BM).

Entonces, la pregunta es: ¿la asignación de los objetos adicionales y la creación de tablas de búsqueda se compensan con el aumento del rendimiento del algoritmo? Recuerde, no estamos hablando de un cambio de O (N 2 ) a O (N), sino simplemente una reducción en el número de pasos tomados para cada N.

Y esperaría que los diseñadores de JDK dijeran algo como "para cadenas de menos de X caracteres, el enfoque simple es más rápido, no esperamos un 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. "

    
respondido por el kdgregory 06.04.2011 - 14:12
10

El algoritmo de búsqueda de cadenas eficiente y estándar que todos conocen es Boyer-Moore . Entre otras cosas, es necesario crear una tabla de transición que tenga el mismo tamaño que el conjunto de caracteres. En el caso de ASCII, esa es una matriz con 256 entradas, que es una sobrecarga constante que se amortiza en cadenas largas, y no ralentiza las cadenas pequeñas lo suficiente como para que alguien las cuide. Pero Java usa caracteres de 2 bytes que hacen que esa tabla tenga un tamaño de 64K. En el uso normal, esta sobrecarga supera 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 podría pensar que solo puede almacenar las excepciones de una 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 las hace demasiado caras para ser eficientes. (Para un problema, recuerde que si esto toma una rama inesperada causa un atasco en la tubería y esos tienden a ser caros.)

Tenga en cuenta que con Unicode este problema depende en gran medida de su codificación. Cuando se escribió Java, Unicode encajaba dentro de los 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 divididos por 2. (Esta codificación se llamó UCS-2). salte a cualquier carácter en particular o extraiga una subcadena en particular, y la ineficiencia para indexOf() no fue un problema. Desafortunadamente, Unicode ha crecido desde entonces, por lo que un carácter Unicode no siempre encaja 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). Para la compatibilidad con versiones anteriores, no pudieron cambiar el tamaño de un carácter Java, pero ahora hay un meme de que los caracteres Unicode y Java son la misma cosa. No lo son, pero pocos programadores de Java lo saben, e incluso muchos menos lo encontrarán en la vida diaria. (Tenga en cuenta que Windows y .NET siguieron la misma ruta, por las mismas razones).

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

    
respondido por el btilly 06.04.2011 - 15:49
1

En general, todo se reduce a esto: la mejora más obvia es la de Boyer-Moore, o alguna variante de la misma. B-M y las variantes, sin embargo, realmente quieren una interfaz completamente diferente.

En particular, Boyer-Moore y los derivados realmente funcionan en dos pasos: primero se realiza una inicialización. Esto crea una tabla basada únicamente 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 memorizando la tabla y usándola para búsquedas posteriores de la misma cadena de destino. No creo que eso encajaría muy bien con la intención original de Sun para esta función: que sería un componente básico de bajo nivel que no dependería de nada más. Si se trata de una función de nivel superior que depende de un poco de otra infraestructura, esto significaría (entre otras cosas) que tendría que asegurarse de que ninguna de las infraestructuras de memorización que utilizó podría utilizar la búsqueda de subcadenas.

Creo que el resultado más probable de eso 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 con el nombre existente. Considerando todas las cosas, creo que probablemente tendría más sentido simplemente 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 reducida de memoizing, que (por ejemplo) almacenó solo una tabla de forma estática, y la reutilizó si la cadena de destino era idéntica a la utilizada para el crear la tabla Eso es ciertamente posible, pero no sería óptimo para muchos casos de uso. Hacerlo seguro para subprocesos también sería no trivial.

Otra posibilidad sería exponer la naturaleza de dos pasos de la búsqueda B-M explícitamente. Sin embargo, dudo que a alguien realmente le guste esa idea: conlleva 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 las cadenas es algo así como 20 caracteres).

    
respondido por el Jerry Coffin 06.04.2011 - 17:07

Lea otras preguntas en las etiquetas