6

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

我通过将原始数据从 a 反转为 a 来实现这一点std::map（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 来做到这一点。

哦，还有，如果有人想知道，这既不是作业，也不是面试问题。

4

4 回答 4

4

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

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

所以你可以做这样的事情：

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 函数，但可能会失去其他一些好处）

于 2012-06-06T12:01:25.000 回答
2

这取决于您所说的“更有效”是什么意思。首先，这真的是瓶颈吗？当然，100k 条目很多，但如果您只需要每隔几分钟执行一次，那么算法需要几秒钟就可以了。

我看到的唯一需要改进的地方是内存使用。如果这是一个问题，您可以跳过多图的生成，只保留一个计数器图，如下所示（注意，我的 C++ 有点生疏）：

std::map<int, int> countFrequency; // count => how many customers with that count

for ( std::map<int, int>::const_iterator it = uc.begin();
        it != uc.end();  ++it )
{
    // If it->second is not yet in countFrequency, 
    // the default constructor initializes it to 0.
    countFrequency[it->second] += 1;
}

// Now write this out
for ( std::map<int, int>::const_iterator it = countFrequency.begin();
        it != countFrequency.end();  ++it )
{
    std::cout << "==> There are "
            << it->second << " users that have bought "
            << it->first << " products(s)" << std::endl;
}

如果添加了用户并购买了count商品，您可以countFrequency使用

countFrequency[count] += 1;

如果现有用户从oldCount到项目，newCount您可以更新countFrequency

countFrequency[oldCount] -= 1;
countFrequency[newCount] += 1;

现在，顺便说一句，我建议使用unsigned intfor count（除非负数有正当理由）和 typedef'ing 一个userID类型，以增加可读性。

于 2012-06-06T12:08:40.820 回答
1

如果可以的话，我建议始终保持这两条数据都是最新的。换句话说，我会维护第二张地图，将购买的产品数量映射到购买那么多产品的客户数量。如果您维护它，此地图包含您问题的确切答案。每次客户购买产品时，设 n 为该客户现在购买的产品数量。从键 n-1 的值中减去 1。将键 n 处的值加一。如果键的范围足够小，这可能是一个数组而不是一个映射。您是否期望一个客户购买数百种产品？

于 2012-06-06T12:01:13.760 回答
1

只是为了百灵，这是一种混合方法，vector如果数据很小，则使用 amap来涵盖一个用户购买了真正荒谬数量的产品的情况。我怀疑您是否真的需要在商店应用程序中使用后者，但更一般的问题版本可能会从中受益。

typedef std::map<int, int> Map;
typedef Map::const_iterator It;

template <typename Container>
void get_counts(const Map &source, Container &dest) {
    for (It it = source.begin(); it != source.end(); ++it) {
        ++dest[it->second];
    }
}

template <typename Container>
void print_counts(Container &people, int max_count) {
    for (int i = 0; i <= max_count; ++i) {
        if contains(people, i) {
            std::cout << "==> There are "
                << people[i] << " users that have bought "
                << i << " products(s)" << std::endl;
        }
    }
}


// As an alternative to this overloaded contains(), you could write
// an overloaded print_counts -- after all the one above is not an 
// efficient way to iterate a sparsely-populated map. 
// Or you might prefer a template function that visits
// each entry in the container, calling a specified functor to
// will print the output, and passing it the key and value.
// This is just the smallest point of customization I thought of.
bool contains(const Map &c, int key) {
    return c.count(key);
}
bool contains(const std::vector<int, int> &c, int key) {
    // also check 0 < key < c.size() for a more general-purpose function
    return c[key]; 
}

void do_everything(const Map &uc) {
    // first get the max product count
    int max_count = 0;
    for (It it = uc.begin(); it != uc.end(); ++it) {
        max_count = max(max_count, it->second);
    }

    if (max_count > uc.size()) { // or some other threshold
        Map counts;
        get_counts(uc, counts);
        print_counts(counts, max_count);
    } else {
        std::vector<int> counts(max_count+1);
        get_counts(uc, counts);
        print_counts(counts, max_count);
    }
}

从这里你可以重构，创建一个类模板CountReOrderer，它接受一个模板参数，告诉它是使用 avector还是 amap进行计数。

于 2012-06-06T13:03:06.217 回答