2012-06-28 42 views
22

我已經寫了兩個將空白分隔的整數字符串轉換爲int數組的函數。所述第一函數使用Substring,然後應用System.Int32.Parse到串轉換爲int值:更快地解析.NET上的數字

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() 

第二功能橫穿就地累積整數字符串的字符而不創建臨時子:

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() 

空格分隔整數的基準測試1到1,000,000,第一個版本需要1.5s,而第二個版本需要0.3s。

解析這些值可能會影響性能,所以通過使用臨時子字符串在表上留下5倍的性能可能是不理想的。解析整數很簡單,但解析其他值(如浮點數,小數點和日期)則相當困難。

那麼,是否有內置函數直接從字符串中的子字符串解析(即使用給定的字符串的開始和長度)以避免生成臨時字符串?如果沒有,是否有任何庫提供了有效的功能來執行此操作?

+4

你有沒有嘗試過使用正則表達式而不是使用Substring?已編譯的正則表達式可能比字符串操作快得多 –

+3

@PanagiotisKanavos您能解釋一下如何使用正則表達式將字符串解析爲一個整數數組? –

+1

我最近有一個類似的問題,當我搜索時找不到任何東西,必須自己寫小數解析代碼。它不像你想象的那麼困難,因爲Decimal類有一個構造函數,它需要一個縮放因子,所以你可以做和整數解析幾乎一樣的東西,並且跟蹤小數點的位置。日期也不太困難,但是在兩種情況下,我都嚴格控制了格式。我不想寫一般的解析代碼... – MrKWatkins

回答

0

不知道這是什麼好,但你嘗試過這樣的:

var stringValues = input.split(" "); 

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

這會創建臨時字符串; OP不希望這樣... – MrKWatkins

+3

是的,這比慢速版慢,因爲您不僅分配了臨時字符串,還保留了對它們的引用,因此您需要爲寫障礙和GC撤離的成本付費他們來自幼兒園一代。 –

+0

問題似乎已經改變,包括一個F#實現......任何人都在意翻譯答案? – Paddy

5

我寫這一個雙打,不創建一個臨時串。它意味着在JSON解析器內部使用,因此它將自身限制爲根據http://www.json.org/在JSON中如何表示雙精度。

這不是最佳的但因爲它需要你知道在哪裏的數量開始和結束(beginend參數),所以你必須穿越數長度的兩倍,找出它的盡頭。它仍然比double.Parse快大約10-15倍,並且它可以很容易地修改,它在函數內部找到end,然後返回out參數以知道您必須恢復解析主字符串的位置。

使用像這樣:

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); 

代碼可以在這裏找到:

https://gist.github.com/3010984(會過於冗長,張貼在這裏)。

而且StandardFunctions.IgnoreChar是我的目的就這麼簡單:

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

System.Int32.Parse是slowlest,因爲它使用CultureInfoFormatInfo和等;性能原因不在臨時字符串中。從反射

代碼:

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")); 
     } 
    } 
} 
+0

有趣。 @JonHarrop應該測量在substring版本上使用他更簡單的int解析器的性能,以確保5x的根本原因被完全理解。 – fmr

+0

這可能是兩個。在類似的情況下,我從自定義整數解析中獲得了性能上的提升(因爲我可以假設一種格式),並且不會削減我的輸入字符串。 – MrKWatkins

+0

@fmr「@JonHarrop應該測量在substring版本上使用他更簡單的int解析器的性能,只是爲了確保5x的根本原因被完全理解」。拆分爲子字符串需要0.7s。拆分爲子字符串並將我的fast int解析器映射到它們需要0.99s。儘管如此,還有其他的力量在工作。 –

4

所有這些代碼粘貼到C#和呼叫Test()。這與您可以直接在字符串數組上操作以使用C#解析數字的方式相近。它是爲速度而建造的,而不是優雅的。爲OpenGL圖形引擎創建了ParseIntParseFloat函數,以便從基於文本的3d模型中導入矢量。解析花車是該過程中的一個重要瓶頸。這是我能做到的最快速度。

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; 
    } 
+3

對於那些誰在谷歌發現了這一點,儘管這是選擇的解決方案,測試強調了這種種問題: StringToFloats調用parseInt函數,而不是ParseFloat,總是忽略了字符串的最後一個號碼,崩潰,如果你指定比數字少在字符串中。 ParseFloat經常產生非常不正確的數字,因爲mul溢出並變得無意義。例如「0.000167039223」被解析爲0.0011846202。 ParseFloat因各種其他數字而失去精度,因爲中間體被保存爲無法精確保存它們的浮點數。 – user495625

+1

@ user495625我繼續前進,沒有說明ParseFloat函數,因爲它產生的結果不穩定並且精度更高。答案是將「mul」變量從int更改爲double。函數的精度現在是10位小數。我不打算讓它的其餘部分保持不變,因爲它會失去它的說明性用處。我希望你能爲這個答案提供幫助。保重。 – drankin2112

+0

@ drankin2112我注意到,這仍然修剪輸入字符串的最後一位數字,有沒有解決方法?我也試圖使用這個片段來加載模型。 – Krythic

1

那麼,還有內置函數直接從一個子串,以避免產生臨時 串(使用給定的開始和一個字符串的長度,即 )在字符串內解析?如果沒有,是否有任何庫提供了有效的功能來執行此操作?

看來你想使用一個詞法緩衝和詞法分析器,類似於OCaml中可以ocamllexLexbuf緩衝區提供。 (我不能提供F#的參考。)

如果您的基準測試涉及由其他令牌分隔的大量整數字符串是您的典型案例,那麼它將運行良好。但在其他情況下,這可能是不切實際的。

+0

@ user2314737你是什麼意思?我沒有寫一個問題! – user40989

+0

不是。 Lexing會將每個包含int的子字符串複製到它自己的字符串中。我仍然需要將這些字符串解析爲實際的整數... –

+0

@JonHarrop你當然是對的。那時我沒有喝茶。 – user40989