我应该使用什么类型的稀疏向量？

Question

数据

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

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

因此，具有 N=10 向量和 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 包含很多零，因此我应该改用稀疏向量。虽然我对稀疏矩阵了解不多。我应该使用什么类型的稀疏向量？

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

Answer 1

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

完成您描述的任务：

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

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

我应该使用什么类型的稀疏向量？

What type of sparse vector should I use?

c++

containers

sparse-matrix

data-structures