不变性是否会导致性能问题？

Question

我刚刚进入函数式编程并试图理解何时应该使类/属性变得可变.

使用大量字符串连接时,我们知道最好使用StringBuilder,例如:

using System;
using System.Diagnostics;
using System.Text;

namespace ConsoleApplication3
{
    internal class Program
    {
        private static string myStr;
        private static readonly StringBuilder mySb = new StringBuilder();

        private static void Main(string[] args)
        {
            Profile("+", 100000, () => myStr = myStr + "a"); // Takes 2236 ms
            Profile("SB", 100000, () => mySb.Append("a")); // Takes 1 ms
        }

        private static void Profile(string description, int iterations, Action func)
        {
            // clean up
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();

            // warm up 
            func();

            Stopwatch watch = Stopwatch.StartNew();
            for (int i = 0; i < iterations; i++)
            {
                func();
            }
            watch.Stop();
            Console.Write(description);
            Console.WriteLine(" Time Elapsed {0} ms", watch.ElapsedMilliseconds);
        }
    }
}

这就是俗称的情况下在它的显著更好的性能,通过连接字符串StringBuilder相对于+运营商.我的假设是StringBuilder通过创建更少的字符串来实现更好的性能.

性能和不变性之间是否存在平衡,或者出于某种原因这种情况是否例外？

Answer 1

有效地连接字符串不是关于可变结构和不可变结构,而是关于选择正确的数据结构和评估策略来支持O(1)追加.

通常,各种树的树用于支持快速附加,这最大化共享并最小化复制.示例结构包括绳索和指树.

在某些情况下,延迟评估也有帮助(例如,如果连接涉及复制,则可以延迟到实际需要字符串尾部的时间).在这种情况下,严格的数据结构可能会产生额外的复制开销,从而做了比必要更多的工作.

在你的情况下,我怀疑+涉及参数的严格副本(即O(n + m))工作,而字符串构建器可以通过分摊字符串缓冲区的重新分配来避免一些工作(给你树状性能,代价是要求线性使用结构,并失去线程安全性.