迭代链接列出的性能C#

本文关键字：性能 链接 迭代 | 更新日期: 2023-09-27 18:28:27

我目前正在做一些需要类似层次结构的设计（很像团结中的设计……事实上，我基本上只是在团结之上复制团结，作为一种学习体验），这需要在列表中插入/移动大量对象。出于这个原因，我决定使用LinkedList来存储所有层次结构对象（这是我第一次使用ListList）。

我决定看看哪种在链表上循环的方法最有效。我知道我可能在微观优化，但我通常通过测试来学习新东西，我的测试结果让我有点惊讶，所以我希望有人能对此有所了解。

（我不是设置性能测试的专家，但这种设置通常能让我很好地了解性能的差异）

测试：列表中有10个整数，另一个有100000

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace ConsoleApplication1
{
  class Program
  {
    private static Stopwatch timer = new Stopwatch();
    static void Main(string[] args)
    {
        /// Initialization
        var _linkedList = new LinkedList<int>();
        for (int i = 0; i < 10; i++)
            _linkedList.AddLast(i);

        /// Test 1
        timer.Start();
        for (var _node = _linkedList.First; _node != _linkedList.Last; _node = _node.Next)
            FuncFoo(_node.Value);
        timer.Stop();
        Console.WriteLine("For Loop: " + timer.Elapsed);
        timer.Reset();

        /// Test 2
        timer.Start();
        foreach (var _int in _linkedList)
            FuncFoo(_int);
        timer.Stop();
        Console.WriteLine("Foreach Loop: " + timer.Elapsed);
        timer.Reset();

        /// Test 3
        timer.Start();
        var _listNode = _linkedList.First;
        while (_listNode != _linkedList.Last)
        {
            FuncFoo(_listNode.Value);
            _listNode = _listNode.Next;
        }
        timer.Stop();
        Console.WriteLine("While Loop: " + timer.Elapsed);
        timer.Reset();

        ///End
        Console.Write("Press any key to continue...");
        Console.ReadKey();
    }
    private static void FuncFoo(int _num)
    {
        _num = (int)Math.Sqrt(1 + 2 + 3 + 4 + 5) * _num;
    }
  }
}

结果：列表中的10个整数

For Loop: 0.0002371
Foreach Loop: 0.0002880
While Loop: 0.0000002

结果：列表中的100000个整数

For Loop: 0.0013548
Foreach Loop: 0.0015256
While Loop: 0.0013436

所以有两件事我不确定。

  1. 为什么for循环比while循环慢得多？我以为for循环在幕后起到了while循环的作用？（我理解为什么foreach循环在所有情况下都稍微慢一点）

  2. 为什么while循环的效率会随着链接列表中添加更多元素而降低？我想它们或多或少都会保持相同的比例（就像for&foreach循环一样）。但是看到while循环似乎失去了性能（或者for/foreach增益性能？）让我很困惑。

我假设我的代码作为测试可能是不起作用的（在这种情况下，我想知道我做错了什么/为什么，这样我就知道如何在未来进行更可靠的测试）。但如果这是一个有效的测试，我想知道是什么导致了这些看似奇怪的结果（即使性能差异不会对我的代码产生影响）。

迭代链接列出的性能C#

首先，通过将迭代次数从1增加到100万，使您的测试更具代表性。还为每个测试添加未记录的迭代，以使JIT编译器有机会优化我们的代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace ConsoleApplication1
{
    class Program
    {
        private static Stopwatch timer = new Stopwatch();
        static void Main(string[] args)
        {
            /// Initialization
            var _linkedList = new LinkedList<int>();
            for (int i = 0; i < 10; i++)
                _linkedList.AddLast(i);
            for (int x = 0; x < 1000000; x++)
                for (var _node = _linkedList.First; _node != _linkedList.Last; _node = _node.Next)
                    FuncFoo(_node.Value);
            for (int x = 0; x < 1000000; x++)
                foreach (var _int in _linkedList)
                    FuncFoo(_int);
            for (int x = 0; x < 1000000; x++)
            {
                var _listNode = _linkedList.First;
                while (_listNode != _linkedList.Last)
                {
                    FuncFoo(_listNode.Value);
                    _listNode = _listNode.Next;
                }
            }
            /// Test 1
            timer.Start();
            for (int x = 0; x < 1000000; x++)
                for (var _node = _linkedList.First; _node != _linkedList.Last; _node = _node.Next)
                    FuncFoo(_node.Value);
            timer.Stop();
            Console.WriteLine("For Loop: " + timer.Elapsed);
            timer.Reset();

            /// Test 2
            timer.Start();
            for (int x = 0; x < 1000000; x++)
                foreach (var _int in _linkedList)
                    FuncFoo(_int);
            timer.Stop();
            Console.WriteLine("Foreach Loop: " + timer.Elapsed);
            timer.Reset();

            /// Test 3
            timer.Start();

            for (int x = 0; x < 1000000; x++)
            {
                var _listNode = _linkedList.First;
                while (_listNode != _linkedList.Last)
                {
                    FuncFoo(_listNode.Value);
                    _listNode = _listNode.Next;
                }
            }
            timer.Stop();
            Console.WriteLine("While Loop: " + timer.Elapsed);
            timer.Reset();

            ///End
            Console.Write("Press any key to continue...");
            Console.ReadKey();
        }
        private static void FuncFoo(int _num)
        {
            _num = (int)Math.Sqrt(1 + 2 + 3 + 4 + 5) * _num;
        }
    }
}

哇！还有更多实际结果：

For Loop: 00:00:00.2793502 
Foreach Loop: 00:00:00.3588778 
While Loop: 00:00:00.2660378

正如我们所看到的，for循环和while循环具有相同的结果。这是因为他们的MSIL代码也几乎相同：

IL_0115: callvirt instance class [System]System.Collections.Generic.LinkedListNode`1<!0> class [System]System.Collections.Generic.LinkedList`1<int32>::get_First()
IL_011a: stloc.s _listNode
IL_011c: br.s IL_0136
// loop start (head: IL_0136)
    IL_011e: nop
    IL_011f: ldloc.s _listNode
    IL_0121: callvirt instance !0 class [System]System.Collections.Generic.LinkedListNode`1<int32>::get_Value()
    IL_0126: call void ConsoleApplication1.Program::FuncFoo(int32)
    IL_012b: nop
    IL_012c: ldloc.s _listNode
    IL_012e: callvirt instance class [System]System.Collections.Generic.LinkedListNode`1<!0> class [System]System.Collections.Generic.LinkedListNode`1<int32>::get_Next()
    IL_0133: stloc.s _listNode
    IL_0135: nop
    IL_0136: ldloc.s _listNode
    IL_0138: ldloc.0
    IL_0139: callvirt instance class [System]System.Collections.Generic.LinkedListNode`1<!0> class [System]System.Collections.Generic.LinkedList`1<int32>::get_Last()
    IL_013e: ceq
    IL_0140: ldc.i4.0
    IL_0141: ceq
    IL_0143: stloc.s CS$4$0000
    IL_0145: ldloc.s CS$4$0000
    IL_0147: brtrue.s IL_011e
// end loop

ForEach循环运行时间更长，因为它的机制创建了实现IDisposable的Enumerator的新实例，并且应该在循环的末尾进行处理。实际MSIL代码如下所示：

IL_009c: ldloc.0
IL_009d: callvirt instance valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<!0> class [System]System.Collections.Generic.LinkedList`1<int32>::GetEnumerator()
IL_00a2: stloc.s CS$5$0001
.try
{
    IL_00a4: br.s IL_00b5
    // loop start (head: IL_00b5)
        IL_00a6: ldloca.s CS$5$0001
        IL_00a8: call instance !0 valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<int32>::get_Current()
        IL_00ad: stloc.3
        IL_00ae: ldloc.3
        IL_00af: call void ConsoleApplication1.Program::FuncFoo(int32)
        IL_00b4: nop
        IL_00b5: ldloca.s CS$5$0001
        IL_00b7: call instance bool valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<int32>::MoveNext()
        IL_00bc: stloc.s CS$4$0000
        IL_00be: ldloc.s CS$4$0000
        IL_00c0: brtrue.s IL_00a6
    // end loop
    IL_00c2: leave.s IL_00d3
} // end .try
finally
{
    IL_00c4: ldloca.s CS$5$0001
    IL_00c6: constrained. valuetype [System]System.Collections.Generic.LinkedList`1/Enumerator<int32>
    IL_00cc: callvirt instance void [mscorlib]System.IDisposable::Dispose()
    IL_00d1: nop
    IL_00d2: endfinally
} // end handler

正如您所看到的，这个MSIL完全不同，因为它使用了Enumerator.MoveNext方法而不是LinkedListNode.get_Next（），并创建了影响性能的try块，因为在某些平台上，异常处理会带来成本。

此外，JIT不会对"try"块执行优化，这也会影响您的性能。

相关文章：