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 }
java
efficiency
implementations
strings
Yaneeve
fonte
fonte
Respostas:
"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 ".
fonte
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 para
indexOf()
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.
fonte
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).
fonte