長尾分佈發生計數的數據結構

我有一個很大的元素列表（數千萬）。我想要計算這些元素的幾個子集的出現次數。發生分佈是長尾的。長尾分佈發生計數的數據結構

的數據結構目前看起來像這樣（在OCaml的上下的香味）：

type element_key 
type element_aggr_key 

type raw_data = element_key list 

type element_stat = 
{ 
    occurrence : (element_key, int) Hashtbl.t; 
} 

type stat = 
{ 
    element_stat_hashtable : (element_aggr_key, element_stat) Hashtbl.t; 
}

Element_stat目前使用哈希表，其中的關鍵是每個元件和所述值是一個整數。然而，這是低效率的，因爲當許多元素只有一次發生時，發生的哈希表被多次調整大小。我無法避免通過設置較大的初始大小來調整發生哈希表的大小，因爲實際上有很多element_stat實例（stat中的哈希表大小很大）。

我想知道這個用例是否有更高效的（內存方式和/或插入方式）數據結構。我發現了很多現有的數據結構，如trie，radix樹，Judy數組。但是我很難理解他們的差異以及他們是否適合我的問題。

來源

2014-02-06 Johan Mazel

你只是擔心調整大小，或者你認爲這是一個真正的性能瓶頸？總體而言，我相信調整大小會增加一個對數因子。調整大小在一開始就發生了很多，但桌子很小。後來它幾乎從不發生。 –

我有一個高調整成本的經驗。然而，我沒有任何數字。我還知道一個事實，即調整大小發生在特殊情況下，其中大量關鍵字（大約一百萬）只有一次發生（參見長尾分佈）。 –

你在這裏有一個表映射element_aggr_key到表，依次映射element_key到int。對於所有的實際目的，這相當於映射element_aggr_key * element_key到int一個表，所以你可以這樣做：

type stat = (element_aggr_key * element_key, int) Hashtbl.t

然後你有一個哈希表，你可以給它一個巨大的初始大小。

來源

2015-02-06 05:01:10 Planar

長尾分佈發生計數的數據結構

回答

相關問題