c++ - 我应该使用什么类型的稀疏 vector ？

Question

数据

我有N索引的不同(排序) vector (std::vector<unsigned int>)。索引在 [0; L-1]。以下是有关此数据的两条经验法则:

• 只有大约 0.1% 到 10% 的可能索引出现在任何地方
• 如果在给定的 vector 中找到一个索引，那么它很可能会在其他 vector 中多次找到。

因此可能的数据集为 N=10 vector 和 L = 200可能是

{45, 110, 119, 145, 170}
{9, 45, 110, 145, 178, 170}
{45, 145}
{45, 178, 183}
{45, 53, 110, 170}
{9, 119, 123, 179}
{9, 45, 119, 130, 131, 170, 190, 199}
{9, 45, 110, 170, 199}
{31, 45, 145}
{9, 178, 183}

目标

我想计算每个索引的频率。我会做类似的事情

std::vector<double> computeFrequencies(std::vector<std::vector<unsigned int>>& data)
{
    assert(data.size() == N);

    std::vector<double> frequencies(L);
    for (unsigned Ni = 0 ; Ni < N ; Ni++)
    {
        for (unsigned i = 0 ; i < data[Ni].size() ; i++)
        {
            assert(data[Ni][i] < L)
            frequencies[data[Ni][i]]++;
        }
    }

    for (unsigned i = 0 ; i < L; i++)
    {
        frequencies[i] /= (double) N;
    }

    return(frequencies);    
}

然后我将再次遍历函数 computeFrequencies 返回的对象只有一次。

for (unsigned i = 0 ; i < L; i++)
{
    foo(frequencies[i]);
}

问题

对象 frequencies包含很多零点，因此我应该改用稀疏 vector 。虽然我对稀疏矩阵了解不多。我应该使用什么类型的稀疏 vector ？

我正在考虑使用 boost::numeric::ublas::coordinate_matrix<double><double>因为当我遍历所有 N vector ，我会不断添加新的非零值，我认为坐标矩阵可以很好地处理这个问题。请注意，一般来说，对于此功能，我更担心 RAM 使用而不是计算时间。

Answer 1

看起来稀疏 vector 表示不太适合您的问题。

按照您的描述完成您的任务:

1. 将已排序的 vector 合并为一个已排序的 vector 。如何进行高效的 K-way 合并时不时地出现在这里:merging N sorted files using K way merge
2. 遍历新 vector 并计算每个条目的重复次数(很容易，因为它们都在一起)以获得您的频率并在您进行时foo它们。

您甚至可以同时执行这两个步骤，完全避免将数据复制到新结构中的需要。