我有一个大的(ish – > 100K)集合将用户标识符(int)映射到他们购买的不同产品的数量(也是一个int.)我需要尽可能有效地重新组织数据找到有多少用户拥有不同数量的产品.例如,有多少用户有1个产品,有多少用户有两个产品等.
我通过将原始数据从std :: map转换为std :: multimap(其中键和值被简单地反转)来实现这一点.然后,我可以使用count(N)选择具有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来做到这一点.
哦,如果有人想知道,这既不是家庭作业,也不是面试问题.
解决方法
假设您知道单个用户可以购买的最大产品数量,您可能会看到仅使用向量来存储操作结果的更好性能.因为它是原始地图中几乎每个条目都需要分配,这可能不是最快的选择.
它还可以减少地图上的查找开销,获得内存局部性的好处,并使用向量的恒定时间查找替换调用以计算多图(这不是常量时间操作).
所以你可以这样做：
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函数,但可能会失去一些其他好处)
