問題我有一個數組列表，我想計算重復的出現次數。例如，如果我有這個：{{1,2,3}, {1,0,3}, {1,2,3}, {5,2,6}, {5,2,6}, {5,2,6}}我想要一張像這樣的地圖（或任何相關的集合）：{ {1,2,3} -> 2, {1,0,3} -> 1, {5,2,6} -> 3 }我什至可以丟失數組值，我只對基數感興趣（例如這里的 2、1 和 3）。我的解決方案我使用以下算法：首先對數組進行散列，并檢查每個散列是否在 an 中HashMap<Integer, ArrayList<int[]>>，我們將其命名為distinctHash，其中鍵是散列，值是一個 ArrayList，讓我們將其命名為rowList，其中包含此散列的不同數組（以避免沖突）。如果散列不在distinctHash 中，請將其與值 1 放在另一個HashMap<int[], Long>計算每次出現的次數中，我們稱其為distinctElements。然后，如果哈希在distinctHash 中，則檢查相應的數組是否包含在rowList 中。如果是，則增加與在rowList 中找到的相同數組關聯的distinctElements中的值。（如果您使用新數組作為鍵，您將創建另一個鍵，因為它們的引用不同）。這是代碼，返回的布爾值告訴是否找到了新的不同數組，我在所有數組上依次應用此函數： 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 散列函數）。還有另一種算法可以更快嗎？正如我所說，我對數組值不感興趣，只對它們出現的次數感興趣。我準備為了速度犧牲精度，所以概率算法很好。
3 回答
拉丁的傳說
TA貢獻1789條經驗 獲得超8個贊
將 包裝int[]在實現equalsand的類中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
注意：上述解決方案比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()));
嗶嗶one
TA貢獻1854條經驗 獲得超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條經驗 獲得超14個贊
如果該數組的所有重復的元素序列彼此相似并且每個數組的長度不多，則可以將每個數組映射到一個int數字并使用方法的最后一部分。雖然這種方法減少了散列時間，但這里有一些假設可能不適用于您的情況。
添加回答
舉報
0/150
提交
取消