当阵列更快时，为什么要使用列表？

I noticed that Arrays perform much, much faster than Haxe's Linked Lists (atleast on cpp). The results I got are as follows.

我注意到Arrays的执行速度远远超过Haxe的链接列表（至少在cpp上）。我得到的结果如下。

Main.hx:40: With 1 items, Array is 14% faster than List.
Main.hx:40: With 5 items, Array is 58% faster than List.
Main.hx:40: With 10 items, Array is 59% faster than List.
Main.hx:40: With 100 items, Array is 54% faster than List.
Main.hx:40: With 1000 items, Array is 56% faster than List.
Main.hx:40: With 10000 items, Array is 55% faster than List.
Main.hx:40: With 100000 items, Array is 52% faster than List.

This strikes me as bedazzling. How can Array be so fast even though it has to copy around items continuously? And why even use Lists then?

这让我感到尴尬。尽管数组必须连续复制项目，但数组怎么能这么快？为什么甚至使用Lists呢？

package tests;

import haxe.Timer;

class Main 
{

    static function main() 
    {
        var arr:Array<Int> = new Array();
        var list:List<Int> = new List();
        var result = new List();

        for (items in [1, 5, 10, 100, 1000, 10000, 100000]) {
            var listtime = timeit(10000, function() {
                for (i in 0...items)
                    list.add(i);
                for (x in list)
                    result.add(x);
                result.clear();
                list = new List();
            });

            var arrtime = timeit(10000, function() {
                for (i in 0...items)
                    arr.push(i);
                for (x in arr)
                    result.add(x);
                result.clear();
                arr = new Array();
            });

            if (arrtime < listtime)
                trace('With $items items, Array is ${Std.int((1-arrtime/listtime)*100)}% faster than List.');
            else
                trace('With $items items, List is ${Std.int((1-listtime/arrtime)*100)}% faster than Array.');
        }
    }

    static public function timeit<T>(times:Int, f:Void -> T):Float {
        var start = Timer.stamp();
        for (i in 0...times) {
            f();
        }
        var time = Timer.stamp() - start;
        return time;
    }

}

3 个解决方案

#1

How can Array be so fast even though it has to copy around items continuously?

尽管数组必须连续复制项目，但数组怎么能这么快？

Arrays are faster for linear processing because array contents are stored contiguously in memory. When you access memory linearly, multiple objects are fetched to the processor cache simultaneously. Linked list nodes on the other hand are scattered throughout the memory, so processing them linearly results in more acccesses in main memory. Reading cache is much, much faster than reading main memory.

对于线性处理，数组更快，因为数组内容连续存储在内存中。当您以线性方式访问内存时，会同时将多个对象提取到处理器缓存中。另一方面，链接列表节点分散在整个存储器中，因此线性处理它们会在主存储器中产生更多的影响。读取缓存比读取主内存快得多。

And why even use Lists then?

为什么甚至使用Lists呢？

One major reason to use a linked list, is that inserting new elements, or removing existing ones, does not invalidate references (including iterators and pointers) to other elements in the linked list. An array can not have such guarantee.

使用链表的一个主要原因是插入新元素或删除现有元素不会使链接列表中其他元素的引用（包括迭代器和指针）无效。阵列不能有这样的保证。

#2

Why use Lists, when Arrays are faster?

当阵列更快时，为什么要使用列表？

Faster for what? Linked lists are typically a lot faster when it comes to inserting elements between others or deleting elements in the middle of the list. With an array (at least, an C-style array) inserting or deleting at position i requires moving every element after i. With linked lists, you need only change a couple of pointers.

更快的是什么？链接列表在其他人之间插入元素或删除列表中间的元素时通常要快得多。使用数组（至少是C风格的数组）在位置i处插入或删除需要在i之后移动每个元素。使用链接列表，您只需要更改几个指针。

Try your test again, but instead of pushing elements onto the end of the list, insert them at the beginning.

再次尝试测试，但不是将元素推到列表的末尾，而是在开头插入它们。

#3

There is an article that goes over this matter extensively :

有一篇文章广泛讨论了这个问题：

https://github.com/delahee/haxe.opt/blob/master/list_vs_array.md

TLDR : it depends of your use case but list can definitely go faster in some scenarios.

TLDR：这取决于你的用例，但在某些情况下列表肯定会更快。

#1