0

我有一个很大的元素列表（数千万）。我正在尝试计算这些元素的几个子集的出现次数。发生分布是长尾的。

数据结构目前看起来像这样（以 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、基数树、Judy 数组。但是我很难理解它们的差异以及它们是否适合我的问题。

4

1 回答 1

1

您在这里拥有的是一个映射element_aggr_key到表的表，这些表又映射element_key到int. 出于所有实际目的，这相当于映射element_aggr_key * element_key到的单个表int，因此您可以这样做：

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

然后你有一个哈希表，你可以给它一个巨大的初始大小。

于 2015-02-06T05:01:10.350 回答