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

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

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

查找最常访问的页面ID访问顺序：

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

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

我的想法：

1. 将文件的每个项目放入map1<key:user_id, list > 。
2. 当list.size() == 3 ，创建一个新的struct three_hits来保存三个pageID。
3. 将它放入map2 。
4. 然后，在map2中找到具有最大计数器值的项目。

声明：

  struct three_hits { int f_page; int s_page; int t_page; }; map<string, list > map_hit; map 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 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 tmp(r.pageID); map_hit[r.uid]=tmp; } } // O(n) 

迭代map_t_hits一次以找到具有最高值的键（ t_hits ）。

地图的时间O（n lg n）和空间O（n） 。

更好的解决方案？

Answer 1

您可以考虑使用sort-merge执行此操作。 首先使用用户id的稳定排序将给定用户的所有序列放在一起，保持原始顺序。 然后对所有3个网页序列进行排序，最后计算相等序列的运行。 这也是O（n log n）。 它可能需要花费更多的时间在实践中，但如果使用内部存储器运行可能需要更少的存储，并且可以在外部存储器中运行，如果您在任何时候都有太多的数据存储。 它是否真的更好取决于你的具体情况的细节。