高效的频率计数器

Question

我有15,000,000 std:6个整数的向量.

那些15M载体包含重复.重复的例子:

(4,3,2,0,4,23)
(4,3,2,0,4,23)

我需要获得一个具有相关计数的唯一序列列表.(仅存在一次的序列将具有1个计数)

在std C++中有一个算法(可以是x11)一次性完成吗？

Windows,4GB RAM,30 + GB硬盘

Answer 1

标准库中没有这样的算法可以做到这一点,但是通过单个循环并选择适当的数据结构非常容易.

为此你想要使用std::unordered_map通常是哈希映射.它预计每次访问的持续时间(插入和查找),因此是大数据集的首选.

以下访问和入侵技巧将自动在计数器地图中插入一个新条目(如果它尚未存在); 然后它会递增并回写计数.

typedef std::vector<int> VectorType;        // Please consider std::array<int,6>!

std::unordered_map<VectorType, int> counters;

for (VectorType vec : vectors) {
    counters[vec]++;
}

对于进一步处理,您可能希望按出现次数对条目进行排序.为此,要么将它们写在对的向量中(它封装数字向量和出现次数),要么在具有键和值交换的(有序)映射中写出它们,因此它由计数器自动排序.

为了减少此解决方案的内存占用,请尝试以下操作:

如果您不需要从此哈希映射中获取密钥,则可以使用不存储密钥但仅存储密钥的哈希映射.为此,使用size_t密钥类型,std::identity<std::size_t>对于内部哈希函数,并通过手动调用哈希函数来访问它std::hash<VectorType>.

std::unordered_map<std::size_t, int, std::identity<std::size_t> > counters;
std::hash<VectorType> hashFunc;

for (VectorType vec : vectors) {
    counters[hashFunc(vec)]++;
}

这减少了内存,但需要额外的努力来解释结果,因为您必须第二次循环原始数据结构才能找到原始向量(然后通过再次对它们进行哈希查找它们在哈希映射中).