c++ - 在非常大的文件中查找最常见的三项序列

Question

我有许多网页访问日志文件，其中每次访问都与用户 ID 和时间戳相关联。我需要确定最流行(即最常访问)的三页序列。日志文件太大，无法一次保存在主内存中。

示例日志文件:

User ID  Page ID
A          1
A          2
A          3
B          2
B          3
C          1
B          4
A          4

对应结果:

A： 1-2-3， 2-3-4
B： 2-3-4
2-3-4 is the most popular three-page sequence

我的想法是使用两个哈希表。第一个散列用户 ID 并存储其序列；第二个散列三页序列并存储每个序列出现的次数。这需要 O(n) 空间和 O(n) 时间。

但是，由于我必须使用两个哈希表，内存不能同时保存所有内容，我必须使用磁盘。频繁访问磁盘效率不高。

我怎样才能做得更好？

Answer 1

如果您想快速获得近似结果，请按照您的意图使用哈希表，但为每个哈希表添加一个大小有限的队列以删除最近最少使用的条目。

如果您想要准确的结果，请使用外部排序程序按用户 ID 对日志进行排序，然后每 3 个连续条目合并一次并再次排序，这次是按页面 ID。

更新(按时间戳排序)

可能需要一些预处理才能正确使用日志文件的时间戳:

• 如果日志文件已经按时间戳排序，则无需预处理。
• 如果有多个日志文件(可能来自独立进程)，并且每个文件都已按时间戳排序，则打开所有这些文件并使用归并排序读取它们。
• 如果文件几乎按时间戳排序(好像几个独立的进程将日志写入单个文件)，请使用二进制堆以正确的顺序获取数据。
• 如果文件不按时间戳排序(这在实践中不太可能)，请使用按时间戳进行外部排序。

Update2(改进近似方法)

使用 LRU 队列的近似方法应该对随机分布的数据产生相当好的结果。但是网页访问可能在一天中的不同时间有不同的模式，或者在周末可能会有所不同。对于此类数据，原始方法可能会产生较差的结果。为了改善这一点，可以使用分层 LRU 队列。

将 LRU 队列划分为 log(N) 个较小的队列。尺寸为 N/2, N/4, ... 最大的应该包含任何元素，下一个 - 仅元素，至少看到 2 次，下一个 - 至少 4 次，... 如果元素从某个子元素中删除-queue，它被添加到另一个队列中，因此它在完全删除之前存在于所有层次较低的子队列中。这样的优先级队列仍然具有 O(1) 复杂度，但可以更好地逼近最流行的页面。