问题
我有一个数组列表,我想计算重复项的出现次数。
例如,如果我有这个:
{{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 哈希函数)。
还有其他算法可以更快吗?正如我所说,我对数组值不感兴趣,只对它们出现的次数感兴趣。我准备牺牲精度来换取速度,所以概率算法很好。
最佳答案
将 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()));
关于java - 计算具有重复项的数组列表中每个不同数组的出现次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52631769/