問題我有一個數(shù)組列表，我想計算重復(fù)的出現(xiàn)次數(shù)。例如，如果我有這個：{{1,2,3}, {1,0,3}, {1,2,3}, {5,2,6}, {5,2,6}, {5,2,6}}我想要一張像這樣的地圖（或任何相關(guān)的集合）：{ {1,2,3} -> 2, {1,0,3} -> 1, {5,2,6} -> 3 }我什至可以丟失數(shù)組值，我只對基數(shù)感興趣（例如這里的 2、1 和 3）。我的解決方案我使用以下算法：首先對數(shù)組進行散列，并檢查每個散列是否在 an 中HashMap<Integer, ArrayList<int[]>>，我們將其命名為distinctHash，其中鍵是散列，值是一個 ArrayList，讓我們將其命名為rowList，其中包含此散列的不同數(shù)組（以避免沖突）。如果散列不在distinctHash 中，請將其與值 1 放在另一個HashMap<int[], Long>計算每次出現(xiàn)的次數(shù)中，我們稱其為distinctElements。然后，如果哈希在distinctHash 中，則檢查相應(yīng)的數(shù)組是否包含在rowList 中。如果是，則增加與在rowList 中找到的相同數(shù)組關(guān)聯(lián)的distinctElements中的值。（如果您使用新數(shù)組作為鍵，您將創(chuàng)建另一個鍵，因為它們的引用不同）。這是代碼，返回的布爾值告訴是否找到了新的不同數(shù)組，我在所有數(shù)組上依次應(yīng)用此函數(shù)： 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 個數(shù)組需要 40 秒，20,000,000 個數(shù)組需要 2h-3h）。使用 NetBeans 分析告訴我散列占用了 70% 的運行時間（使用 Google Guava murmur3_128 散列函數(shù)）。還有另一種算法可以更快嗎？正如我所說，我對數(shù)組值不感興趣，只對它們出現(xiàn)的次數(shù)感興趣。我準備為了速度犧牲精度，所以概率算法很好。
3 回答
拉丁的傳說
TA貢獻1789條經(jīng)驗 獲得超8個贊
將 包裝int[]在實現(xiàn)equalsand的類中hashCode，然后Map將包裝類構(gòu)建為實例計數(shù)。
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
注意：上述解決方案比Ravindra Ranwala 的解決方案更快并且使用更少的內(nèi)存，但它確實需要創(chuàng)建一個額外的類，因此哪個更好是有爭議的。
對于較小的陣列，請使用下面由 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()));
嗶嗶one
TA貢獻1854條經(jīng)驗 獲得超8個贊
你可以這樣做，
Map<List<Integer>, Long> result = Stream.of(source)
.map(a -> Arrays.stream(a).boxed().collect(Collectors.toList()))
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
這是輸出，
{[1, 2, 3]=2, [1, 0, 3]=1, [5, 2, 6]=3}
翻翻過去那場雪
TA貢獻2065條經(jīng)驗 獲得超14個贊
如果該數(shù)組的所有重復(fù)的元素序列彼此相似并且每個數(shù)組的長度不多，則可以將每個數(shù)組映射到一個int數(shù)字并使用方法的最后一部分。雖然這種方法減少了散列時間，但這里有一些假設(shè)可能不適用于您的情況。
添加回答
舉報
0/150
提交
取消