qual è il metodo di ricerca della sottostringa più veloce in Java

Question

Ho bisogno di implementare un modo per cercare la sottostringa (aghi) in un elenco di stringhe (pagliaio) utilizzando Java.

In particolare, la mia app ha un elenco di profili utente. Se scrivo alcune lettere, ad esempio "Ja", quindi esegui una ricerca, tutti gli utenti il ​​cui nome contiene "ja" devono essere visualizzati. Ad esempio, il risultato potrebbe essere "Jack", "Jackson", "Jason", "Dijafu".

In Java, come noto, esistono 3 metodi build-in per visualizzare la sottostringa di ricerca in una stringa.

1. string.contains()

2. String.IndexOf()

3. espressione regolare. è qualcosa di simile string.matches ("ja"))

La mia domanda è: Quali sono i tempi di esecuzione di ogni metodo di cui sopra? quale è il modo più veloce o più efficiente o più popolare per verificare se l'elenco di string contiene una sottostringa data.

So che esistono alcuni algoritmi che fanno la stessa cosa, come l'algoritmo di ricerca stringa Boyer-Moore, l'algoritmo di Knuth-Morris-Pratt e così via. Non voglio usarli perché ho solo una piccola lista di stringhe, e penso che usarli sia un po 'eccessivo per me in questo momento. Devo anche scrivere un sacco di codice extra per un algoritmo non incorporato. Se pensi che i miei pensieri non siano corretti, non esitare a correggermi.

Answer 1

String[] names = new String[]{"jack", "jackson", "jason", "dijafu"}; 
    long start = 0; 
    long stop = 0; 

    //Contains 
    start = System.nanoTime(); 
    for (int i = 0; i < names.length; i++){ 
     names[i].contains("ja"); 
    } 
    stop = System.nanoTime(); 
    System.out.println("Contains: " + (stop-start)); 

    //IndexOf 
    start = System.nanoTime(); 
    for (int i = 0; i < names.length; i++){ 
     names[i].indexOf("ja"); 
    } 
    stop = System.nanoTime(); 
    System.out.println("IndexOf: " + (stop-start)); 

    //Matches 
    start = System.nanoTime(); 
    for (int i = 0; i < names.length; i++){ 
     names[i].matches("ja"); 
    } 
    stop = System.nanoTime(); 
    System.out.println("Matches: " + (stop-start)); 

uscita:

Contains: 16677 
IndexOf: 4491 
Matches: 864018 

Answer 2

Per quanto riguarda i tre che hai chiesto, un'espressione regolare sarà molto più lenta perché richiede di mettere insieme una macchina a stati completi quando hai un obiettivo molto più semplice. Per contains vs indexOf ...

2114 public boolean contains(CharSequence s) { 
2115  return indexOf(s.toString()) > -1; 
2116 } 

(vale a dire, contains solo chiamate indexOf, ma si potrebbe essere richiesto un String creazione in più su ogni invocazione. Questa è solo un'implementazione di contains, ma dal momento che il contratto di contains è un semplificazione di indexOf, questo è probabilmente il modo in cui ogni implementazione funzionerà.)

Answer 3

Questo dipende dalla marca/versione di JRE (e persino JDK). Dipende anche/potrebbe dipendere da fattori come la lunghezza delle stringhe, la probabilità di essere contenuti, in quale posizione, ecc. L'unico modo per ottenere dati precisi sulle prestazioni richiede l'impostazione del contesto esatto.

Tuttavia, in generale aString.contains() e aString.indexOf() devono essere esattamente uguali. E anche se un'espressione regolare era ottimizzata in modo ottimale, non avrebbe superato le prestazioni dei primi due.

No, Java non utilizza algoritmi estremamente specializzati.

Answer 4

Dall'esempio nella sua interrogazione, suppongo che si vuole fare di casi confronti insensibili. Quelli rallentano notevolmente il processo.Quindi, se riesci a convivere con alcune inesattezze - che potrebbero dipendere dalle impostazioni locali in cui devi eseguire il confronto, e il tuo testo lungo viene ricercato ancora e ancora, potrebbe avere senso convertire il testo lungo una volta in maiuscolo, e anche la stringa di ricerca, quindi cerca maiuscole e minuscole.

Answer 5

Se stai cercando una grande quantità di stringhe, ho letto che l'algoritmo Aho-Corasick è piuttosto veloce, ma è nativamente implementato in Java. È lo stesso algoritmo utilizzato da GREP nei sistemi basati su Unix se questo aiuta ed è piuttosto efficiente. Here è un'implementazione Java per gentile concessione di Berkley.

Consulta anche: https://stackoverflow.com/a/1765616/59087

Answer 6

La risposta accettata non è corretta e non completa.

• indexOf() esegue una ricerca stringa ingenua utilizzando il backtracking sui disallineamenti. Questo è abbastanza veloce su piccoli modelli/testi ma mostra prestazioni molto scarse su grandi testi
• contains("ja") dovrebbe essere paragonabile a indexOf (perché delega ad esso)
• matches("ja") non consegnerà il risultato corretto, perché cerca una corrispondenza esatta (solo la stringa "ja" corrisponderà esattamente)
• Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find(); sarebbe il modo corretto per trovare testi con espressioni regolari. In pratica (utilizzando testi di grandi dimensioni) sarà il modo più efficiente usando solo la java api. Questo perché un modello costante (come "ja") non verrà elaborato dal motore regex (che è lento) ma da un Algoritmo Boyer-Moore (che è veloce)