基准测试性能字符串算法 .NET C#

高效算法用于修剪字符串中的空白字符

DrABELL

4.98/5 (22投票s)

2015年8月1日

CPOL

6分钟阅读

82392

这是“.NET 中修剪字符串所有空白字符的最快方法”的替代方案

引言

本文描述了几种算法解决方案，用于修剪字符串内的空白字符，或将空白字符序列减少为单个空白字符。

空白字符与空格：重要说明

“空白字符”一词不应与“空格”（即 ASCII 32 或 Unicode U+0020 的空格符号）混淆 [1]。空白字符代表一个更广泛的类别，还包括换行符、制表符、回车符等 [1]。本文提供了通用的解决方案来修剪（或减少）所有字符串内的空白字符，以及几种适用于空格的算法，这些空格被选为最常见的实际示例。同样的原理和算法解决方案也可以应用于其他空白字符。

对 String.Trim() 方法的扩展

标准的 .NET/C# 库包含 Trim()、TrimStart() 和 TrimEnd() 方法，允许剥离前导/尾部或所有空白字符，但没有能够修剪字符串内部空白字符的方法。提出的解决方案扩展了标准功能，允许修剪字符串内部的空白字符（对应于新引入的 TrimWithin() 方法），或将空白字符序列减少为单个空白字符（另一个新增的 TrimWithin2one() 方法）。为了找到最高效的算法解决方案，我们测试/基准测试了多种编码技术。到目前为止，基于字符串到字符数组转换的两种算法 [5...7] 被发现是最有效的（参见列表 1 和 2），推荐用于实际使用。其他算法主要出于教学目的列出。

安全代码

提出的解决方案实现了安全/托管代码库，因此不包含任何指针算术和/或任何底层函数 API 调用。值得一提的是，不安全代码可能会显示一些边际性能改进（参见 [5] 中的讨论），但根据定义，它是“不安全”的，因此不推荐使用。

性能估算：样本测试结果

在本地 PC（i3 Core Duo 3220 w/Kingston HyperX 1600MHz DDR3）上使用以下多语言 Unicode 测试字符串（故意添加了多个空格）进行的样本测试，性能基准测试估算如下（注意：突出显示的算法 1 和 2 表现最佳，即推荐使用）：

测试字符串

MY WAY OR WIFI ! VERSTEHEN, АННА ? ХОРОШО ГРАФ, BAZAARU НЕТ ! Εντάξει !

修剪所有字符串内的空白字符（结果字符串）

MYWAYORWIFI!VERSTEHEN,АННА?ХОРОШОГРАФ,BAZAARUНЕТ!Εντάξει!

将字符串内的空白字符序列减少为单个（结果字符串）

MY WAY OR WIFI ! VERSTEHEN, АННА ? ХОРОШО ГРАФ, BAZAARU НЕТ ! Εντάξει !

基准测试

算法		运行时长，μs	已用时间，ms	迭代次数	注释
1).	TrimWithin	0.9	942	1,000,000	修剪字符串内的空白字符
2).	TrimWithin2one	1.2	1,224	1,000,000	将字符串内的空白字符减少为 1
3).	String.Replace 方法	1.3	1,314	1,000,000	修剪字符串内的空格
4).	String Split/Concat 算法	1.4	1,371	1,000,000	修剪字符串内的空格
5).	String Split/Join 算法	1.4	1,366	1,000,000	修剪字符串内的空格
6).	Trim2one 算法	1.8	1,817	1,000,000	将字符串内的空格减少为 1

背景

本文 [1] 受到 Felipe R. Machado 发布的《.NET 中修剪字符串所有空白字符的最快方法》[2] 这篇原创文章的启发。其中一些算法仅出于“学术”兴趣包含在内，实际价值有限，性能表现很差（即基于 Regex 和 Linq 的算法）；因此，它们不包含在目前的考虑范围内。以下代码片段允许基于以下编码技术对不同算法进行准确的基准测试：

字符串转字符数组和字符数组转字符串技术（最快/推荐）
Chris Maunder 建议的 String.Replace() 方法
原始文章 [2] 中包含的 String.Split() 结合 String.Join()
根据 [4] 的 String.Split() 结合 String.Concat()

使用代码

列表 1 包含与最高效（迄今为止）的字符串内部空白字符 TrimWithin() 算法及其相应基准测试相关的代码片段。它可以与标准的 Trim() 或 TrimStart() 方法结合使用，以删除前导空白字符。

列表 1：TrimWithin() 方法，用于修剪任何 Unicode/ASCII 字符串中的所有字符串内部空白字符

        #region TrimWithin() Algo/Benchmark
        /// <summary>
        /// Trim out all in-string White Spaces using String-to-Char[] conversion
        /// </summary>
        /// <param name="InputString">string</param>
        /// <returns>string</returns>
        public string TrimWithin(string InputString)
        {
            char[] _arInput;
            char[] _arBuffer;
            string _result = String.Empty;
            try
            {
                // basic input validation: cannot be null, empty or white space
                if (String.IsNullOrEmpty(InputString) || String.IsNullOrWhiteSpace(InputString) )
                { throw new ArgumentNullException("Empty String"); }

                // get char[] from InputString
                _arInput = InputString.ToCharArray();

                // create buffer char[] array to populate without white spaces
                _arBuffer = new char[_arInput.Length];

                // set initial index of buffer array
                int _idx = 0;

                // iterate through input array _arInput
                // and populate buffer array excluding white spaces 
                for (int i = 0; i < _arInput.Length; i++)
                {
                    if (!Char.IsWhiteSpace(_arInput[i]))
                    {
                        _arBuffer[_idx] = (_arInput[i]);
                        _idx++;
                    }
                }

                // convert buffer Char[] into string and return
                return new String(_arBuffer, 0, _idx);
            }
            catch { throw; }
            finally { _arInput = null; _arBuffer = null; }
        }

        /// <summary>
        /// Trim all in-string White Spaces using String-to-Char[] - Benchmark
        /// Re: Ayoola-Bell Toggle Case Algorithm
        /// https://codeproject.org.cn/Tips/160799/How-to-Toggle-String-Case-in-NET
        /// </summary>
        /// <param name="InputString">string</param>
        /// <returns>string</returns>
        public double TrimWithinBenchmark(string InputString,
                                          Int64 LoopCounter)
        {
            // result string
            string _result = String.Empty;

            // stopwatch obj (ref: System.Diagnostics)
            Stopwatch _sw = new Stopwatch();

            // start count ticks
            _sw.Start();

            // trim using String-to-Char[] and String (Char[]) conversions
            for (Int64 i = 0; i < LoopCounter; ++i)
            {
                char[] _arInput = InputString.ToCharArray();
                char[] _arBuffer = new char[_arInput.Length];

                // set initial index of buffer array
                int _idx = 0;

                // iterate through input array _arInput
                // and populate buffer array excluding white spaces 
                for (int j = 0; j < _arInput.Length; j++)
                {
                    // populate buffer array excluding white spaces
                    if (!Char.IsWhiteSpace(_arInput[j])) 
                    { 
                        _arBuffer[_idx] = (_arInput[j]); 
                        _idx++; 
                    }
                }
                _result = (new String(_arBuffer, 0, _idx));
            }
            // stop count
            _sw.Stop();

            // duration measured in ticks
            Int64 _ticks = _sw.ElapsedTicks;

            // duration in msec (rounded)
            return Math.Round(TicksToMillisecond(_ticks), 2);
        }
        #endregion

列表 2（如下所示）包含与最高效（迄今为止）的字符串内部空白字符 TrimWithin2one() 算法及其相应基准测试相关的代码片段。该算法将任何字符串内的相同空白字符序列减少为一个。它也可以与标准的 Trim() 方法结合使用，以删除前导/尾部空白字符。

重要澄清：CP 会员 Alexander Chernosvitov 在评论线程中提出了另一个算法，它实现了不同的逻辑，即：将任何空白字符序列修剪到序列中的第一个，因此对于 5 个空格后跟 5 个制表符的序列，下面的算法将产生一个空格和一个制表符，而提出的替代方案将只产生一个空格，忽略制表符。

列表 2：TrimWithin2one() 方法，用于将字符串内部空白字符序列减少为单个

      #region TrimWithin2one
        /// <summary>
        /// Reduce in-string White Spaces sequences to a single one
        /// </summary>
        /// <param name="InputString">string</param>
        /// <returns>string</returns>
        public string TrimWithin2one(string InputString)
        {
            char[] _arInput;
            char[] _arBuffer;
            string _result = String.Empty;
            try
            {
                // basic input validation: cannot be null, empty or white space
                if (String.IsNullOrEmpty(InputString) || String.IsNullOrWhiteSpace(InputString) )
                { throw new ArgumentNullException("Empty String"); }
                
                // get Char[] from input string
                _arInput = InputString.ToCharArray();

                // create buffer array
                _arBuffer = new char[_arInput.Length];

                // insert first element from  input array into buffer
                _arBuffer[0] = _arInput[0];

                // set initial index of buffer array
                int _idx = 1;

                // iterate through input array starting from 2nd element
                // and populate buffer array reducing amount of white spaces 
                for (int i = 1; i < _arInput.Length; i++)
                {
                    if (!Char.IsWhiteSpace(_arInput[i]) ||
                        (Char.IsWhiteSpace(_arInput[i]) && _arInput[i] != _arBuffer[_idx - 1]))
                    { _arBuffer[_idx] = (_arInput[i]); _idx++; }
                }

                // convert buffer array into string to return
                return new String(_arBuffer, 0, _idx);
            }
            catch { throw; }
            finally { _arInput = null; _arBuffer = null; }
        }

        /// <summary>
        /// Reduce in-string White Spaces sequence to a single one: Benchmark
        /// </summary>
        /// <param name="InputString">string</param>
        /// <returns>string</returns>
        public double TrimWithin2oneBenchmark(string InputString,
                                              Int64 LoopCounter)
        {
            // result string
            string _result = String.Empty;
            
            // stopwatch obj (ref: System.Diagnostics)
            Stopwatch _sw = new Stopwatch();
            
            // start count ticks
            _sw.Start();

            // trim using String-to-Char[] conversion
            for (Int64 i = 0; i < LoopCounter; ++i)
            {
                char[] _arChars = InputString.ToCharArray();
                char[] _buffer = new char[_arChars.Length];
                _buffer[0] = _arChars[0];
                int pos = 1;
                for (int j = 1; j < _arChars.Length; j++)
                {
                    if (!Char.IsWhiteSpace(_arChars[j]) || 
                       (Char.IsWhiteSpace(_arChars[j]) && _arChars[j] != _buffer[pos-1] )) 
                       { _buffer[pos] = (_arChars[j]); pos++; }
                }
                _result = (new String(_buffer, 0, pos));
            }
            // stop count
            _sw.Stop();

            // duration measured in ticks
            Int64 _ticks = _sw.ElapsedTicks;

            // duration in msec (rounded)
            return Math.Round(TicksToMillisecond(_ticks), 2);
        }
        #endregion

关注点

以下代码片段包含了三个 .NET/C# 托管代码中的空格修剪算法，主要出于教学目的。

列表 3：修剪所有空格的算法

//******************************************************************************
// Module           :   TrimString.cs
// Description      :   Trim White Space Algorithm benchcmarks
//******************************************************************************
// Author           :   Alexander Bell
// Date             :   08/01/2015
//******************************************************************************
// DISCLAIMER: This Application is provide on AS IS basis without any warranty
//******************************************************************************
using System;
using System.Diagnostics;

namespace StringOp
{
    public class StringTrim
    {
        #region TrimUsingReplace
        /// <summary>
        /// Trim White Spaces using String.Replace method
        /// </summary>
        /// <param name="InputString">string</param>
        /// <param name="OldString">string</param>
        /// <param name="NewString">string</param>
        /// <param name="LoopCounter">Int64</param>
        /// <returns>double</returns>
        public double TrimUsingReplace(string InputString, 
                                        string OldString, 
                                        string NewString, 
                                        Int64 LoopCounter)
        {
            // result string
            string _result = String.Empty;

            // stopwatch obj (ref: System.Diagnostics)
            Stopwatch _sw = new Stopwatch();

            // start count ticks
            _sw.Start();

            // trim using String.Replace
            for (Int64 i = 0; i < LoopCounter; ++i)
            {
                _result=InputString.Replace(OldString, NewString);
            }

            // stop count
            _sw.Stop();

            // duration measured in ticks
            Int64 _ticks = _sw.ElapsedTicks;

            // duration in msec (rounded)
            return Math.Round(TicksToMillisecond(_ticks), 2);
        }
        #endregion

        #region TrimUsingSplitJoin
        /// <summary>
        /// Trim White Spaces using String Split/Join methods
        /// </summary>
        /// <param name="InputString">string</param>
        /// <param name="Separator">string</param>
        /// <param name="LoopCounter">Int64</param>
        /// <returns>double</returns>
        public double TrimUsingSplitJoin(string InputString, 
                                        string Separator, 
                                        Int64 LoopCounter)
        {
            // result string
            string _result = String.Empty;

            // stopwatch obj (ref: System.Diagnostics)
            Stopwatch _sw = new Stopwatch();

            // start count ticks
            _sw.Start();

            // trim using String Split/Join
            for (Int64 i = 0; i < LoopCounter; ++i)
            {
                _result = String.Join(String.Empty,InputString.Split(new string[]{Separator}, 
                    StringSplitOptions.RemoveEmptyEntries));
            }

            // stop count
            _sw.Stop();

            // duration measured in ticks
            Int64 _ticks = _sw.ElapsedTicks;

            // duration in msec (rounded)
            return Math.Round(TicksToMillisecond(_ticks), 2);
        }
        #endregion

        #region TrimUsingSplitConcat
        /// <summary>
        /// Trim White Spaces using String Split/Concat methods
        /// </summary>
        /// <param name="InputString"></param>
        /// <param name="Separator"></param>
        /// <param name="LoopCounter">Int64</param>
        /// <returns>double</returns>
        public double TrimUsingSplitConcat(string InputString, 
                                           string Separator, 
                                            Int64 LoopCounter)
        {
            // result string
            string _result = String.Empty;

            // stopwatch obj (ref: System.Diagnostics)
            Stopwatch _sw = new Stopwatch();

            // start count ticks
            _sw.Start();

            // trim using String Split/Concat
            for (Int64 i = 0; i < LoopCounter; ++i)
            {
                _result = String.Concat(InputString.Split(new string[] { Separator }, 
                    StringSplitOptions.RemoveEmptyEntries));
            }

            // stop count
            _sw.Stop();

            // duration measured in ticks
            Int64 _ticks = _sw.ElapsedTicks;

            // duration in msec (rounded)
            return Math.Round(TicksToMillisecond(_ticks), 2);
        }
        #endregion

        /// <summary>
        /// Ticks-to-ms
        /// </summary>
        /// <param name="Ticks">Int64</param>
        /// <returns>double</returns>
        internal double TicksToMillisecond(Int64 Ticks)
        {
            // msec per tick (stopwatch frequency in kHz)
            double _msPerTick = (double)1000 / Stopwatch.Frequency;

            // duration in msec
            return Ticks * _msPerTick;
        }
    }
}

测试网站 [2] 提供了与每个算法相关的数值性能估算（基准测试）。输入任意文本，从下拉列表中选择迭代次数，然后单击 TRIM 按钮即可获得基准测试估算。Unicode 没问题，但请将文本限制在 nvarchar(100) 以内。谢谢！:)

将 N 个连续空格折叠成一个使用 STRING.REPLACE

列表 4：将最多 14 个连续空格修剪成 1 个

        #region Trim2one
        /// <summary>
        /// Benchmark: 
        /// Algo to Trim up to 14 consequitive white spaces into 1
        /// </summary>
        /// <param name="InputString">string</param>
        /// <param name="LoopCounter">Int64</param>
        /// <returns>double</returns>
        public double Trim2oneBenchmark(string InputString,
                                        Int64 LoopCounter)
        {
            const string _whiteSpc1 = " ";
            string _whiteSpc2 = _whiteSpc1 + _whiteSpc1;
            string _whiteSpc3 = _whiteSpc2 + _whiteSpc1;
            string _whiteSpc4 = _whiteSpc3 + _whiteSpc1;
            string _whiteSpc8 = _whiteSpc4 + _whiteSpc4;

            // result string
            string _result = String.Empty;

            // stopwatch obj (ref: System.Diagnostics)
            Stopwatch _sw = new Stopwatch();

            // start count ticks
            _sw.Start();

            // trim using String.Replace
            for (Int64 i = 0; i < LoopCounter; ++i)
            {
                _result= InputString.Replace(_whiteSpc8, _whiteSpc1).
                                     Replace(_whiteSpc4, _whiteSpc1).
                                     Replace(_whiteSpc3, _whiteSpc1).
                                     Replace(_whiteSpc2, _whiteSpc1);
            }

            // stop count
            _sw.Stop();

            // duration measured in ticks
            Int64 _ticks = _sw.ElapsedTicks;

            // duration in msec (rounded)
            return Math.Round(TicksToMillisecond(_ticks), 2);
        }

        /// <summary>
        /// Trim up to 14 consequitive white spaces into 1
        /// </summary>
        /// <param name="InputString">string</param>
        /// <returns>string</returns>
        public string Trim2one(string InputString)
        {
            const string _whiteSpc1 = " ";
            string _whiteSpc2 = _whiteSpc1 + _whiteSpc1;
            string _whiteSpc3 = _whiteSpc2 + _whiteSpc1;
            string _whiteSpc4 = _whiteSpc3 + _whiteSpc1;
            string _whiteSpc8 = _whiteSpc4 + _whiteSpc4;

            return InputString.Replace(_whiteSpc8, _whiteSpc1).
                               Replace(_whiteSpc4, _whiteSpc1).
                               Replace(_whiteSpc3, _whiteSpc1).
                               Replace(_whiteSpc2, _whiteSpc1);
        }
        #endregion

注意：列表 5 中包含的代码片段实现了下面显示的字符串组合，目的是为了教学（提高可读性）并避免输入长字符串空格时出错。

列表 4a：由变量组成的空格序列

            const string _whiteSpc1 = " ";
            string _whiteSpc2 = _whiteSpc1 + _whiteSpc1;
            string _whiteSpc3 = _whiteSpc2 + _whiteSpc1;
            string _whiteSpc4 = _whiteSpc3 + _whiteSpc1;
            string _whiteSpc8 = _whiteSpc4 + _whiteSpc4;

在生产版本中，通过用 const 替换 string vars（如评论中提到的）可以实现一些性能改进。

列表 4b. 包含空格序列的字符串常量（1, 2, 3, 4, 8）

            const string _whiteSpc1 = " ";
            const string _whiteSpc2 = "  ";
            const string _whiteSpc3 = "   ";
            const string _whiteSpc4 = "    ";
            // etc.

该算法将使用 String.Replace() 方法将最多 14 个连续空格修剪成一个。为了更好地理解此算法背后的逻辑，请参阅以下转换图，该图演示了空格减少过程。

使用 String.Replace() 方法的空白字符减少算法

第一次 Replace(8->1)，空白字符减少
2->2
3->3
4->4
5->5
6->6
7->7
8->1 (完成)
9->2
10->3
11->4
12->5
13->6
14->7

第二次 Replace(4->1)，空白字符减少
2->2
3->3
4->1 (完成)
5->2
6->3
7->4
8->1 (完成)
9->2
10->3
11->1 (完成)
12->2
13->3
14->4

第三次 Replace(3->1)，空白字符减少
2->2
3->1 (完成)
4->1 (完成)
5->2
6->1 (完成)
7->2
8->1 (完成)
9->2
10->1 (完成)
11->1 (完成)
12->2
13->1 (完成)
14->2

第四次 Replace(2->1)，空白字符减少
2->1 (完成)
3->1 (完成)
4->1 (完成)
5->1 (完成)
6->1 (完成)
7->1 (完成)
8->1 (完成)
9->1 (完成)
10->1 (完成)
11->1 (完成)
12->1 (完成)
13->1 (完成)
14->1 (完成)

此算法解决方案可以进一步扩展，适用于任何 N 个连续的空格。

历史

原创文章发布 [1]
此替代版本发布
添加了 Trim2one 算法
使用 String-toChar[] 算法添加了修剪所有空白字符
使用 String-toChar[] 算法添加了将所有空白字符减少为 1
文章结构重组，代码库/基准测试更新

参考文献