Domanda espressioni regolari java: prestazioni e alternative


Recentemente ho dovuto cercare un numero di valori stringa per vedere quale corrisponde a un determinato modello. Né il numero di valori stringa né il modello stesso è chiaro fino a quando un termine di ricerca non è stato inserito dall'utente. Il problema è che ho notato ogni volta che la mia applicazione esegue la seguente riga:

    if (stringValue.matches (rexExPattern))
    {
        // do something so simple
    }

ci vogliono circa 40 microsecondi. Non c'è bisogno di dire quando il numero di valori di stringa supera alcune migliaia, sarà troppo lento.

Il modello è qualcosa come:

    "A*B*C*D*E*F*"

dove A ~ F sono solo esempi qui, ma il modello è qualcosa come sopra. notare che* che il modello cambia effettivamente per ricerca. Ad esempio "A * B * C *" può cambiare in W * D * G * A * ".

Mi chiedo se ci sia una migliore sostituzione per il modello sopra o, più in generale, un'alternativa per le espressioni regolari java.


23
2017-11-07 07:05


origine


risposte:


Le espressioni regolari in Java sono compilate in una struttura dati interna. Questa compilazione è il processo che richiede tempo. Ogni volta che invochi il metodo String.matches(String regex), l'espressione regolare specificata viene nuovamente compilata.

Quindi dovresti compilare la tua espressione regolare solo una volta e riutilizzarla:

Pattern pattern = Pattern.compile(regexPattern);
for(String value : values) {
    Matcher matcher = pattern.matcher(value);
    if (matcher.matches()) {
        // your code here
    }
}

68
2017-11-07 07:12



Considera il seguente test (veloce e sporco):

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test3 {

    // time that tick() was called
    static long tickTime;

    // called at start of operation, for timing
    static void tick () {
        tickTime = System.nanoTime();
    }

    // called at end of operation, prints message and time since tick().
    static void tock (String action) {
        long mstime = (System.nanoTime() - tickTime) / 1000000;
        System.out.println(action + ": " + mstime + "ms");
    }

    // generate random strings of form AAAABBBCCCCC; a random 
    // number of characters each randomly repeated.
    static List<String> generateData (int itemCount) {

        Random random = new Random();
        List<String> items = new ArrayList<String>();
        long mean = 0;

        for (int n = 0; n < itemCount; ++ n) {
            StringBuilder s = new StringBuilder();
            int characters = random.nextInt(7) + 1;
            for (int k = 0; k < characters; ++ k) {
                char c = (char)(random.nextInt('Z' - 'A') + 'A');
                int rep = random.nextInt(95) + 5;
                for (int j = 0; j < rep; ++ j)
                    s.append(c);
                mean += rep;
            }
            items.add(s.toString());
        }

        mean /= itemCount;
        System.out.println("generated data, average length: " + mean);

        return items;

    }

    // match all strings in items to regexStr, do not precompile.
    static void regexTestUncompiled (List<String> items, String regexStr) {

        tick();

        int matched = 0, unmatched = 0;

        for (String item:items) {
            if (item.matches(regexStr))
                ++ matched;
            else
                ++ unmatched;
        }

        tock("uncompiled: regex=" + regexStr + " matched=" + matched + 
             " unmatched=" + unmatched);

    }

    // match all strings in items to regexStr, precompile.
    static void regexTestCompiled (List<String> items, String regexStr) {

        tick();

        Matcher matcher = Pattern.compile(regexStr).matcher("");
        int matched = 0, unmatched = 0;

        for (String item:items) {
            if (matcher.reset(item).matches())
                ++ matched;
            else
                ++ unmatched;
        }

        tock("compiled: regex=" + regexStr + " matched=" + matched + 
             " unmatched=" + unmatched);

    }

    // test all strings in items against regexStr.
    static void regexTest (List<String> items, String regexStr) {

        regexTestUncompiled(items, regexStr);
        regexTestCompiled(items, regexStr);

    }

    // generate data and run some basic tests
    public static void main (String[] args) {

        List<String> items = generateData(1000000);
        regexTest(items, "A*");
        regexTest(items, "A*B*C*");
        regexTest(items, "E*C*W*F*");

    }

}

Le stringhe sono sequenze casuali di 1-8 caratteri con ciascun carattere che si verificano 5-100 volte consecutive (ad esempio "AAAAAAGGGGGDDFFFFFF"). Ho indovinato in base alle tue espressioni.

Certo, questo potrebbe non essere rappresentativo del tuo set di dati, ma le stime temporali per applicare queste espressioni regolari a 1 milione generano casualmente stringhe di lunghezza media 208 ciascuna sul mio modesto i5 dual-core da 2,3 GHz:

Regex      Uncompiled    Precompiled
A*          0.564 sec     0.126 sec
A*B*C*      1.768 sec     0.238 sec
E*C*W*F*    0.795 sec     0.275 sec

Uscita effettiva:

generated data, average length: 208
uncompiled: regex=A* matched=6004 unmatched=993996: 564ms
compiled: regex=A* matched=6004 unmatched=993996: 126ms
uncompiled: regex=A*B*C* matched=18677 unmatched=981323: 1768ms
compiled: regex=A*B*C* matched=18677 unmatched=981323: 238ms
uncompiled: regex=E*C*W*F* matched=25495 unmatched=974505: 795ms
compiled: regex=E*C*W*F* matched=25495 unmatched=974505: 275ms

Anche senza l'accelerazione delle espressioni precompilate, e anche considerando che i risultati variano in modo incontrollato a seconda del set di dati e dell'espressione regolare (e anche considerando che ho infranto una regola di base dei test delle prestazioni Java giusti e ho dimenticato di utilizzare prima HotSpot), questo è molto veloce, e mi chiedo ancora se il collo di bottiglia è veramente dove pensi che sia.

Dopo il passaggio alle espressioni precompilate, se ancora non stai incontrando il tuo requisiti effettivi di prestazione, fai qualche profilazione. Se trovi che il collo di bottiglia è ancora nella tua ricerca, considera l'implementazione di un algoritmo di ricerca più ottimizzato.

Ad esempio, supponendo che il set di dati sia simile al mio test impostato sopra: se il tuo set di dati è noto in anticipo, riduci ogni elemento in esso contenuto in una chiave stringa più piccola rimuovendo i caratteri ripetitivi, ad es. per "AAAAAAABBBCCCCCCC", memorizzarlo in una mappa di qualche tipo digitata da "ABC". Quando un utente cerca "ABC * "(supponendo che le espressioni rege siano in quella forma particolare), cerca gli elementi" ABC "o qualsiasi altra cosa, dipende molto dal tuo scenario.


25
2017-11-07 09:21