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

在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>(); or values = null代替values.clear() ?

更有效的方法是使用Set http://docs.oracle.com/javase/7/docs/api/java/util/Set.html而不是列表，例如HashSet http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html执行。 contains 方法的运行时间为 O(1)，而不是列表的 O(n)。您只需调用 add 方法就可以节省一次调用。

至于你的具体问题，我只是在每个循环中创建一个新的集合 - 对象创建并不那么昂贵，可能比清除集合要少（正如底部的基准测试所证实的那样 - 请参阅编辑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);
    }
}

但是，了解哪个更快（新对象与清除对象）的唯一方法是分析代码的该部分并检查两个版本的性能。

EDIT

我运行了一个快速基准测试，清晰的版本似乎比在每个循环中创建一组要快一些（大约快 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();
}

EDIT 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