当阵列速度更快时,为什么要使用列表？

Question

我注意到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.

这让我感到尴尬.尽管Array必须不断复制项目,但Array怎么能这么快？为什么甚至使用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;
    }

}

Answer 1

尽管Array必须不断复制项目,但Array怎么能这么快？

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

为什么甚至使用Lists呢？

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