数组应该比 ArrayLists 快这么多吗？

Question

我实现了两种方法，shuffleList 和 shuffleArray，它们使用完全相同的功能。我有一个 50 万整数的 ArrayList 和一个相同的 50 万整数数组。在我的基准测试代码中，它在相应的数组或 ArrayList 上对每个方法执行 100 次并记录时间，看起来 shuffleArray 大约需要 0.5 秒，而 shuffleList 大约需要 3.5 秒，甚至虽然代码没有使用任何 ArrayList 方法，但使用了 get 和 set，它们的工作速度应该与它们在数组中的工作速度一样快。

现在我知道 ArrayLists 有点慢，因为它们在内部使用数组但有一些额外的代码，但这有这么大的不同吗？

     void shuffleList(List<Integer> list){
        Random rnd = ThreadLocalRandom.current();
        for(int i=list.size()-1;i>0;i--){
            int index=rnd.nextInt(i+1);
            int a=list.get(index);
            list.set(index,list.get(i));
            list.set(i,a);
        }
    }

    void shuffleArray(int[] ar)
    {
        Random rnd = ThreadLocalRandom.current();
        for (int i = ar.length - 1; i > 0; i--)
        {
            int index = rnd.nextInt(i + 1);
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }

基准代码：

import org.openjdk.jmh.Main;
import org.openjdk.jmh.annotations.*;

@BenchmarkMode(Mode.AverageTime)
public class MyBenchmark {


    @Benchmark
    @Fork(value = 1)
    @Warmup(iterations = 3)
    @Measurement(iterations = 10)
    public void compete() {
        try {
            Sorting sorting = new Sorting();
            sorting.load();
            System.out.println(sorting.test());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) throws Exception {
        Main.main(args);
    }
}

    protected List<Integer> list = new ArrayList<Integer>();
    protected List<int[]> arrays= new ArrayList<>();

    protected void load(){
        try (Stream<String> stream = Files.lines(Paths.get("numbers.txt"))) {
            stream.forEach(x -> list.add(Integer.parseInt(x)));
        } catch (IOException e) {
            e.printStackTrace();
        }
        finally{
            int[] arr =new int[list.size()];
            for(int i=0;i<list.size();i++)
                arr[i]=list.get(i);
            arrays.add(arr);
        }
    }

    protected double test(){
        int arr[]=arrays.get(0);
        Stopwatch watch = new Stopwatch();
        for (int i=0; i<100; i++){
          shuffleArray(arr);
          shuffleList(list);
        }
        return watch.elapsedTime();
    }

我在 for 循环中注释掉其中一个方法并使用另一个。

更新：

我按照你们很多人的建议，在 shuffleList 方法中将 Int a 更改为 Integer a，这让它变得更快了一点，而是 3 秒现在是 3.5，但我仍然认为这是一个很大的不同。

值得一提的是，将shuffleArray方法中的int[] arr改为Integer[] arr，同时保持int a原样，模拟数组的装箱和拆箱时间，确实使它成为a慢很多，它需要大约 3 秒，所以我可以让数组和 ArrayList 一样慢，但我不能做相反的事情。

更新：

在 shuffleList 中使用 Collections.swap() 确实使它和数组一样快，但我仍然不明白为什么，我的基准测试太敏感了还是真的很重要？

最终 shuffleList 代码，由 Andy Turner 和 Joop Eggen 提供：

    protected void shuffleList(List<Integer> list){
        Random rnd = ThreadLocalRandom.current();
        for(int i=list.size()-1;i>0;i--){
            int index=rnd.nextInt(i+1);
            Collections.swap(list, i, index);
        }
    }

Answer 1

使用Integer a，省去了一次拆箱和一次装箱操作。

    for (int i = list.size()-1; i>0; i--){
        int index=rnd.nextInt(i+1);
        Integer a=list.get(index);
        list.set(index,list.get(i));
        list.set(i,a);
    }

并且 Integer 对象使用更多内存。

@Andy Turner 提到存在 Collections#swap。

    for (int i = list.size()-1; i > 0; i--) {
        int index = rnd.nextInt(i+1);
        Collections.swap(list, i, index);
    }

如果不预热 JIT 编译器，这可能会降低基准测试速度，但在生产代码中看起来会更好。不过你可能还是会使用 Collections.shuffle。

如评论所述，交换版本也很快。首先，OP 显示使用正确的微基准测试代码。

swap 也使用原始整数 class。它 l.set(i, l.set(j, l.get(i))); 是为了交换 - 作为 set returns 该位置的前一个元素。 JIT 编译器可能可以解包集合并立即使用前一个元素。

Answer 2

有一个 Java 函数可以完成这项工作：

Collections.shuffle( list );

这应该比 for 循环快得多。

数组应该比 ArrayLists 快这么多吗？

Are arrays supposed to be faster than ArrayLists by this much?

java

arrays

benchmarking

arraylist

time-complexity