Wydajne parsowanie liczb całkowitych z podciągów w Javie

Question

AFAIK nie ma wydajnego sposobu w standardowych bibliotekach Java do parsowania liczby całkowitej z podłańcucha bez faktycznego tworzenia nowego łańcucha zawierającego podciąg.

Jestem w sytuacji, w której parsuję miliony liczb całkowitych z ciągów i nie chcę specjalnie tworzyć nowych ciągów dla każdego podciągu. Kopiowanie to obciążenie, którego nie potrzebuję.

Podając łańcuch s, chciałbym metody takie jak:

parseInteger(s, startOffset, endOffset) 

z semantyką jak:

Integer.parseInt(s.substring(startOffset, endOffset)) 

Teraz wiem, że mogę napisać to dość trywialnie tak:

public static int parse(String s, int start, int end) { 
    long result = 0; 
    boolean foundMinus = false; 

    while (start < end) { 
     char ch = s.charAt(start); 
     if (ch == ' ') 
      /* ok */; 
     else if (ch == '-') { 
      if (foundMinus) 
       throw new NumberFormatException(); 
      foundMinus = true; 
     } else if (ch < '0' || ch > '9') 
      throw new NumberFormatException(); 
     else 
      break; 
     ++start; 
    } 

    if (start == end) 
     throw new NumberFormatException(); 

    while (start < end) { 
     char ch = s.charAt(start); 
     if (ch < '0' || ch > '9') 
      break; 
     result = result * 10 + (int) ch - (int) '0'; 
     ++start; 
    } 

    while (start < end) { 
     char ch = s.charAt(start); 
     if (ch != ' ') 
      throw new NumberFormatException(); 
     ++start; 
    } 
    if (foundMinus) 
     result *= -1; 
    if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) 
     throw new NumberFormatException(); 
    return (int) result; 
} 

Ale nie o to chodzi. Wolałbym to zrobić ze sprawdzonej, obsługiwanej biblioteki firm trzecich. Na przykład parsowanie longów i radzenie sobie z Long.MIN_VALUE jest nieco subtelne, a ja oszukuję powyżej, analizując ints w longs. A powyższy problem nadal występuje, jeśli przeanalizowana liczba całkowita jest większa niż Long.MAX_VALUE.

Czy istnieje taka biblioteka?

Moje poszukiwania okazały się niewielkie.

Answer 1

Nie martw się zbytnio o obiekty, jeśli nie występują rzeczywiste problemy z wydajnością. Używaj aktualnej maszyny JVM, istnieją trwałe ulepszenia pod względem wydajności i obciążenia pamięci.

Można rzucić okiem na „ByteString” z buforów protokołów Google, jeśli chcesz mieć podciąg dzielenie pod spodem napis:

https://developers.google.com/protocol-buffers/docs/reference/java/com/google/protobuf/ByteString#substring%28int,%20int%29

Answer 2

Czy profilowaną swoją aplikację? Czy znalazłeś źródło swojego problemu?

Od Strings są niezmienne, istnieje duża szansa, że ​​wymagana jest bardzo mała pamięć i wykonano niewiele operacji w celu utworzenia podciągu.

Chyba że naprawdę masz problemy z pamięcią, usuwaniem śmieci itp., Po prostu użyj metody podciągania. Nie szukaj kompleksowych rozwiązań problemów, których nie masz.

Poza tym: jeśli zaimplementujesz coś samodzielnie, możesz stracić więcej, niż zyskujesz pod względem wydajności. Twój kod jest bardzo skomplikowany - jeśli chodzi o domyślną implementację, możesz być pewien, że jest stosunkowo szybki. I bezbłędnie.

Answer 3

nie mogłem się oprzeć, aby zmierzyć poprawę swojej metoda:

package test; 

public class TestIntParse { 

    static final int MAX_NUMBERS = 10000000; 
    static final int MAX_ITERATIONS = 100; 

    public static void main(String[] args) { 
     long timeAvoidNewStrings = 0; 
     long timeCreateNewStrings = 0; 

     for (int i = 0; i < MAX_ITERATIONS; i++) { 
      timeAvoidNewStrings += test(true); 
      timeCreateNewStrings += test(false); 
     } 

     System.out.println("Average time method 'AVOID new strings': " + (timeAvoidNewStrings/MAX_ITERATIONS) + " ms"); 
     System.out.println("Average time method 'CREATE new strings': " + (timeCreateNewStrings/MAX_ITERATIONS) + " ms"); 
    } 

    static long test(boolean avoidStringCreation) { 
     long start = System.currentTimeMillis(); 

     for (int i = 0; i < MAX_NUMBERS; i++) { 
      String value = Integer.toString((int) Math.random() * 100000); 
      int intValue = avoidStringCreation ? parse(value, 0, value.length()) : parse2(value, 0, value.length()); 
      String value2 = Integer.toString(intValue); 
      if (!value2.equals(value)) { 
       System.err.println("Error at iteration " + i + (avoidStringCreation ? " without" : " with") + " string creation: " + value + " != " + value2); 
      } 
     } 

     return System.currentTimeMillis() - start; 
    } 

    public static int parse2(String s, int start, int end) { 
     return Integer.valueOf(s.substring(start, end)); 
    } 

    public static int parse(String s, int start, int end) { 
     long result = 0; 
     boolean foundMinus = false; 

     while (start < end) { 
      char ch = s.charAt(start); 
      if (ch == ' ') 
       /* ok */; 
      else if (ch == '-') { 
       if (foundMinus) 
        throw new NumberFormatException(); 
       foundMinus = true; 
      } else if (ch < '0' || ch > '9') 
       throw new NumberFormatException(); 
      else 
       break; 
      ++start; 
     } 

     if (start == end) 
      throw new NumberFormatException(); 

     while (start < end) { 
      char ch = s.charAt(start); 
      if (ch < '0' || ch > '9') 
       break; 
      result = result * 10 + ch - '0'; 
      ++start; 
     } 

     while (start < end) { 
      char ch = s.charAt(start); 
      if (ch != ' ') 
       throw new NumberFormatException(); 
      ++start; 
     } 
     if (foundMinus) 
      result *= -1; 
     if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) 
      throw new NumberFormatException(); 
     return (int) result; 
    } 

} 

Efekty:

Average time method 'AVOID new strings': 432 ms 
Average time method 'CREATE new strings': 500 ms 

Twoja metoda jest mniej więcej 14% bardziej wydajne w czasie i rzekomo w pamięci, choć dość bardziej złożony (i podatny na błędy). Z mojego punktu widzenia twoje podejście się nie opłaca, ale może zrobić w twoim przypadku.