如何用 C 寫乙個高效的 String Split 方法？

1樓：

僅說Split這件事請需要做這麼兩件事情：

找到位置

形成新的string

現在底層實現為 dotnet/corefx

Creates an array of strings by splitting this string at eachoccurrence of a separator. The separator is searched for, and if foundthe substring preceding the occurrence is stored as the first element inthe array of strings. We then continue in this manner by searchingthe substring that follows the occurrence.

On the other hand, if the separatoris not found, the array of strings will contain this instance as its only elementIf the separator is nullwhitespace (i.e., Character.

IsWhitespace) is used as the separatorpublic string Split(params char? separatorreturn SplitInternal(separator, int.MaxValue, StringSplitOptions.

None

而SplitInternal方法

private string SplitInternal(ReadOnlySpan separators, int count, StringSplitOptions optionsif (count < 0throw new ArgumentOutOfRangeException(nameof(countSR.ArgumentOutOfRange_NegativeCountif (options < StringSplitOptions.None || options > StringSplitOptions.

RemoveEmptyEntriesthrow new ArgumentException(SR.Format(SR.Arg_EnumIllegalVal, optionsbool omitEmptyEntries = (options == StringSplitOptions.

RemoveEmptyEntriesif ((count == 0) || (omitEmptyEntries && Length == 0return Array.Emptyif (count == 1return new string { thisvar sepListBuilder = new ValueListBuilder(stackalloc int[StackallocIntBufferSizeLimitMakeSeparatorList(separators, ref sepListBuilderReadOnlySpan sepList = sepListBuilder.AsSpanHandle the special case of no replacesif (sepList.

Length == 0return new string { thisstring result = omitEmptyEntriesSplitOmitEmptyEntries(sepList, default, 1, countSplitKeepEmptyEntries(sepList, default, 1, countsepListBuilder.Disposereturn result

可以發現其用

MakeSeparatorList(separators, ref sepListBuilder);

來尋找位置

用string result = omitEmptyEntriesSplitOmitEmptyEntries(sepList, default, 1, countSplitKeepEmptyEntries(sepList, default, 1, count);

來進行分割

查詢位置其實是個挺簡單的思路時間複雜度O(n);

private string SplitKeepEmptyEntries(ReadOnlySpan sepList, ReadOnlySpan lengthList, int defaultLength, int countDebug.Assert(count >= 2int currIndex = 0int arrIndex = 0countint numActualReplaces = (sepList.Length < count) ?

sepList.Length : countAllocate space for the new array1 for the string from the end of the last replace to the end of the stringstring splitStrings = new string[numActualReplaces + 1for (int i = 0; i < numActualReplaces && currIndex < Length; isplitStrings[arrIndex++] = Substring(currIndex, sepList[i] - currIndexcurrIndex = sepList[i] + (lengthList.

IsEmpty ? defaultLength : lengthList[iHandle the last string at the end of the array if there is oneif (currIndex < Length && numActualReplaces >= 0splitStrings[arrIndex] = Substring(currIndexelse if (arrIndex == numActualReplacesWe had a separator character at the end of a string.

Rather than just allowinga null character, we'll replace the last element in the array with an empty stringsplitStrings[arrIndex] = string.Emptyreturn splitStrings

切割也是乙個O(n).

如果說是非想提效的話：

採用併發技術並行尋找位置

只支援某些特殊的分隔符內部做索引的冗餘可以將O(n)變為O(1)

2樓：

你這是瞎優化，看到某個地方佔cpu百分比高就不爽。這是入門小白的標準情況。

你應該看的是實際占用時間而不是百分比。如果乙個演算法執行只用 0.1ms，就算佔了100% cpu又如何？需要優化嗎？

其次是要找出關鍵的效能瓶頸，而且需要看你專案的需求。你tm要是個每天在後台慢慢跑的檢測程式，要那麼高的效能幹嘛？

cpu占用只是個參考。

3樓：liangshiwei

這幾天問json，現在問Split。天天瞎造輪子，乙個成熟的輪子不僅是效能上，完整大量的測試才是最重要的。

在你造出輪子後，要有把握所有的場景都不會出問題。

4樓：Ben Lampson

你的問題就是佔了cpu了麼，那另外乙個角度回答就是你想把這事交給記憶體嘛。

字串有多長呢。一次遍歷能搞定不。這就結了呀。

答案出來了呀。

5樓：「已登出」

1.單純豎線分割，沒頭沒尾沒轉義，泛用性約等於0。

2.Split()分完了再遍歷，效率非常之低。Split的原理是吧乙個字串每一部分擷取出來變成一堆新字串，也就是說你至少需要遍歷兩次才能完成這個查詢。

如果想快你需要自己實現Split，一邊分割一邊遍歷，時間能減少很多。

3.你確定能有四倍？你考慮你這個玩意發數字的時候你接到的其實是字串，你還需要把這個字串轉換成數字了嗎？JSON裡這個功能可是直接做好了的。

4.都是keyvalue形式了，你敢用兩個不同的符號分割嗎？除錯的時候你這段訊息拿出來根本看不出來哪個是key那個是value啊！

6樓：

但我認為在許多場景中，其實不需要用到這麼複雜的文字格式你認為錯了。

大多數場景，都比你這複雜。

說句有點刻薄的話，你寫的東西在絕大多數場景中，沒有使用價值，而且根本和JSON沒有一點關係。

7樓：吳優

前幾天剛寫了乙個，用了.net core2.1的span類，解析json到ast已經實現了，反射建立物件沒啥興趣就沒仔細寫了，你對比下效能怎麼樣

8樓：魚與熊掌

令人絕望的 "|" 分隔符。(能這麼寫的我覺得都是新手程式設計師

你有沒有想過，如果值或者key裡面有| 那這個序列化不就壞了。

如何用 C 寫乙個高效的 String Split 方法？

如何用C 列印乙個菱形

如何用C語言畫乙個蘑菇？

如何用jQuery自己寫乙個Vue？

其他用戶還看了：