czy ktoś może zaproponować szybszą alternatywę dla tego algorytmu wyrażeń regularnych?

Question

Muszę wywoływać tę funkcję dość często. Zasadniczo zamienia wszystkie znaki akcentowane na ich nieakcentowane odpowiedniki, zamienia spacje na "_", konwertuje na małe litery i usuwa pozostałe kody obce, dzięki czemu można bezpiecznie używać ich jako nazw plików/ścieżek URL/itd. Problem polega na tym, jak widać, wygląda okropnie z punktu widzenia wydajności. Czy ktokolwiek może pomyśleć o czystszej, szybszej alternatywie?

public static String makeValidPathName(String rawString) { 
    if (rawString==null) return null; 
    rawString = rawString.replaceAll("[ÁÀÂÄáàäaàáâãäå]","a"); 
    rawString = rawString.replaceAll("æ","ae"); 
    rawString = rawString.replaceAll("çÇ","c"); 
    rawString = rawString.replaceAll("[ÈÉÊËèéêë]","e"); 
    rawString = rawString.replaceAll("[ìíîïÍÌÎÏ]","i"); 
    rawString = rawString.replaceAll("ñÑ","n");        
    rawString = rawString.replaceAll("[ÓÓÖÔòóôõö]","o"); 
    rawString = rawString.replaceAll("œ","oe"); 
    rawString = rawString.replaceAll("[ÙÚÛÜùúûü]", "u"); 
    rawString = rawString.replaceAll("[ýÿ]","y"); 
    rawString= rawString.replaceAll("[^a-z A-Z 0-9 \\_ \\+]",""); 
    rawString = rawString.replaceAll(" ","_"); 
    return rawString.toLowerCase(); 
} 

--- EDIT

Ok, chłopaki ... Zrobiłem testy wydajności na wszystkich 4 przypadkach:

• przypadek 1) oryginał rutyny, ponieważ jest tu zamieszczonych.
• Przypadek 2) Poprawa sugeruje @WChargin
• przypadek 3) w tabeli przeglądowej sugerowanego przez @devconsole z moich optymalizacje dla SparseArray
• Case 4) podejście Normalizer sugerowaną przez @Erik Pragt

... a zwycięzcą jest ... TADAAA .....

D/REPLACEMENT_TEST(18563): *** Running Tests (1000 iterations) 
D/REPLACEMENT_TEST(18563): Original REGEX : 13533 ms 
D/REPLACEMENT_TEST(18563): Compiled REGEX : 12563 ms 
D/REPLACEMENT_TEST(18563): Character LUT : 1840 ms 
D/REPLACEMENT_TEST(18563): Java NORMALIZER : 2416 ms 

• to ciekawe optymalizacja kompilacja wzorzec nie hel p dużo.
• Widzę, że byłem całkowicie błędny co do moich założeń dotyczących prędkości w REGEXES, a devconsole miał rację w swoim wykształconym przypuszczeniu, że Normalizer przewyższa liczbę wyrażeń regularnych.
• To niesamowite, jak powolne są REGEXY. Różnice o rząd wielkości naprawdę mnie zaskakują. Postaram się ich unikać na Javie.
• Tabela przeglądowa jest najszybszą opcją z krótkim marginesem. Będę trzymać się tego rozwiązania, ponieważ w wersji Normalizer, nadal będę musiał zamienić niektóre znaki ręcznie (spacje na "_"), a następnie skonwertować na małe litery.

Testy przeprowadzono w Samsung Galaxy Tab v1 10.1.

W załączonym kodzie źródłowym znajdują się przypadki testowe.

public class Misc { 

    /* Test 2 (@WCChargin's Regex compilation) initialization */ 

static Map<Pattern, String> patterns = new HashMap<Pattern, String>(); 

static { 
     patterns.put(Pattern.compile("[ÁÀÂÄáàäaàáâãäå]") ,"a"); 
     patterns.put(Pattern.compile("æ"),"ae"); 
     patterns.put(Pattern.compile("çÇ"),"c"); 
     patterns.put(Pattern.compile("[ÈÉÊËèéêë]"),"e"); 
     patterns.put(Pattern.compile("[ìíîïÍÌÎÏ]"),"i"); 
     patterns.put(Pattern.compile("ñÑ"),"n");        
     patterns.put(Pattern.compile("[ÓÓÖÔòóôõö]"),"o"); 
     patterns.put(Pattern.compile("œ"),"oe"); 
     patterns.put(Pattern.compile("[ÙÚÛÜùúûü]"), "u"); 
     patterns.put(Pattern.compile("[ýÿ]"),"y"); 
     patterns.put(Pattern.compile("[^a-z A-Z 0-9 \\_ \\+]"),""); 
     patterns.put(Pattern.compile(" "),"_"); 
} 

    /* Test 3 (@devconsole's Lookup table) initialization */ 
static SparseArray<String> homeBrewPatterns=new SparseArray<String>(); 
/** helper function to fill the map where many different chars map to the same replacement */ 
static void fillMap(String chars, String replacement) { for (int i=0,len=chars.length(); i<len; i++) homeBrewPatterns.put(chars.charAt(i), replacement); } 
static { 
    // fill the sparsearray map with all possible substitutions: Any char code gets its equivalent, ie, ä->a. a->a. A->a 
    // this also does the toLowerCase automatically. If a char is not in the list, it is forbidden and we skip it. 
    fillMap("ÁÀÂÄáàäaàáâãäå","a"); 
    fillMap("æ","ae"); 
    fillMap("çÇ","c"); 
    fillMap("ÈÉÊËèéêë","e"); 
    fillMap("ìíîïÍÌÎÏ","i"); 
    fillMap("ñÑ","n"); 
    fillMap("ÓÓÖÔòóôõö","o"); 
    fillMap("œ","oe"); 
    fillMap("ÙÚÛÜùúûü","u"); 
    fillMap("ýÿ","y"); 
    fillMap(" ","_"); 
    for (char c='a'; c<='z'; c++) fillMap(""+c,""+c); // fill standard ASCII lowercase -> same letter 
    for (char c='A'; c<='Z'; c++) fillMap(""+c,(""+c).toLowerCase()); // fill standard ASCII uppercase -> uppercase 
    for (char c='0'; c<='9'; c++) fillMap(""+c,""+c); // fill numbers 
} 

    /** FUNCTION TO TEST #1: Original function, no pattern compilation */ 
public static String makeValidPathName(String rawString) { 
    if (rawString==null) return null; 
    rawString = rawString.replaceAll("[ÁÀÂÄáàäaàáâãäå]","a"); 
    rawString = rawString.replaceAll("æ","ae"); 
    rawString = rawString.replaceAll("çÇ","c"); 
    rawString = rawString.replaceAll("[ÈÉÊËèéêë]","e"); 
    rawString = rawString.replaceAll("[ìíîïÍÌÎÏ]","i"); 
    rawString = rawString.replaceAll("ñÑ","n");        
    rawString = rawString.replaceAll("[ÓÓÖÔòóôõö]","o"); 
    rawString = rawString.replaceAll("œ","oe"); 
    rawString = rawString.replaceAll("[ÙÚÛÜùúûü]", "u"); 
    rawString = rawString.replaceAll("[ýÿ]","y"); 
    rawString = rawString.replaceAll("[^a-z A-Z 0-9 \\_ \\+]",""); 
    rawString = rawString.replaceAll(" ","_"); 
    return rawString.toLowerCase(); 
} 
/** FUNCTION TO TEST #2: @WCChargin's suggestion: Compile patterns then iterate a map */ 
public static String makeValidPathName_compiled(String rawString) { 
    for (Map.Entry<Pattern, String> e : patterns.entrySet()) { 
     rawString=e.getKey().matcher(rawString).replaceAll(e.getValue()); 
    } 
    return rawString.toLowerCase(); 
} 

    /** FUNCTION TO TEST #3: @devconsole's suggestion: Create a LUT with all equivalences then append to a stringbuilder */ 
public static String makeValidPathName_lut(String rawString) { 
    StringBuilder purified=new StringBuilder(rawString.length()); // to avoid resizing 
    String aux; // to avoid creating objects inside the for 
    for (int i=0, len=rawString.length(); i<len; i++) { 
     aux=homeBrewPatterns.get(rawString.charAt(i)); 
     if (aux!=null) purified.append(aux); 
    } 
    return purified.toString(); 
} 

    /** FUNCTION TO TEST #4: @Erik Pragt's suggestion on the use of a Normalizer */ 
public static String makeValidPathName_normalizer(String rawString) { 
     return rawString == null ? null 
      : Normalizer.normalize(rawString, Form.NFD) 
       .replaceAll("\\p{InCombiningDiacriticalMarks}+", ""); 
} 

    /** Test Runner as a Runnable, just do a Handler.post() to run it */ 

public static Runnable msStringReplacementTest=new Runnable() { 

    public void run() { 


    String XTAG="REPLACEMENT_TEST"; 

    Log.d(XTAG, "*** Running Tests"); 

    int ITERATIONS=1000; 

    String[] holder=new String[4]; 

      /* http://www.adhesiontext.com/ to generate dummy long text ... its late n im tired :) */ 

    String tester="e arte nací valse ojales i demediada cesé entrañan domó reo ere fiaréis cinesiterapia fina pronto mensuraré la desatufases adulantes toree fusca ramiro hez apolíneo insalvable atas no enorme mí ojo trola chao fas eh borda no consignataria uno ges no arenque ahuyento y daca pío veló tenle baúl ve birria filo rho fui tañe mean taz raicita alimentarías ano defunciones u reabráis repase apreciaran cantorales ungidas naftalina ex guió abomba o escribimos consultarás des usó saudí mercó yod aborrecieses guiri lupia ña adosado jeringara fe cabalgadura tú descasar diseñe amar limarme escobero latamente e oreó lujuria niñez fabularios da inviernen vejé estañarán dictará sil mírales emoción zar claudiquéis ó e ti ñ veintén dañen ríase esmeraras acató noté as mancharlos avisen chocarnos divertidas y relata nuera usé fié élitro baba upa cu enhornan da toa hechizase genesíacos sol fija aplicó gafa pi enes fin asé deal rolar recurran cacen ha id pis pisó democristiano oes eras lañó ch pino fijad ñ quita hondazos ñ determinad vid corearan corrompimiento pamema meso fofas ocio eco amagados pian bañarla balan cuatrimestrales pijojo desmandara merecedor nu asimiladores denunciándote jada ñudos por descifraseis oré pelote ro botó tu sí mejorado compatibilizaciones enyerba oyeses atinado papa borbón pe dé ñora semis prosada luces leí aconteciesen doy colmará o ve te modismos virola garbillen apostabas abstenido ha bajá le osar cima ají adormecéis ñu mohecí orden abrogándote dan acanilladas uta emú ha emporcara manila arribeña hollejo ver puntead ijadeáis chalanesca pechugón silbo arabescos e i o arenar oxidas palear ce oca enmaderen niñez acude topó aguanieves i aconsejaseis lago él roía grafito ceñir jopo nitritos mofe botáis nato compresores ñu asilo amerizan allanándola cuela ó han ice puya alta lío son de sebo antieconómicas alá aceza latitud faca lavé colocándolos concebirlo miserea ñus gro mearé enchivarse"; 

    long time0=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[0]=makeValidPathName(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed0=System.currentTimeMillis()-time0; 

    Log.d(XTAG, "Original REGEX : "+elapsed0+" ms"); 

    long time1=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[1]=makeValidPathName_compiled(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed1=System.currentTimeMillis()-time1; 

    Log.d(XTAG, "Compiled REGEX : "+elapsed1+" ms"); 

    long time2=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[2]=makeValidPathName_lut(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed2=System.currentTimeMillis()-time2; 

    Log.d(XTAG, "Character LUT : "+elapsed2+" ms"); 

    long time3=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[3]=makeValidPathName_normalizer(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed3=System.currentTimeMillis()-time3; 

    Log.d(XTAG, "Java NORMALIZER : "+elapsed3+" ms"); 

    Log.d(XTAG, "Output 0: "+holder[0]); 
    Log.d(XTAG, "Output 1: "+holder[1]); 
    Log.d(XTAG, "Output 2: "+holder[2]); 
    Log.d(XTAG, "Output 3: "+holder[3]); 
    } 
}; 

Chłopaki, bardzo dziękuję za sugestie :) Kocham stackoverflow :)

Answer 1

zbudować statycznych Map<Character,String> który mapuje charakter jego replac łańcuch ementowy, czyli mapa "Á" do "a", "ä" do "a" itd. Należy również uwzględnić relacje jeden-do-jednego, czyli mapę "a" do "a" i tak dalej. Otrzymujesz mapę z co najwyżej kilkoma wpisami.

Teraz powtarzaj po znakach wejściowego ciągu znaków i szukaj zastępczego ciągu na mapie statycznej. Pomiń znak, jeśli mapa nie zawiera wpisu, w przeciwnym razie dołącz zamiennik do StringBuilder.

Answer 2

Co można spróbować zrobić, zamiast używać wyrażeń regularnych, jest użycie Normalizer. Możesz znaleźć informacje na ten temat here.

Od tej strony:

import java.text.Normalizer; 
import java.text.Normalizer.Form; 

// ... 

public static String removeAccents(String text) { 
    return text == null ? null 
     : Normalizer.normalize(text, Form.NFD) 
      .replaceAll("\\p{InCombiningDiacriticalMarks}+", ""); 
} 

To nie rozwiązuje wszystkich potrzeb, ale działa na dość szerokiej gamy znaków. Zalecałbym jednak wykonanie pomiaru wydajności w celu porównania obu rozwiązań. Jeśli naprawdę chcesz skorzystać z rozwiązania regex, spróbuj najpierw utworzyć statyczne wzorce i potem użyj Matchera, więc otrzymasz tylko jeden rzut czasu na tworzenie tych wzorców.

Answer 3

Jeśli trzeba użyć wyrażenia regularnego, można precompile wzorców:

Map<Pattern, String> patterns = new HashMap<Pattern, String>(); 
{ // initializer block (you could do this in constructor also) 
    patterns.put(Pattern.compile("[ÁÀÂÄáàäaàáâãäå]") ,"a"); 
    rawString = rawString.replaceAll("æ","ae"); 
    // etc. 
} 

// later... 
for (Map.Entry<Pattern, String> e : patterns) { 
    rawString = e.getValue().matcher(rawString).replaceAll(e.getKey()); 
} 

Linia w pętli for jest kluczem. Oto rozwarstwienie:

• e.getValue() dostaje wzór z mapy kluczowego
• .matcher(rawString) dostaje Matcher obiektu do wzorca, aby dopasować wystąpień wyrażenia regularnego z danym ciągiem (surowe string)
• .replaceAll robót podobnie jak metody String (wierzę String wykorzystuje to, faktycznie)
• e.getKey() pobiera wartość zastępuje z mapy kluczowego

---

Odnośniki dla dalszego czytania:

• Pattern
• Matcher i sposób jej replaceAll
• Map.Entry