[探索 3 分鐘] 將字串內容反轉輸出, 效率型做法 (c#)

Question : 將字串內容反轉, 範例輸出入如下 (input → output)。

• abc → cba 
• 123 → 321

就是這麼簡單。一開始也沒想太多, 就是跑一個迴圈, 從尾巴開始讀每個字元, 用字串累加到頭就結束了。而且沒有遺忘連續字串相加要使用 StringBuilder, 因為效能考量。

public string ReverseByStringBuilder(string s)
{
    var sb = new StringBuilder();
    for (var i = s.Length - 1; i >= 0; --i)
        sb.Append(s[i]);
    return sb.ToString();
}

另一個版本行數差不多, 但使用 CharArray, 然後又用到 Array.Reverse 方法。

public string ReverseByArray(string s)
{
    char[] charArray = s.ToCharArray();
    Array.Reverse(charArray);
    return new string(charArray);
}

也查到 這一版, 直接用另外一個陣列, 把原來的值拷貝過來, 頭放尾, 尾放頭, 就少了 StringBuilder 類別的開銷了。

public string ReverseByCharBuffer(string s)
{
    char[] c = s.ToCharArray();
    for (int i = 0; i < s.Length / 2; ++i)
    {
        char t = s[i];
        c[i] = s[s.Length - i - 1];
        c[s.Length - i - 1] = t;
    }
    return new string(c);
}

現在好奇兩件事, 上面的執行效率各是如何 ? 最快的版本究竟快在哪裡 ? 跑個 100 萬次來試試。

結果如您想像嗎 ? Array.Reverse() 操作最快, 也就是上述 ReverseByArray() 版本, 比另外兩個版本快上 2.5~3.5 倍, 而直接不使用 StringBuilder 也快許多。翻 Array.Reverse 原始碼 查看, 原來有個隱藏的 native 函式: TrySZReverse(), 有興趣的同學, 就可以循這個線索繼續往下追。

[MethodImplAttribute(MethodImplOptions.InternalCall)]  
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
private static extern bool TrySZReverse(Array array, int index, int count); 

參考資料

• https://msdn.microsoft.com/zh-tw/library/d3877932(v=vs.110).aspx
• https://github.com/Microsoft/referencesource/blob/master/mscorlib/system/array.cs
• https://stackoverflow.com/questions/2930886/array-reverse-algorithm
• https://stackoverflow.com/questions/2866372/logic-behind-the-array-reverse-method
• http://www.cnblogs.com/kirinboy/archive/2010/04/23/reverse-a-string.html
• https://my.oschina.net/guanxinsui/blog/914188