java - 计算具有重复项的数组列表中每个不同数组的出现次数

Question

问题

我有一个数组列表，我想计算重复项的出现次数。

例如，如果我有这个:

{{1,2,3},
 {1,0,3},
 {1,2,3},
 {5,2,6},
 {5,2,6},
 {5,2,6}}

我想要这样的 map (或任何相关的集合):

{ {1,2,3} -> 2,
  {1,0,3} -> 1,
  {5,2,6} -> 3 }

我什至可以丢失数组值，我只对基数感兴趣(例如这里的 2、1 和 3)。

我的解决方案

我使用以下算法:

• 首先散列数组，并检查每个散列是否在 HashMap<Integer, ArrayList<int[]>> 中，我们将其命名为 distinctHash，其中键是散列，值是一个 ArrayList，我们将其命名为 rowList，包含此散列的不同数组(以避免冲突) .

• 如果散列不在distinctHash中，将它的值1放在另一个HashMap<int[], Long>中计算每次出现的次数，我们称它为 distinctElements。

• 然后如果哈希在distinctHash中，则检查相应的数组是否包含在rowList中。如果是，则增加 distinctElements 中与 rowList 中找到的相同数组关联的值。 (如果您使用新数组作为键，您将创建另一个键，因为它们的引用不同)。

这是代码，返回的 boolean 值告诉我是否找到了一个新的不同数组，我按顺序在我的所有数组上应用这个函数:

    HashMap<int[], Long> distinctElements;
    HashMap<Integer, ArrayList<int[]>> distinctHash;

    private boolean addRow(int[] row) {

        if (distinctHash.containsKey(hash)) {
            int[] indexRow = distinctHash.get(hash).get(0);
            for (int[] previousRow: distinctHash.get(hash)) {
                if (Arrays.equals(previousRow, row)) {
                    distinctElements.put(
                            indexRow,
                            distinctElements.get(indexRow) + 1
                    );
                    return false;
                }
            }
            distinctElements.put(row, 1L);

            ArrayList<int[]> rowList = distinctHash.get(hash);
            rowList.add(row);
            distinctHash.put(hash, rowList);

            return true;

        } else {
            distinctElements.put(row, 1L);

            ArrayList<int[]> newValue = new ArrayList<>();
            newValue.add(row);
            distinctHash.put(hash, newValue);

            return true;
        }
    }

问题

问题是我的算法对于我的需求来说太慢了(5,000,000 个数组需要 40 秒，20,000,000 个数组需要 2h-3h)。使用 NetBeans 进行的分析告诉我，哈希运算占用了 70% 的运行时间(使用 Google Guava murmur3_128 哈希函数)。

还有其他算法可以更快吗？正如我所说，我对数组值不感兴趣，只对它们出现的次数感兴趣。我准备牺牲精度来换取速度，所以概率算法很好。

Answer 1

将 int[] 包装在一个实现了 equals 和 hashCode 的类中，然后构建 Map实例计数的包装类。

class IntArray {
    private int[] array;
    public IntArray(int[] array) {
        this.array = array;
    }
    @Override
    public int hashCode() {
        return Arrays.hashCode(this.array);
    }
    @Override
    public boolean equals(Object obj) {
        return (obj instanceof IntArray && Arrays.equals(this.array, ((IntArray) obj).array));
    }
    @Override
    public String toString() {
        return Arrays.toString(this.array);
    }
}

测试

int[][] input = {{1,2,3},
                 {1,0,3},
                 {1,2,3},
                 {5,2,6},
                 {5,2,6},
                 {5,2,6}};
Map<IntArray, Long> map = Arrays.stream(input).map(IntArray::new)
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
map.entrySet().forEach(System.out::println);

输出

[1, 2, 3]=2
[1, 0, 3]=1
[5, 2, 6]=3

---

注意:上述解决方案比 solution by Ravindra Ranwala 更快且使用的内存更少, 但它确实需要创建一个额外的类，所以哪个更好是值得商榷的。

对于较小的阵列，请使用下面由 Ravindra Ranwala 提供的更简单的解决方案。
对于更大的阵列，上述解决方案可能更好。

 Map<List<Integer>, Long> map = Stream.of(input)
         .map(a -> Arrays.stream(a).boxed().collect(Collectors.toList()))
         .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));