4

问题背景

我读了这个关于如何尽快反转字符串的问题。我发现其中一个答案是比较不同的方法。在其中之一中，他们只是运行一个循环，将位置元素与位置元素交换i，string.Length-1-i但他们通过 XOR 使用已知的棘手交换。我想知道与通过时间变量使用经典交换的相同方法相比，使用通过 XOR 的交换来反转字符串的速度有多快。令人惊讶的是，与 XOR 相比，我得到了近 50% 的改进。

问题

编译器是否在幕后做了一些神奇的事情，为什么我会得到这个结果？

带有基准的修改后的代码

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ContestLibrary
{
    public class Problem
    {
        delegate string StringDelegate(string s);

        static void Benchmark(string description, StringDelegate d, int times, string text)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int j = 0; j < times; j++)
            {
                d(text);
            }
            sw.Stop();
            Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times);
        }

        public static string ReverseXor(string s)
        {
            char[] charArray = s.ToCharArray();
            int len = s.Length - 1;

            for (int i = 0; i < len; i++, len--)
            {
                charArray[i] ^= charArray[len];
                charArray[len] ^= charArray[i];
                charArray[i] ^= charArray[len];
            }

            return new string(charArray);
        }

        public static string ReverseClassic(string s)
        {
            char[] charArray = s.ToCharArray();
            int len = s.Length-1;

            for (int i = 0; i < len; i++, len--)
            {
                char temp = charArray[len];
                charArray[len] = charArray[i];
                charArray[i] = temp;
            }
            return new string(charArray);
         }

        public static string StringOfLength(int length)
        {
            Random random = new Random();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < length; i++)
            {
                sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65))));
            }
            return sb.ToString();
        }

        static void Main(string[] args)
        {

            int[] lengths = new int[] {1,10,100,1000, 10000, 100000};

            foreach (int l in lengths)
            {
                int iterations = 10000;
                string text = StringOfLength(l);
                Benchmark(String.Format("Classic (Length: {0})", l), ReverseClassic, iterations, text);
                Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text);
                Console.WriteLine();    
            }
            Console.Read();
        }
    }
}
4

3 回答 3

4

原因很简单，让我们检查一下每个函数在 IL 代码中有多少个操作。但首先，让我们看看这两个函数在时间上的真正差异。你说 XOR 函数比另一个函数慢 50%，当我在 Debug 模式下运行代码时，我得到了结果，但是你必须在 Release 模式下运行代码才能完全让优化器完成它的工作:)。在释放模式下，XOR 函数几乎慢了 3 倍。

图片有 for 循环内部分的 IL 代码，这是唯一改变的部分。

第一张图是带有临时变量的函数

带有临时变量的经典代码

第二张图是带异或的函数

异或函数

如您所见，指令数量的差异很大，14 对 34。3 倍的时间差异来自一些操作，如conv.u2，它们有点昂贵。

于 2018-02-08T06:12:29.183 回答
2

我同意哈罗德的观点。XOR 交换并不比使用临时变量快。

我认为 XOR 交换的神话可以追溯到为新变量分配内存是一项耗时的工作的时代。

最初我认为这有可能与类型有关，并且也许在数组中使用 XOR 交换int会比在数组上产生更好的结果char，所以我在你的基准测试基础上构建了int仅用于文本的数组 - 轮流异或交换的相同结果（或多或少）int 只是比使用临时变量慢。

更新：

正如 Damien_The_Unbeliever 在他对您的问题的评论中所写的那样，R. Martinho Fernandes 在您链接到的问题中给出的答案实际上是第一页中正确反转字符串的唯一答案，即使使用英语以外的语言也是如此。
事实上，基于该答案和其中一个评论，我编写了一个扩展方法来正确反转字符串。

在我的母语（希伯来语）中，我们有各种点和符号来指定元音，而数组（或IEnumerable）的简单反转是错误的，就像在法语示例中一样。

它比基于常规交换的实现慢得多（并且比基于 XOR 的交换慢大约 10 倍），但我几乎不认为这会成为一个问题，因为反转字符串不是你经常做的事情，并且反转许多字符串一个紧密的循环甚至更少。
根据您的基准方法进行测试，使用此方法反转 10,000 个长度为 10,000 的字符串大约需要 13.5 秒。
如果有人会编写一个程序，实际上需要对如此长的字符串进行如此多的反向操作，我会感到非常惊讶。

所以这是我的国际安全字符串反向实现，我希望有人能从中受益：

public static string Reverse(this string source)
{
    if (string.IsNullOrEmpty(source))
    {
        return source;
    }
    var info = new StringInfo(source);
    var sb = new StringBuilder();

    for (int i = info.LengthInTextElements - 1; i > -1; i--)
    {
        sb.Append(info.SubstringByTextElements(i, 1));
    }
    return sb.ToString();
}
于 2018-01-10T05:37:53.490 回答
0

您可以使用 测试下面的代码Array.Reverse，它比您提到的其他方法更有效，Array.Reverse是本机编码的，维护和理解非常简单。

    public static string ReverseArray(string text)
    {
        if (text == null) return null;

        char[] array = text.ToCharArray();
        Array.Reverse(array);
        return new String(array);
    }

下面是一个完整的代码来演示，

委托字符串 StringDelegate(string s);

    static void Benchmark(string description, StringDelegate d, int times, string text)
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int j = 0; j < times; j++)
        {
            d(text);
        }
        sw.Stop();
        Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times);
    }

    public static string ReverseArray(string text)
    {
        if (text == null) return null;

        // this was posted by petebob as well 
        char[] array = text.ToCharArray();
        Array.Reverse(array);
        return new String(array);
    }

    public static string ReverseXor(string s)
    {
        char[] charArray = s.ToCharArray();
        int len = s.Length - 1;

        for (int i = 0; i < len; i++, len--)
        {
            charArray[i] ^= charArray[len];
            charArray[len] ^= charArray[i];
            charArray[i] ^= charArray[len];
        }

        return new string(charArray);
    }

    public static string ReverseClassic(string s)
    {
        char[] charArray = s.ToCharArray();
        int len = s.Length-1;

        for (int i = 0; i < len; i++, len--)
        {
            char temp = charArray[len];
            charArray[len] = charArray[i];
            charArray[i] = temp;
        }
        return new string(charArray);
    }

    public static string StringOfLength(int length)
    {
        Random random = new Random();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++)
        {
            sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65))));
        }
        return sb.ToString();
    }

    static void Main(string[] args)
    {

        int[] lengths = new int[] { 1, 10, 100, 1000, 10000, 100000 };

        foreach (int l in lengths)
        {
            int iterations = 10000;
            string text = StringOfLength(l);                
            Benchmark(String.Format("Classic (Length: {0})", l), ReverseClassic, iterations, text);
            Benchmark(String.Format("Array (Length: {0})", l), ReverseArray, iterations, text);
            Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text);
            Console.WriteLine();
        }
        Console.Read();
    }

注意：我已经更正了您用于反转字符串的代码，它没有正确反转字符串作为您的帖子

于 2018-01-10T05:25:12.917 回答