c# - LinkedList 比 List 迭代更快？

Question

出于某种原因，我的 LinkedList 似乎优于我的 List。我有一个 LinkedList 因为有一部分代码我必须重新排列 child 。重新排列之后的一切都只是简单地遍历数据并执行计算。我之前只是使用 Iterator 遍历 LinkedList，但后来我认为我应该同时存储相同元素的 List，所以我可以更快地迭代它们。不知何故，添加 List 并对其进行迭代对于完全相同的事情来说要慢得多。不确定这是怎么回事，所以任何信息都有帮助。

这里大致是我期望更快的代码:

class Program {
    public static void Main(string[] args) {
        var originalList = new List<Thing>();
        for (var i = 0; i < 1000; i++) {
            var t = new Thing();
            t.x = 0d;
            t.y = 0d;
            originalList.Add(t);
        }
        var something = new Something(originalList);

        for (var i = 0; i < 1000; i++) {
            var start = DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
            something.iterate();
            time += (DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond) - start;
            Console.Out.WriteLine(time / (i + 1));
        }
    }

    class Thing {
        public double x {get; set;}
        public double y {get; set;}
    }

    class Something {
                    private List<Thing> things;
        private LinkedList<Thing> things1 = new LinkedList<Thing>();
        private List<Thing> things2 = new List<Thing>();

        public Class(List<Thing> things) {
            this.things = things;

            for (var i = 0; i < things.Count; i++) {
                things1.AddLast(things[i]);
                things2.Add(things[i]);
            }
        }

        public void iterate() {
            //loops like this happen a few times, but the list is never changed, only the
            //objects properties in the list
            for (var i = 0; i < things2.Count; i++) {
                                    var thing = things2[i];
                thing.x += someDouble;
                thing.y += someOtherDouble;
            }
        }
    }
}

这是我首先做的，我认为应该慢一些:

class Program {
    public static void Main(string[] args) {
        var originalList = new List<Thing>();
        for (var i = 0; i < 1000; i++) {
            var t = new Thing();
            t.x = 0d;
            t.y = 0d;
            originalList.Add(t);
        }
        var something = new Something(originalList);

        for (var i = 0; i < 1000; i++) {
            var start = DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
            something.iterate();
            time += (DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond) - start;
            Console.Out.WriteLine(time / (i + 1));
        }
    }

    class Thing {
        public double x {get; set;}
        public double y {get; set;}
    }

    class Something {
        private List<Thing> things;
        private LinkedList<Thing> things1 = new LinkedList<Thing>();

        public Class(List<Thing> things) {
            this.things = things;

            for (var i = 0; i < things.Count; i++) {
                things1.AddLast(things[i]);
            }
        }

        public void iterate() {
            //loops like this happen a few times, but the list is never changed, only the
            //objects properties in the list
            var iterator = things1.First;
            while (iterator != null) {
                var value = iterator.Value;
                value.x += someDouble;
                value.y += someOtherDouble;
                iterator = iterator.Next;
            }
        }
    }
}

Answer 1

因为它不编译，所以很难验证任何东西，所以我不能在我的机器上运行它，但仍然存在一些大问题:

• 您不应该使用DateTime.Now 来衡量性能。而是使用能够进行高保真时间测量的 Stopwatch，例如:

var stopwatch = Stopwatch.StartNew();
//do stuff here
stopwatch.Stop();
double timeInSeconds = stopwatch.Elapsed.TotalSeconds;

• 您的算法在以下行中存在根本性缺陷:

DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond

刻度表示为整数(此处为long)，除法结果不是实数，而是被截断了。例如。 55/7 = 7。因此，它绝对不是一种稳定的基准测试方式。

此外，使用更多元素运行基准测试并确保在 Release模式下进行。