Get best of the week

Escrevemos melhor a pesquisa por substring do que nos livros didáticos



A vida de um engenheiro é cheia de surpresas: especialmente quando você precisa lidar com a produtividade. Por exemplo, o que acontece se você tentar executar esse código Java? Parece bastante inocente:

//   String.repeat  JDK 11  :
final var needle = "A".repeat(500000) + "B";
final var haystack = "A".repeat(1000000) + "B";
System.out.println(haystack.indexOf(needle));

Esperamos, esperamos, esperamos ... Pelo menos no meu laptop OpenJDK 13 de 2015, encontrar uma agulha no palheiro leva cerca de um minuto. Nossa boa e velha JVM passou por décadas de ajuste de desempenho, implementou efetivamente intrínsecas String.indexOfe assim por diante. O que poderia ter dado errado?
Este é o começo de uma série de vários artigos, cortesia de seu autor, Linas Medžiūnas , e publicado originalmente no blog WiX Engineering .


Dê uma olhada no que é inserido: os dados são especialmente selecionados para obter desempenho quadrático no pior dos casos ( O(nm)onde né o comprimento haystacke mo comprimento needle) para o algoritmo de busca de substring ingênuo. Corremos todos os caracteres haystacke, se eles coincidirem com os primeiros needle, começamos a correr needleno loop interno - e assim por diante até o primeiro caractere incompatível.

Você pode argumentar que este exemplo é inútil, porque esses dados de entrada foram projetados e arquivados especialmente, na prática, você não encontrará isso. Pense duas vezes. E se você estiver trabalhando em um serviço da Web cujos usuários possam carregar seqüências de caracteres arbitrárias e, em algum lugar na parte de trás do serviço, houver um código executadoindexOfnessas linhas? Depois, apenas alguns pedidos maliciosos, como o descrito acima, colocam seu serviço de joelhos. Vale a pena conhecer, pelo menos, os piores casos para os dados de entrada.

Felizmente, existem algoritmos de pesquisa de substring com complexidade linear ( O(n+m)). Eles não têm problemas com os dados do exemplo acima. Por exemplo, o código Scala a seguir faz a mesma coisa, mas é executado em milissegundos no mesmo computador, na mesma JVM e usando exatamente o mesmo sob o capô java.lang.String:

val needle = "A" * 500000 + "B"
val haystack = "A" * 1000000 + "B"
println(haystack.indexOfSlice(needle))

O segredo da enorme diferença está no método indexOfSlice, que faz parte da biblioteca padrão do Scala . Ele implementa o inteligente algoritmo linear de Knut-Morris-Pratt . E não, não estou dizendo que o idioma X seja melhor que o idioma Y. Infelizmente, tudo é muito mais complicado aqui! Por exemplo, indexOfSliceno Scala, esse é um método generalizado que funciona não apenas com cadeias de caracteres, mas também em outras coleções seqüenciais, e pode comparar não apenas caracteres, mas também elementos de outros tipos. Deve ser muito mais lento do queString.indexOfdo Java no caso intermediário (falaremos sobre isso mais tarde). Portanto, temos um algoritmo eficiente com desempenho muito melhor no pior caso, mas, em média, é mais lento porque possui uma parte constante muito maior. Dilemas como esse são um problema típico no ajuste de desempenho. Não existe uma pílula mágica que resolva todos os problemas - você precisa analisar cuidadosamente o problema e fazer os micro-benchmarks certos.


Você ainda está comigo Boa! Veja bem, isso é apenas uma introdução. Eu queria motivá-lo a lidar com a complexidade teórica e o desempenho prático dos algoritmos. No restante deste artigo, examinaremos algumas implementações de vários algoritmos de pesquisa de substring e seus benchmarks.

Vamos explorar três algoritmos de pesquisa de substring. Todos eles trabalham em tempo linear e requerem pré-processamento, linearmente dependente do comprimento needle. O cálculo do mesmo needleé necessário apenas uma vez e, em seguida, pode ser reutilizado em várias tentativas de pesquisa. Isso é razoável, porque em muitos casos precisamos procurar a mesma linha repetidamente. E mesmo que não façamos isso, a pré-computação não é uma operação particularmente cara.

Todos os algoritmos abaixo ignoram cada um dos caracteres emhaystackapenas uma vez em uma linha (sem acesso aleatório pelo índice), para que todos funcionem bem no modo de streaming. Este artigo surgiu durante um trabalho real em um servidor proxy para produção com base na estrutura Netty , e isso influenciou algumas das decisões de design da API. Além disso, como precisamos fazer uma pesquisa em buffers de bytes, o código funcionará com Byte, não com Char.


Knut-Morris-Pratt (algoritmo KMP)


Este é um algoritmo de pesquisa de substring bem conhecido, que remonta aos anos 70 do século passado. Está bem descrito na literatura , portanto não o descreverei aqui em detalhes. O ILC é baseado em máquinas de estado - durante a fase de cálculo preliminar, uma matriz de índices de link é construída com base em needle. Durante a pesquisa, a máquina aceita caracteres haystackum a um na entrada e atualiza seu estado interno de acordo (e o estado em que há apenas um índice na tabela de relações).

Aqui está uma implementação no Scala .

Algoritmo de pesquisa de substring binário


Inicialmente, tive que inventar independentemente o nome desse algoritmo: nunca vi nada parecido em nenhum lugar da literatura. Como resultado, vim para o nome "Shifting Bit Mask". Mais tarde, verificou-se que esse algoritmo e suas variações são conhecidos desde 1964 sob vários nomes em inglês como "Bitap", "Shift-or", "Shift-and", "Baeza-Yates - Gonnet". Obrigado aos leitores que encontraram para mim. Este artigo foi escrito muito antes desta notícia.

Esse algoritmo é baseado em uma idéia muito simples e funciona muito bem, já que quase não há saltos, e é baseado em várias operações binárias primitivas. Por isso, ele tem um limite no comprimento needleque vamos procurar: não pode ter mais que 64 bytes. Esse número foi obtido simplesmente pelo número de bits emLongna JVM. Essa limitação é generosa o suficiente para um grande número de tarefas reais.

Desde que eu mesmo desenvolvi esse algoritmo, tentarei falar sobre ele com mais detalhes. Primeiro, pré-calculamos o contexto de pesquisa para o desejado needle:

  def computeBitMasks(needle: Array[Byte]): Array[Long] = {
    require(needle.length <= 64, "Maximum supported search pattern length is 64.")
    val bitMasks = Array.ofDim[Long](256)
    var bit = 1L
    for (c <- needle) {
      bitMasks(toUnsignedInt(c)) |= bit
      bit <<= 1
    }
    bitMasks
  }

Nós pré-calculamos bitMask(64 bits Long) para cada valor de byte possível (256 peças bitMask). Para algum valor de byte X, ele bitmaskcontém unidades em todos os locais em que Xestá needle. Por exemplo, aqui está uma pequena máscara para a string "abracadabra": Além disso, você precisa pré-calcular , o que ajudará a entender que encontramos uma correspondência exata. Parece um valor , com um pouco de posição :



successBitMaskLong1needle.length — 1

  def computeSuccessBitMask(needle: Array[Byte]): Long = {
    1L << (needle.length - 1)
  }

E, finalmente, você precisa fazer, de fato, uma pesquisa. O único estado mutável que queremos armazenar é currentMask( Long). Para cada byte in haystack, mudamos currentMaskum 1pouco para a esquerda , definimos seu bit menos significativo 1e fazemos um bit a bit andentre o resultado e bitMaskcalculado para o valor atual do byte processado haystack(isso andlimpa todos os bits nos locais currentMaskque não correspondem ao byte processado atual).

Assim, após o processamento de cada byte, apenas os bits que estão em posições adequadas sobreviverão. E com cada byte processado, todos os bits são deslocados para a esquerda em uma posição. Se o bit "sobreviver" durante o número de iterações igual ao comprimentoneedle- encontramos uma correspondência! E podemos verificar isso com successBitMask:

  def process(value: Byte): Boolean = {
    currentMask = ((currentMask << 1) | 1) & bitMasks(toUnsignedInt(value))
    (currentMask & successBitMask) == 0
  }

Nota: o método descrito acima retorna falsese algo for encontrado e parece contra-intuitivo. Isso pode ser entendido para que o valor truesignifique a necessidade de continuar a pesquisa, mas a falseinterrompe - isso se deve ao fato de que, como escrevi acima, a API foi compatível com o Netty. Se você está se perguntando como executar uma pesquisa, aqui está um exemplo.

Como resultado, toda a lógica se resume a apenas algumas instruções simples do processador. Infelizmente, permanece uma verificação completamente inútil dos limites dos índices da matriz bitMasks, que nenhum JDK pode remover (e eu observei o assembler gerado por vários JDKs diferentes).

Aqui está a implementação completa do Scala .

Aho korasik


Este é outro algoritmo popular conhecido desde 1975. Seu recurso distintivo (e às vezes bastante útil) é a capacidade de pesquisar vários de uma needlesó vez ao mesmo tempo, enquanto todos os personagens de haystacksão ignorados exatamente uma vez (acho ótimo!). A idéia de que tudo isso funciona é uma extensão do algoritmo KMP, uma máquina de estados finitos usando uma árvore de prefixos (que é construída com base em várias needle), contendo links para links (compare com uma matriz unidimensional do KMP). Com base nesses links, o estado interno do autômato é alternado entre os nós da árvore de prefixos após cada símbolo processado e alguns dos nós indicam um resultado de pesquisa positivo para um determinadoneedle. A fase de pré-computação aqui é bastante complicada, mas a fase de pesquisa é inesperadamente muito simples.

Aqui está um link para uma implementação de trabalho no Scala .


Esta era uma lista completamente incompleta de algoritmos de pesquisa de substring. Também tentamos o algoritmo Rabin-Karp e Boyer-Moore . Desses dois, Boyer-Moore mostrou desempenho comparável, mas ambos não são compatíveis com streaming (usando acesso aleatório haystackpor índice) e, portanto, eu os removi desta investigação.


Benchmarks


Iremos comparar os três algoritmos descritos acima e, além disso, examinar os resultados dos métodos String.indexOf(Java) e indexOfSlice(Scala). Para ser honesto, essa não é uma comparação completamente correta, porque String.indexOffunciona com cadeias de caracteres e todos os outros métodos estão em matrizes de bytes. Mas isso não parece invalidar os resultados dessa comparação. Além disso, também incluí os resultados Bytes.indexOfdo Guava (v.28.1). Este método funciona em matrizes de bytes. E eles escreveram no Google - tudo o que escrevem lá funciona super rápido, certo?

Escrever benchmarks é sempre difícil, porque você pode enviar dados completamente diferentes para a entrada, alterá-los de várias maneiras diferentes - não apenas em tamanho needleehaystack, mas também pelo conteúdo interno dessas linhas (o que pode afetar bastante alguns algoritmos). Na prática, sempre vale a pena verificar os dados de entrada mais semelhantes aos dados de suas tarefas reais (foi o que fizemos em nosso projeto).

Para encurtar este artigo, usei apenas 2 tipos de entrada. Um deles visa refletir o caso real: haystackaproximadamente 1,5 KB de tamanho (com texto legível por humanos dentro) needle- 9 bytes, e não haystacknesta sequência (isso é necessário para forçar o algoritmo a executar uma varredura completa).

Outro tipo de entrada é necessário para obter o pior comportamento de um algoritmo quadrático. É muito mais curto do que os dados desde o início deste artigo: caso contrário, teríamos que esperar um minuto inteiro, lembra-se? Matrizhaystacké definido no formato "AA...AAB"(o mesmo tamanho do primeiro tipo de dados) e needle- 64 bytes (especialmente para o algoritmo de pesquisa de substring binário para lidar com ele) uma matriz do mesmo tipo (a correspondência ocorre apenas no final haystack).

Um benchmark escrito na estrutura JMH pode ser encontrado aqui . Se você tiver outras idéias sobre o que e como medir aqui - você pode clonar este repositório, alterar alguma coisa e postar comentários.

Por sugestão de Vladimir Sitnikov , adicionei resultados de benchmark para java.util.regex.Pattern: ele usa o algoritmo de Boyer-Moore sob o capô.


(Nota do tradutor: a propósito, Vladimir Sitnikov é membro de vários comitês de programa do JUG Ru Group e faz relatórios interessantes. Por exemplo, um vídeo de seu relatório do JPoint 2019 intitulado "Java retarda: edição do CodeCache" está disponível no link ).

Resultados de referência


Os resultados são apresentados em milissegundos, menos é melhor: aqui tudo é como o esperado:

# JMH version: 1.21
# VM version: JDK 13.0.1, OpenJDK 64-Bit Server VM, 13.0.1+9
Benchmark (searchInput) Mode Cnt Score Error Units
javaIndexOf REGULAR avgt 5 0.622 ± 0.002 us/op
shiftingBitMask REGULAR avgt 5 1.982 ± 0.017 us/op
regexPattern REGULAR avgt 5 2.184 ± 0.006 us/op
kmp REGULAR avgt 5 2.635 ± 0.016 us/op
scalaIndexOfSlice REGULAR avgt 5 3.202 ± 0.009 us/op
guavaIndexOf REGULAR avgt 5 3.696 ± 0.095 us/op
ahoCorasic REGULAR avgt 5 7.063 ± 0.040 us/op
shiftingBitMask WORST_CASE avgt 5 1.986 ± 0.010 us/op
kmp WORST_CASE avgt 5 5.120 ± 0.006 us/op
ahoCorasic WORST_CASE avgt 5 6.892 ± 0.025 us/op
scalaIndexOfSlice WORST_CASE avgt 5 8.765 ± 0.007 us/op
regexPattern WORST_CASE avgt 5 11.566 ± 0.086 us/op
javaIndexOf WORST_CASE avgt 5 23.029 ± 0.124 us/op
guavaIndexOf WORST_CASE avgt 5 52.927 ± 0.275 us/op



  • Para dados comuns, ele domina javaIndexOf, porque usa intrínsecas de alto desempenho dentro, por causa das quais a parte constante é pequena;
  • , : , (O(nm)) javaIndexOf, — , shiftingBitMask ( ) .
  • guavaIndexOf , javaIndexOf; , 2 , shiftingBitMask;
  • scalaIndexOfSlice - , knuthMorrisPratt, , — , ;
  • o desempenho não é o recurso mais forte ahoCorasic(ou pelo menos de sua implementação; devo admitir que realmente não tentei fazer microoptimizações nele, porque o adicionei apenas por causa de seu recurso distintivo: a capacidade de pesquisar várias linhas ao mesmo tempo, e isso semelhante ao tópico de um artigo separado);
  • dados de entrada (e comprimento needle) não afetaram o desempenho shiftingBitMaske ahoCorasic.

achados


Em diferentes casos, os benchmarks podem funcionar de maneiras diferentes. Apesar de os resultados acima parecerem muito indicativos, você sempre deve fazer medições e dados que refletem suas tarefas reais.

Com base nos dados apresentados, tirei as seguintes conclusões:

  • String- , , String.indexOf ( java.util.regex.Pattern — );
  • , needle 64 , ;
  • , --;
  • Scala - ( ), indexOfSlice — ;
  • , -.

Isso é tudo! Se você gosta de ler sobre algoritmos, desempenho e similares (e também sobre Scala, JVM e Java em geral), assine o autor deste artigo, Linas Medziunas ( Medium , Twitter ).

O repositório do github com todo o código deste artigo está aqui .


Traduções de artigos são publicadas com o apoio do JUG Ru Group e da JPoint Conference .

More articles:


All Articles