有效地重新排序基于C++地图的集合的方法

Question

我有一个大的(ish - > 100K)集合将用户标识符(一个int)映射到他们购买的不同产品的数量(也是一个int.)我需要尽可能有效地重新组织数据有多少用户拥有不同数量的产品.例如,有多少用户有1个产品,有多少用户有两个产品等.

我通过将原始数据从a std::map转换为a std::multimap(其中键和值被简单地反转)来实现这一点.然后,我可以选择使用N个产品的用户数量count(N)(尽管我也将值唯一地存储在一个集合中,所以我可以确定我迭代的值的确切数量及其顺序)

代码如下所示:

// uc is a std::map<int, int> containing the  original
// mapping of user identifier to the count of different
// products that they've bought.
std::set<int> uniqueCounts;
std::multimap<int, int> cu; // This maps count to user.

for ( map<int, int>::const_iterator it = uc.begin();
        it != uc.end();  ++it )
{
    cu.insert( std::pair<int, int>( it->second, it->first ) );
    uniqueCounts.insert( it->second );
}

// Now write this out
for ( std::set<int>::const_iterator it = uniqueCounts.begin();
        it != uniqueCounts.end();  ++it )
{
    std::cout << "==> There are "
            << cu.count( *it ) << " users that have bought "
            << *it << " products(s)" << std::endl;
}

我不禁感到这不是最有效的方法.有人知道这样做的聪明方法吗？

我受限于我不能使用Boost或C++ 11来做到这一点.

哦,如果有人想知道,这既不是家庭作业,也不是面试问题.

Answer 1

假设您知道单个用户可以购买的最大产品数量，则仅使用向量来存储操作结果可能会获得更好的性能。事实上，您将需要为原始地图中的几乎每个条目进行分配，这可能不是最快的选择。

它还会减少映射上的查找开销，获得内存局部性的好处，并用向量的恒定时间查找替换对多重映射的计数调用（这不是恒定时间操作）。

所以你可以这样做：

std::vector< int > uniqueCounts( MAX_PRODUCTS_PER_USER );

for ( map<int, int>::const_iterator it = uc.begin();
        it != uc.end();  ++it )
{
    uniqueCounts[ uc.second ]++;
}

// Now write this out
for ( int i = 0, std::vector< int >::const_iterator it = uniqueCounts.begin();
        it != uniqueCounts.end();  ++it, ++i )
{
    std::cout << "==> There are "
            << *it << " users that have bought "
            << i << " products(s)" << std::endl;
}

即使您不知道产品的最大数量，您似乎也可以猜测最大值并根据需要调整此代码以增加向量的大小。无论如何，它肯定会导致比原始示例更少的分配。

当然，所有这些都是假设您在处理这些数据后实际上并不需要用户 ID（正如下面的评论所指出的，为每个用户购买的产品数量是一个相对较小且连续的集合。否则，您可能最好使用地图代替向量 - 您仍然可以避免调用 multimap::count 函数，但可能会失去一些其他好处）