Szybsze parsowanie liczb na .NET

Question

Napisałem dwie funkcje, które konwertują ciąg liczb całkowitych rozdzielonych białymi znakami na tablicę int. Pierwsza funkcja wykorzystuje Substring a następnie stosuje System.Int32.Parse przekonwertować podciąg do wartości int:

let intsOfString (s: string) = 
    let ints = ResizeArray() 
    let rec inside i j = 
    if j = s.Length then 
     ints.Add(s.Substring(i, j-i) |> System.Int32.Parse) 
    else 
     let c = s.[j] 
     if '0' <= c && c <= '9' then 
     inside i (j+1) 
     else 
     ints.Add(s.Substring(i, j-i) |> System.Int32.Parse) 
     outside (j+1) 
    and outside i = 
    if i < s.Length then 
     let c = s.[i] 
     if '0' <= c && c <= '9' then 
     inside i (i+1) 
     else 
     outside (i+1) 
    outside 0 
    ints.ToArray() 

Druga funkcja przemierza znaków napisu w miejscu akumulowanie całkowitą bez tworzenia tymczasowego podciąg:

let intsOfString (s: string) = 
    let ints = ResizeArray() 
    let rec inside n i = 
    if i = s.Length then 
     ints.Add n 
    else 
     let c = s.[i] 
     if '0' <= c && c <= '9' then 
     inside (10*n + int c - 48) (i+1) 
     else 
     ints.Add n 
     outside(i+1) 
    and outside i = 
    if i < s.Length then 
     let c = s.[i] 
     if '0' <= c && c <= '9' then 
     inside (int c - 48) (i+1) 
     else 
     outside (i+1) 
    outside 0 
    ints.ToArray() 

Analiza porównawcza na liczbach całkowitych oddzielających spacją od 1 do 1 000 000, pierwsza wersja zajmuje 1,5 s, natomiast druga wersja to 0,3 s.

Parsowanie takich wartości może być krytyczne dla wydajności, więc pozostawienie 5x wydajności tabeli za pomocą tymczasowych podciągów może być niepożądane. Analizowanie liczb całkowitych jest łatwe, ale przetwarzanie innych wartości, takich jak liczby zmiennoprzecinkowe, dziesiętne i daty jest znacznie trudniejsze.

Czy istnieją wbudowane funkcje do analizowania bezpośrednio z podłańcucha w ciągu znaków (to znaczy przy użyciu podanego początku i długości ciągu znaków), aby uniknąć generowania tymczasowego ciągu znaków? Jeśli nie, czy są jakieś biblioteki, które zapewniają wydajne funkcje, aby to zrobić?

Answer 1

Nie wiem czy to jest dobry, ale czy próbowałeś coś takiego:

var stringValues = input.split(" "); 

var intValues = Array.ConvertAll(stringValues, s => int.Parse(s)); 

Answer 2

Pisałem to jedno za deblu, że nie tworzy tymczasowy podciąg. Jest przeznaczony do użycia w parserze JSON, więc ogranicza się do tego, w jaki sposób double może być reprezentowany w JSON zgodnie z http://www.json.org/.

Nie jest jeszcze optymalny, ponieważ wymaga podania informacji, gdzie zaczyna się i kończy numer (parametry begin i end), więc musisz dwukrotnie przemierzyć długość numeru, aby ustalić, gdzie się kończy. Jest nadal około 10-15 razy szybszy niż double.Parse i może być dość łatwo zmodyfikowany, aby znaleźć end wewnątrz funkcji, która jest następnie zwracana jako parametr out, aby wiedzieć, gdzie należy wznowić analizowanie głównego ciągu znaków.

Używane tak:

Parsers.TryParseDoubleFastStream("1", 0, 1, out j); 
Parsers.TryParseDoubleFastStream("2.0", 0, 3, out j); 
Parsers.TryParseDoubleFastStream("3.5", 0, 3, out j); 
Parsers.TryParseDoubleFastStream("-4.5", 0, 4, out j); 
Parsers.TryParseDoubleFastStream("50.06", 0, 5, out j); 
Parsers.TryParseDoubleFastStream("1000.65", 0, 7, out j); 
Parsers.TryParseDoubleFastStream("-10000.8600", 0, 11, out j); 

Kod można znaleźć tutaj:

https://gist.github.com/3010984 (byłaby zbyt długa, aby opublikować tutaj).

I StandardFunctions.IgnoreChar jest dla mojego celu proste:

public static bool IgnoreChar(char c) 
{ 
    return c < 33; 
} 

Answer 3

System.Int32.Parse jest slowlest, ponieważ wykorzystywane CultureInfo, FormatInfo i etc; a przyczyną wydajności nie są łańcuchy tymczasowe.

Kod z refleksji:

private unsafe static bool ParseNumber(ref char* str, NumberStyles options, ref Number.NumberBuffer number, NumberFormatInfo numfmt, bool parseDecimal) 
{ 
    number.scale = 0; 
    number.sign = false; 
    string text = null; 
    string text2 = null; 
    string str2 = null; 
    string str3 = null; 
    bool flag = false; 
    string str4; 
    string str5; 
    if ((options & NumberStyles.AllowCurrencySymbol) != NumberStyles.None) 
    { 
     text = numfmt.CurrencySymbol; 
     if (numfmt.ansiCurrencySymbol != null) 
     { 
      text2 = numfmt.ansiCurrencySymbol; 
     } 
     str2 = numfmt.NumberDecimalSeparator; 
     str3 = numfmt.NumberGroupSeparator; 
     str4 = numfmt.CurrencyDecimalSeparator; 
     str5 = numfmt.CurrencyGroupSeparator; 
     flag = true; 
    } 
    else 
    { 
     str4 = numfmt.NumberDecimalSeparator; 
     str5 = numfmt.NumberGroupSeparator; 
    } 
    int num = 0; 
    char* ptr = str; 
    char c = *ptr; 
    while (true) 
    { 
     if (!Number.IsWhite(c) || (options & NumberStyles.AllowLeadingWhite) == NumberStyles.None || ((num & 1) != 0 && ((num & 1) == 0 || ((num & 32) == 0 && numfmt.numberNegativePattern != 2)))) 
     { 
      bool flag2; 
      char* ptr2; 
      if ((flag2 = (((options & NumberStyles.AllowLeadingSign) == NumberStyles.None) ? false : ((num & 1) == 0))) && (ptr2 = Number.MatchChars(ptr, numfmt.positiveSign)) != null) 
      { 
       num |= 1; 
       ptr = ptr2 - (IntPtr)2/2; 
      } 
      else 
      { 
       if (flag2 && (ptr2 = Number.MatchChars(ptr, numfmt.negativeSign)) != null) 
       { 
        num |= 1; 
        number.sign = true; 
        ptr = ptr2 - (IntPtr)2/2; 
       } 
       else 
       { 
        if (c == '(' && (options & NumberStyles.AllowParentheses) != NumberStyles.None && (num & 1) == 0) 
        { 
         num |= 3; 
         number.sign = true; 
        } 
        else 
        { 
         if ((text == null || (ptr2 = Number.MatchChars(ptr, text)) == null) && (text2 == null || (ptr2 = Number.MatchChars(ptr, text2)) == null)) 
         { 
          break; 
         } 
         num |= 32; 
         text = null; 
         text2 = null; 
         ptr = ptr2 - (IntPtr)2/2; 
        } 
       } 
      } 
     } 
     c = *(ptr += (IntPtr)2/2); 
    } 
    int num2 = 0; 
    int num3 = 0; 
    while (true) 
    { 
     if ((c >= '0' && c <= '9') || ((options & NumberStyles.AllowHexSpecifier) != NumberStyles.None && ((c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F')))) 
     { 
      num |= 4; 
      if (c != '0' || (num & 8) != 0) 
      { 
       if (num2 < 50) 
       { 
        number.digits[(IntPtr)(num2++)] = c; 
        if (c != '0' || parseDecimal) 
        { 
         num3 = num2; 
        } 
       } 
       if ((num & 16) == 0) 
       { 
        number.scale++; 
       } 
       num |= 8; 
      } 
      else 
      { 
       if ((num & 16) != 0) 
       { 
        number.scale--; 
       } 
      } 
     } 
     else 
     { 
      char* ptr2; 
      if ((options & NumberStyles.AllowDecimalPoint) != NumberStyles.None && (num & 16) == 0 && ((ptr2 = Number.MatchChars(ptr, str4)) != null || (flag && (num & 32) == 0 && (ptr2 = Number.MatchChars(ptr, str2)) != null))) 
      { 
       num |= 16; 
       ptr = ptr2 - (IntPtr)2/2; 
      } 
      else 
      { 
       if ((options & NumberStyles.AllowThousands) == NumberStyles.None || (num & 4) == 0 || (num & 16) != 0 || ((ptr2 = Number.MatchChars(ptr, str5)) == null && (!flag || (num & 32) != 0 || (ptr2 = Number.MatchChars(ptr, str3)) == null))) 
       { 
        break; 
       } 
       ptr = ptr2 - (IntPtr)2/2; 
      } 
     } 
     c = *(ptr += (IntPtr)2/2); 
    } 
    bool flag3 = false; 
    number.precision = num3; 
    number.digits[(IntPtr)num3] = '\0'; 
    if ((num & 4) != 0) 
    { 
     if ((c == 'E' || c == 'e') && (options & NumberStyles.AllowExponent) != NumberStyles.None) 
     { 
      char* ptr3 = ptr; 
      c = *(ptr += (IntPtr)2/2); 
      char* ptr2; 
      if ((ptr2 = Number.MatchChars(ptr, numfmt.positiveSign)) != null) 
      { 
       c = *(ptr = ptr2); 
      } 
      else 
      { 
       if ((ptr2 = Number.MatchChars(ptr, numfmt.negativeSign)) != null) 
       { 
        c = *(ptr = ptr2); 
        flag3 = true; 
       } 
      } 
      if (c >= '0' && c <= '9') 
      { 
       int num4 = 0; 
       do 
       { 
        num4 = num4 * 10 + (int)(c - '0'); 
        c = *(ptr += (IntPtr)2/2); 
        if (num4 > 1000) 
        { 
         num4 = 9999; 
         while (c >= '0' && c <= '9') 
         { 
          c = *(ptr += (IntPtr)2/2); 
         } 
        } 
       } 
       while (c >= '0' && c <= '9'); 
       if (flag3) 
       { 
        num4 = -num4; 
       } 
       number.scale += num4; 
      } 
      else 
      { 
       ptr = ptr3; 
       c = *ptr; 
      } 
     } 
     while (true) 
     { 
      if (!Number.IsWhite(c) || (options & NumberStyles.AllowTrailingWhite) == NumberStyles.None) 
      { 
       bool flag2; 
       char* ptr2; 
       if ((flag2 = (((options & NumberStyles.AllowTrailingSign) == NumberStyles.None) ? false : ((num & 1) == 0))) && (ptr2 = Number.MatchChars(ptr, numfmt.positiveSign)) != null) 
       { 
        num |= 1; 
        ptr = ptr2 - (IntPtr)2/2; 
       } 
       else 
       { 
        if (flag2 && (ptr2 = Number.MatchChars(ptr, numfmt.negativeSign)) != null) 
        { 
         num |= 1; 
         number.sign = true; 
         ptr = ptr2 - (IntPtr)2/2; 
        } 
        else 
        { 
         if (c == ')' && (num & 2) != 0) 
         { 
          num &= -3; 
         } 
         else 
         { 
          if ((text == null || (ptr2 = Number.MatchChars(ptr, text)) == null) && (text2 == null || (ptr2 = Number.MatchChars(ptr, text2)) == null)) 
          { 
           break; 
          } 
          text = null; 
          text2 = null; 
          ptr = ptr2 - (IntPtr)2/2; 
         } 
        } 
       } 
      } 
      c = *(ptr += (IntPtr)2/2); 
     } 
     if ((num & 2) == 0) 
     { 
      if ((num & 8) == 0) 
      { 
       if (!parseDecimal) 
       { 
        number.scale = 0; 
       } 
       if ((num & 16) == 0) 
       { 
        number.sign = false; 
       } 
      } 
      str = ptr; 
      return true; 
     } 
    } 
    str = ptr; 
    return false; 
} 
public static int Parse(string s) 
{ 
    return Number.ParseInt32(s, NumberStyles.Integer, NumberFormatInfo.CurrentInfo); 
} 

internal unsafe static int ParseInt32(string s, NumberStyles style, NumberFormatInfo info) 
{ 
    byte* stackBuffer = stackalloc byte[1 * 114/1]; 
    Number.NumberBuffer numberBuffer = new Number.NumberBuffer(stackBuffer); 
    int result = 0; 
    Number.StringToNumber(s, style, ref numberBuffer, info, false); 
    if ((style & NumberStyles.AllowHexSpecifier) != NumberStyles.None) 
    { 
     if (!Number.HexNumberToInt32(ref numberBuffer, ref result)) 
     { 
      throw new OverflowException(Environment.GetResourceString("Overflow_Int32")); 
     } 
    } 
    else 
    { 
     if (!Number.NumberToInt32(ref numberBuffer, ref result)) 
     { 
      throw new OverflowException(Environment.GetResourceString("Overflow_Int32")); 
     } 
    } 
    return result; 
} 

private unsafe static void StringToNumber(string str, NumberStyles options, ref Number.NumberBuffer number, NumberFormatInfo info, bool parseDecimal) 
{ 
    if (str == null) 
    { 
     throw new ArgumentNullException("String"); 
    } 
    fixed (char* ptr = str) 
    { 
     char* ptr2 = ptr; 
     if (!Number.ParseNumber(ref ptr2, options, ref number, info, parseDecimal) || ((ptr2 - ptr/2)/2 < str.Length && !Number.TrailingZeros(str, (ptr2 - ptr/2)/2))) 
     { 
      throw new FormatException(Environment.GetResourceString("Format_InvalidString")); 
     } 
    } 
} 

Answer 4

Wklej cały ten kod w C# i zadzwoń Test(). Jest to tak blisko, jak można bezpośrednio operować na tablicy łańcuchów, aby analizować liczby za pomocą C#. Jest zbudowany z myślą o szybkości, a nie elegancji.Funkcja ParseInt i ParseFloat została stworzona dla silnika graficznego OpenGL do importowania wektorów z tekstowych modeli 3d. Parsowanie jest znaczącym wąskim gardłem w tym procesie. To było tak szybkie, jak tylko mogłem.

using System.Diagnostics; 

    private void Test() 
    { 
     Stopwatch sw = new Stopwatch(); 
     StringBuilder sb = new StringBuilder(); 
     int iterations = 1000; 

     // Build a string of 1000000 space separated numbers 
     for (var n = 0; n < iterations; n++) 
     { 
      if (n > 0) 
       sb.Append(' '); 
      sb.Append(n.ToString()); 
     } 

     string numberString = sb.ToString(); 

     // Time the process 
     sw.Start(); 
     StringToInts(numberString, iterations); 
     //StringToFloats(numberString, iterations); 
     sw.Stop(); 
     long proc1 = sw.ElapsedMilliseconds; 

     Console.WriteLine("iterations: {0} \t {1}ms", iterations, proc1); 
    } 

    private unsafe int[] StringToInts(string s, int length) 
    { 
     int[] ints = new int[length]; 
     int index = 0; 
     int startpos = 0; 

     fixed (char* pStringBuffer = s) 
     { 
      fixed (int* pIntBuffer = ints) 
      { 
       for (int n = 0; n < s.Length; n++) 
       { 
        if (s[n] == ' ' || n == s.Length - 1) 
        { 
         if (n == s.Length - 1) 
          n++; 
         // pIntBuffer[index++] = int.Parse(new string(pStringBuffer, startpos, n - startpos)); 
         pIntBuffer[index++] = ParseInt((pStringBuffer + startpos), n - startpos); 
         startpos = n + 1; 
        } 
       } 
      } 
     } 

     return ints; 
    } 

    private unsafe float[] StringToFloats(string s, int length) 
    { 
     float[] floats = new float[length]; 
     int index = 0; 
     int startpos = 0; 

     fixed (char* pStringBuffer = s) 
     { 
      fixed (float* pFloatBuffer = floats) 
      { 
       for (int n = 0; n < s.Length; n++) 
       { 
        if (s[n] == ' ' || n == s.Length - 1) 
        { 
         if (n == s.Length - 1) 
          n++; 

         pFloatBuffer[index++] = ParseFloat((pStringBuffer + startpos), n - startpos); // int.Parse(new string(pStringBuffer, startpos, n - startpos)); 
         startpos = n + 1; 
        } 
       } 
      } 
     } 

     return floats; 
    } 

    public static unsafe int ParseInt(char* input, int len) 
    { 
     int pos = 0;   // read pointer position 
     int part = 0;   // the current part (int, float and sci parts of the number) 
     bool neg = false;  // true if part is a negative number 

     int* ret = stackalloc int[1]; 

     while (pos < len && (*(input + pos) > '9' || *(input + pos) < '0') && *(input + pos) != '-') 
      pos++; 

     // sign 
     if (*(input + pos) == '-') 
     { 
      neg = true; 
      pos++; 
     } 

     // integer part 
     while (pos < len && !(input[pos] > '9' || input[pos] < '0')) 
      part = part * 10 + (input[pos++] - '0'); 

     *ret = neg ? (part * -1) : part; 
     return *ret; 
    } 

    public static unsafe float ParseFloat(char* input, int len) 
    { 
     //float ret = 0f;  // return value 
     int pos = 0;   // read pointer position 
     int part = 0;   // the current part (int, float and sci parts of the number) 
     bool neg = false;  // true if part is a negative number 

     float* ret = stackalloc float[1]; 

     // find start 
     while (pos < len && (input[pos] < '0' || input[pos] > '9') && input[pos] != '-' && input[pos] != '.') 
      pos++; 

     // sign 
     if (input[pos] == '-') 
     { 
      neg = true; 
      pos++; 
     } 

     // integer part 
     while (pos < len && !(input[pos] > '9' || input[pos] < '0')) 
      part = part * 10 + (input[pos++] - '0'); 

     *ret = neg ? (float)(part * -1) : (float)part; 

     // float part 
     if (pos < len && input[pos] == '.') 
     { 
      pos++; 
      double mul = 1; 
      part = 0; 

      while (pos < len && !(input[pos] > '9' || input[pos] < '0')) 
      { 
       part = part * 10 + (input[pos] - '0'); 
       mul *= 10; 
       pos++; 
      } 

      if (neg) 
       *ret -= (float)part/(float)mul; 
      else 
       *ret += (float)part/(float)mul; 

     } 

     // scientific part 
     if (pos < len && (input[pos] == 'e' || input[pos] == 'E')) 
     { 
      pos++; 
      neg = (input[pos] == '-'); pos++; 
      part = 0; 
      while (pos < len && !(input[pos] > '9' || input[pos] < '0')) 
      { 
       part = part * 10 + (input[pos++] - '0'); 
      } 

      if (neg) 
       *ret /= (float)Math.Pow(10d, (double)part); 
      else 
       *ret *= (float)Math.Pow(10d, (double)part); 
     } 

     return (float)*ret; 
    } 

Answer 5

Tak, są tam wbudowanych funkcji do analizy bezpośrednio z fragmentu ciągu znaków (tj stosując daną początek i długość łańcucha) w celu uniknięcia generowania tymczasowy ciąg? Jeśli nie, czy są jakieś biblioteki, które zapewniają wydajne funkcje, aby to zrobić?

Wydaje się, że chcesz użyć bufor Lexing i lexer, podobny do tego, co może zapewnić OCaml z ocamllex i buforem Lexbuf. (Nie mogę podać referencji dla F #.)

Jeśli twój benchmark obejmujący ogromny ciąg liczb całkowitych oddzielonych innymi tokenami to twój typowy przypadek, będzie dobrze działać. Ale w innych sytuacjach może to być niepraktyczne.