在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 - 对象创建并不昂贵,可能不如清除集合(由底部的基准测试确认 - 请参阅编辑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