c++ - 如何从具有 userID 和 pageID 的大型日志文件中查找最常访问的 3 个网页序列

Question

给定访问网页的日志文件:

Userid  PageID
A          1
A          2
A          3
B          2
B          3
C          1
B          4
A          4

查找page-ID最常访问的序列:

 for A : 1-2-3, 2-3-4
 for B : 2-3-4

所以，2-3-4 是最常见的。

我的想法:

1. 将文件的每一项放入 map1<key:user_id, list<pageID> > .
2. 何时 list.size() == 3 ，创建一个新结构three_hits保存三个pageID。
3. 放入 map2<struct three_hits, int counter> .
4. 然后，找到map2中计数器值最大的项。

声明:

 struct three_hits
 {
     int f_page;
     int s_page;
     int t_page;  
 };
 map<string, list<int> > map_hit;
 map<struct three_hits, int> map_t_hits;

扫描记录:

for each( record: r in log)
{
    if(map_hit.count(r.userid) >0) 
    {
        map_hit[r.uid].second.push_back(r.pageID);

        if(map_hit[r.uid].second.size() ==3)
        {

            list<int> tmp=map_hit[r.uid].second;

            t_hits(tmp[0],tmp[1],tmp[2]);

            // O(n lg n)
            if( map_t_hits.count(t_hits) >0)
                map_t_hits[t_hits]++;
            else
                map_t_hits[t_hits]=1;
        }
        else
        { 
            list<int> tmp(r.pageID);

            map_hit[r.uid]=tmp;
        }
    }
    // O(n)

迭代map_t_hits一次找到具有最高值的键( t_hits )。

map 的时间 O(n lg n) 和空间 O(n)。

还有更好的解决方案吗？

Answer 1

您可以考虑使用排序合并来执行此操作。首先按用户 ID 使用稳定排序将给定用户的所有序列放在一起，保持原始顺序。然后对所有 3 个网页序列进行排序，最后计算相等序列的运行次数。这也是 O(n log n)。在实践中，它可能需要更多的时间，但如果使用内部存储器运行，则可能需要更少的存储，并且如果您有太多数据无法一次存储，则可以在外部存储器中排序运行。它实际上是否更好取决于您特定情况的细节。