Por que a classe String do Java não implementa um indexOf () mais eficiente?

9

Seguindo a pergunta abaixo sobre Stack Overflow

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

Eu fiquei me perguntando por que é que o java (pelo menos 6) não usa uma implementação mais eficiente?

A seguir está o 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    }
Yaneeve
fonte
3
Observe que este não é o Java 6 em geral, mas o código OpenJDK.
Péter Török
1
@ Péter Török, é verdade, mas descompactar o src.zip de jdk1.6.0_23 e olhando para o arquivo String.java eu vejo exatamente o mesmo código
Yaneeve
1
@Yaneeve, hmmm, interessante ... se eu fosse um advogado da Oracle, eu certamente tem alguns pensamentos sobre este :-)
Péter Török
2
Essa rotina é otimizada sob as tampas (quando disponível) através das instruções SSE4.2 - se o seu hardware suportar, basta ativar o suporte com o sinalizador JVM apropriado.
Nim
2
@ Peter - por quê? Ele não copiou o código Java 6 ou violou um acordo de segredo comercial / não divulgação. Ele acabou de dizer que os dois arquivos são iguais nesta área.
Stephen C

Respostas:

26

"Eficiência" tem tudo a ver com tradeoffs, e o "melhor" algoritmo dependerá de muitos fatores. No caso de indexOf(), um desses fatores é o tamanho esperado das strings.

O algoritmo do JDK é baseado em uma referência indexada simples em matrizes de caracteres existentes. O Knuth-Morris-Pratt a que você se refere precisa criar um novo int[]que seja do mesmo tamanho que a sequência de entrada. Para Boyer-Moore , você precisa de várias tabelas externas, das quais pelo menos uma é bidimensional (eu acho; nunca implementei BM).

Portanto, a pergunta se torna: a alocação de objetos adicionais e a criação de tabelas de pesquisa são compensadas pelo aumento do desempenho do algoritmo? Lembre-se, não estamos falando de uma mudança de O (N 2 ) para O (N), mas simplesmente uma redução no número de etapas executadas para cada N.

E eu esperava que os designers do JDK dissessem algo como "para strings com menos de caracteres X, a abordagem simples é mais rápida, não esperamos o uso regular de strings por mais tempo do que isso, e as pessoas que usam strings mais longas saberão como otimizar suas pesquisas ".

kdgregory
fonte
11

O algoritmo padrão de busca eficiente de strings que todo mundo conhece é Boyer-Moore . Entre outras coisas, é necessário criar uma tabela de transição com o mesmo tamanho do seu conjunto de caracteres. No caso do ASCII, é uma matriz com 256 entradas, que é uma sobrecarga constante que compensa longas seqüências de caracteres e não reduz a velocidade das strings pequenas o suficiente para que alguém se importe. Mas o Java usa caracteres de 2 bytes, o que torna essa tabela em 64K. Em uso normal, essa sobrecarga excede a aceleração esperada da Boyer-Moore; portanto, Boyer-Moore não vale a pena.

Obviamente, a maior parte dessa tabela terá a mesma entrada; portanto, você pode pensar que pode simplesmente armazenar exceções de maneira eficiente e fornecer padrões para qualquer coisa que não esteja em suas exceções. Infelizmente, as maneiras de fazer isso vêm com a sobrecarga de pesquisa que as torna muito caras para serem eficientes. (Para um problema, lembre-se de que um caso de ocorrência inesperada de uma ramificação causa um bloqueio no pipeline e esses tendem a ser caros.)

Observe que, com o Unicode, esse problema depende muito da sua codificação. Quando o Java foi gravado, o Unicode cabia dentro de 64 K; portanto, o Java usava apenas 2 bytes por caractere e o comprimento da string era simplesmente o número de bytes dividido por 2. (Essa codificação era chamada UCS-2). pule para qualquer caractere em particular ou extraia qualquer substring em particular, e a ineficiência paraindexOf()foi um não-problema. Infelizmente, o Unicode cresceu desde então, um caractere Unicode nem sempre se encaixa em um caractere Java. Isso colocou o Java nos problemas de tamanho que eles estavam tentando evitar. (A codificação deles agora é UTF-16.) Para compatibilidade com versões anteriores, eles não podiam alterar o tamanho de um caractere Java, mas agora existe um meme de que caracteres Unicode e caracteres Java são a mesma coisa. Eles não são, mas poucos programadores de Java sabem disso e menos ainda o encontram na vida cotidiana. (Observe que Windows e .NET seguiram o mesmo caminho, pelos mesmos motivos.)

Em alguns outros idiomas e ambientes, o UTF-8 é usado. Ele tem as boas propriedades de que ASCII é válido Unicode e Boyer-Moore é eficiente. A desvantagem é que a falta de atenção aos problemas de bytes variáveis ​​atinge muito mais obviamente do que no UTF-16.

btilly
fonte
IMO, alegando que uma alocação de 64K "excede a aceleração esperada" não faz sentido. Uma é o tamanho da memória, a outra CPU faz ciclos. Eles não são diretamente comparáveis.
21711 Jerry Coffin
1
@ jerry-caixão: Uma comparação direta é razoável. São necessários ciclos de CPU não desprezíveis para alocar dados e inicializar uma estrutura de dados de 64K.
btilly
1
+1 para a descrição detalhada dos custos de Boyer-Moore
kdgregory
a inicialização é obviamente linear no tamanho, mas pelo menos em um caso típico, a alocação é aproximadamente uma velocidade constante.
Jerry Coffin
1

Tudo se resume a isso: a melhoria mais óbvia é de Boyer-Moore, ou alguma variante dela. BM e variantes, no entanto, realmente querem uma interface completamente diferente.

Em particular, Boyer-Moore e derivados realmente funcionam em duas etapas: primeiro você faz uma inicialização. Isso cria uma tabela baseada puramente na corda que você está procurando para . Isso cria uma tabela que você pode usar para procurar essa sequência quantas vezes quiser.

Você certamente poderia ajustar isso na interface existente memorizando a tabela e usando-a para pesquisas subsequentes da mesma cadeia de destino. Eu não acho que isso se encaixaria muito bem com a intenção original da Sun para essa função: que seja um componente básico de baixo nível que não dependa de muita coisa. Torná-lo uma função de nível superior que depende de muitas outras infraestruturas significaria (entre outras coisas) que você teria que garantir que nenhuma infraestrutura de memorização usada utilizasse a pesquisa de substring.

Acho que o resultado mais provável disso seria simplesmente reimplementar algo assim (ou seja, uma rotina de pesquisa independente) com um nome diferente, com uma rotina de nível superior com o nome existente. Considerando tudo, acho que provavelmente faria mais sentido apenas escrever uma nova rotina de nível superior com um novo nome.

A alternativa óbvia a isso seria usar algum tipo de versão simplificada de memorização, que (por exemplo) armazenasse apenas uma tabela estaticamente e a reutilizasse se a sequência de destino fosse idêntica à usada para criar a tabela . Isso é certamente possível, mas seria muito aquém do ideal para muitos casos de uso. Torná-lo seguro para threads também não seria trivial.

Outra possibilidade seria expor explicitamente a natureza de duas etapas da pesquisa de BM. Duvido que alguém realmente goste dessa idéia - ela carrega um custo razoavelmente alto (falta de jeito, falta de familiaridade) e pouco ou nenhum benefício para muitos casos de uso (a maioria dos estudos sobre o assunto indica que o comprimento médio da string é algo como 20 caracteres).

Jerry Coffin
fonte
1
Mesmo que você exponha a natureza de duas etapas do BM, duvido que você tenha um bom desempenho porque uma tabela de salto de 64K não pode caber em um cache de CPU de nível 1. O custo de ter que atingir um cache mais lento provavelmente superará o fato de que você precisa de menos operações.
btilly
@ btilly: Isso faria uma grande diferença se você realmente usasse a tabela inteira - mas pelo menos em um caso típico, ~ 1K da tabela ficará no cache, e o restante será tocado apenas durante inicialização.
Jerry Coffin
@ jerry-caixão: Você claramente não se importa em ser capaz de processar textos asiáticos.
btilly
1
@tilly: Não é assim - não é que eu não me importo; é que estou ciente de que, pelo menos para muitos usuários, é muito menos comum. Mesmo quando você lida com texto asiático, é raro procurar uma única string contendo coreano e 3 variedades diferentes de caracteres japoneses e 2 variedades diferentes de caracteres chineses, etc. Sim, os alfabetos asiáticos são maiores que o inglês, mas não , um típico A string ainda não contém dezenas de milhares de caracteres únicos. Por exemplo, uma cadeia de 20 caracteres, você nunca precisa de mais de 20 linhas de cache da tabela.
Jerry Coffin
Na pior das hipóteses, você usa uma linha de cache por caractere exclusivo na string de pesquisa.
Jerry Coffin