java - 在 for 循环中重新创建 ArrayList 的最快方法

Question

在 Java 中，对一个巨大的矩阵 X 使用以下函数来打印其列不同的元素:

// create the list of distinct values
List<Integer> values = new ArrayList<Integer>();

// X is n * m int[][] matrix
for (int j = 0, x; j < m; j++) {
    values.clear();
    for (int i = 0; i < n; i++) {
        x = X[i][j];
        if (values.contains(x)) continue;
        System.out.println(x);
        values.add(x);
    }
}

首先，我按列(索引 j)和行(索引 i)在内部进行迭代。

这个函数会针对不同的矩阵被调用数百万次，所以应该优化代码以满足性能需求。我想知道值数组。使用 values = new ArrayList<Integer>(); 会更快吗？或 values = null而不是 values.clear() ？

Answer 1

效率更高的是使用 Set而不是列表，例如 HashSet执行。 contains 方法将在 O(1) 中运行，而不是在列表中运行 O(n)。只需调用 add 方法即可节省一次调用。

至于你的具体问题，我只想在每个循环中创建一个新的 Set - 创建对象并不那么昂贵，可能比清除 set 更少(正如底部的基准测试所证实的 - 请参阅 EDIT 中最有效的版本2):

for (int j = 0, x; j < m; j++) {
    Set<Integer> values = new HashSet<Integer>();
    for (int i = 0; i < n; i++) {
        x = X[i][j];
        if (!values.add(x)) continue; //value.add returns true if the element was NOT in the set before
        System.out.println(x);
    }
}

但是，要知道哪个更快(新对象还是清除)的唯一方法是分析代码的那部分并检查两个版本的性能。

编辑

我运行了一个快速基准测试，清晰版本似乎比在每个循环中创建一个集合快一点(大约 20%)。您仍然应该检查您的数据集/用例，哪个更好。使用我的数据集更快的代码:

Set<Integer> values = new HashSet<Integer>();
for (int j = 0, x; j < m; j++) {
    for (int i = 0; i < n; i++) {
        x = X[i][j];
        if (!values.add(x)) continue; //value.add returns true if the element was NOT in the set before
        System.out.println(x);
    }
    values.clear();
}

编辑 2

通过在每个循环中创建一组大小合适的新代码，可以获得实际上更快的代码版本:

for (int j = 0, x; j < m; j++) {
    Set<Integer> values = new HashSet<Integer>(n, 1); //right size from the beginning
    for (int i = 0; i < n; i++) {
        x = X[i][j];
        if (!values.add(x)) continue; //value.add returns true if the element was NOT in the set before
        System.out.println(x);
    }
}

结果总结

JVM 预热 + JIT 之后:

Set<Integer> values = new HashSet<Integer>(n, 1); =====> 280 ms
values.clear();                                   =====> 380 ms
Set<Integer> values = new HashSet<Integer>();     =====> 450 ms