在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数组。使用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