java - 数组应该比 ArrayList 快这么多吗？

Question

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

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

     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 循环中的一个方法并使用另一个。

更新:

我做了你们很多人建议的改变Int a至Integer a在 shuffleList方法，并且它使它更快一点，现在是 3 秒而不是 3.5 秒，但我仍然认为这是一个很大的区别。

值得一提的是，将 shuffleArray 中的 int[] arr 更改为 Integer[] arr使用 keep int 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 也使用原始的 Integer 类。它执行 l.set(i, l.set(j, l.get(i))); 以便交换 - 因为 set 返回该处的前一个元素位置。 JIT 编译器可能可以立即解开集合并利用之前的元素。