最有效的方法來計數事件？

我期待在性能關鍵代碼中計算熵和互信息很多次。作爲中間步驟，我需要計算每個值的出現次數。例如：最有效的方法來計數事件？

uint[] myArray = [1,1,2,1,4,5,2]; 
uint[] occurrences = countOccurrences(myArray); 
// Occurrences == [3, 2, 1, 1] or some permutation of that. 
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5.

。當然，明顯的方式給此要麼使用關聯數組或通過排序使用「標準」的排序算法等快速排序輸入數組做。對於像字節這樣的小整數，代碼目前專門用於使用普通的舊數組。

是否有任何聰明的算法比散列表或「標準」排序算法提供的效率更高效，例如關聯數組實現，該算法非常支持插入更新或排序算法，這些算法在數據存在時發光很多關係？

注意：非稀疏整數只是可能數據類型的一個示例。我期望在這裏實現一個合理的通用解決方案，但由於整數和只包含整數的結構是常見的情況，如果它們非常有效，我會對這些解決方案感興趣。

來源

2010-03-05 dsimcha

不能再想起你上面說的。對數組進行排序，然後順序遍歷它。 – 2010-03-05 04:20:49

也許你可以使用某種Hadoop或Map/Reduce來加速你的算法？除此之外，我什麼都看不到。 – kgrad 2010-03-05 04:34:10

@kgrad：我已經完全通過並行化外部循環來充分利用所有內核，因此將此函數的單獨執行並行化沒有意義。 – dsimcha 2010-03-05 04:37:26

請詳細說明您的數據。

有多少項？
獨特項目與總項目的預期比率是多少？
什麼是你的整數的實際值的分佈？它們通常小到可以使用簡單的計數陣列？還是他們聚集到合理狹窄的羣體？等

在任何情況下，我建議以下想法：mergesort修改爲計數重複。

也就是說，在以下方面不工作電話號碼，但對（數字，頻率）（可能用於一些巧妙存儲器高效的表示，例如兩個陣列，而不是對數組等）。

從[（x1,1），（x2,1），...]開始並照常執行mergesort，但是當合並兩個以相同值開始的列表時，將該值放入輸出列表和它們的總和。在您的例子：

[1:1,1:1,2:1,1:1,4:1,5:1,2:1] 
Split into [1:1, 1:1, 2:1] and [1:1, 4:1, 5:1, 2:1] 
Recursively process them; you get [1:2, 2:1] and [1:1, 2:1, 4:1, 5:1] 
Merge them: (first/second/output) 
[1:2, 2:1]/[1:1, 2:1, 4:1, 5:1]/[] - we add up 1:2 and 1:1 and get 1:3 
[2:1]/[2:1, 4:1, 5:1]/[1:3] - we add up 2:1 and 2:1 and get 2:2 
[]/[4:1, 5:1]/[1:3, 2:2] 
[1:3, 2:2, 4:1, 5:1]

這可能是通過使用一些巧妙的技巧，做陣列的初始減少大大改善（獲得的數值數組：occurence對，比原來小很多，但總和每個'值'的'發生'等於原始數組中'值'的出現次數）。例如，將數組拆分爲連續的塊，其中值不超過256或65536，並使用小數組來計算每個塊內的出現次數。實際上，這個技巧也可以在稍後的合併階段應用。

來源

2010-03-05 10:24:41 jkff

對於這個例子中的整數數組，最有效的方法是使用一個數組int s並使用您的值對其進行索引（因爲您似乎已經在執行此操作）。

如果你不能這樣做，我想不出比hashmap更好的選擇。你只需要有一個快速的哈希算法。如果您想使用所有數據，則無法比O（n）性能更好。是否只能使用您擁有的部分數據？

（注意，分類和計數是漸近較慢（O（N *的log（n）））比使用基於散列映射溶液（O（N））。）

來源

2010-03-05 04:24:17

排序漸近較慢，但在高熵情況下（並非每個值出現多次），即使對於非常大的N（以百萬計），實際上排序也更快，因爲它的緩存效率更高。 – dsimcha 2010-03-05 04:41:52

散列通常是更加可擴展，作爲另一答案表示。但是，對於許多可能的分佈（以及許多實際情況，其中子陣列恰好經常被排序，取決於整個陣列如何放在一起），timsort通常「非常好」（更接近O（N）而不是O（N log N）） - 我聽說它可能會成爲Java中的標準/默認排序算法，在一些相當接近的未來數據中（它已經成爲Python中多年來的標準排序算法）。

解決此類問題的方法並不是真正的好方法，只能選擇一些代表您預期會遇到的實際工作負載的案例進行基準測試（具有明顯的風險，您可以選擇實際發生的樣本有偏見/沒有代表性 - 如果你想建立一個圖書館，那麼你的控制之外的許多外部用戶會使用這個庫），這不是一個小的風險。

來源

2010-03-05 04:45:02

我不知道'timsort'，看起來很有趣！ – 2010-03-05 10:12:38

最有效的方法來計數事件？

回答

相關問題