在一个非常大的文件中查找最常见的三项序列。

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是最流行的三页序列。

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

但是，由于我必须使用两个哈希表，内存不能同时容纳所有的东西，所以我必须使用磁盘。经常访问磁盘是不有效的。

我怎么才能做得更好？

Answer 1

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

如果您希望得到确切的结果，请使用外部排序过程按userid对日志进行排序，然后每3个连续条目组合一次，并再次排序，这一次是按页ID排序。

更新(按时间戳排序)

为了正确使用日志文件的时间戳，可能需要进行一些预处理：

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

Update2 (改进近似方法)

对于随机分布的数据，采用LRU队列的近似方法会产生很好的效果。但是网页访问在一天中的不同时间可能有不同的模式，或者在周末可能有所不同。最初的方法可能会给这类数据带来糟糕的结果。为了改进这一点，可以使用分层LRU队列。

将LRU队列划分为日志(N)小队列。尺寸N/2，N/4，.最大的元素应该包含任何元素，下一个元素，至少看到2次，第二次-至少4次，.如果从某个子队列中删除元素，则将其添加到另一个子队列中，因此它驻留在所有的子队列中，这些子队列在层次结构较低的所有子队列中存在，然后才被完全删除。这样的优先级队列仍然具有O(1)复杂度，但允许对大多数流行页面进行更好的近似。

Answer 2

这里可能有大量的语法错误，但是对于一个几乎无限长的日志文件来说，这应该占用有限的RAM。

typedef int pageid;
typedef int userid;
typedef pageid[3] sequence;
typedef int sequence_count;

const int num_pages = 1000; //where 1-1000 inclusive are valid pageids
const int num_passes = 4;
std::unordered_map<userid, sequence> userhistory;
std::unordered_map<sequence, sequence_count> visits;
sequence_count max_count=0;
sequence max_sequence={};
userid curuser;
pageid curpage;
for(int pass=0; pass<num_passes; ++pass) { //have to go in four passes
    std::ifstream logfile("log.log");
    pageid minpage = num_pages/num_passes*pass; //where first page is in a range
    pageid maxpage = num_pages/num_passes*(pass+1)+1;
    if (pass==num_passes-1) //if it's last pass, fix rounding errors
        maxpage = MAX_INT;
    while(logfile >> curuser >> curpage) { //read in line
        sequence& curhistory = userhistory[curuser]; //find that user's history
        curhistory[2] = curhistory[1];
        curhistory[1] = curhistory[0];
        curhistory[0] = curhistory[curpage]; //push back new page for that user
        //if they visited three pages in a row
        if (curhistory[2] > minpage && curhistory[2]<maxpage) { 
            sequence_count& count = visits[curhistory]; //get times sequence was hit
            ++count; //and increase it
            if (count > max_count) { //if that's new max
                max_count = count;  //update the max
                max_sequence = curhistory; //arrays, so this is memcpy or something
            }
        }
    }
}
std::cout << "The sequence visited the most is :\n";
std::cout << max_sequence[2] << '\n';
std::cout << max_sequence[1] << '\n';
std::cout << max_sequence[0] << '\n';
std::cout << "with " << max_count << " visits.\n";

请注意，如果您的pageid或userid是strings而不是ints，那么您将面临很大的速度/大小/缓存损失。

EDIT2现在在4(可自定义的)传递中工作，这意味着它使用较少的内存，这使得在RAM中实现了这一工作。只是按比例变慢了。

Answer 3

如果你有1000个网页，那么你就有10亿个可能的3页序列。如果您有一个32位计数器的简单数组，那么您将使用4GB的内存。也许有一些方法可以通过丢弃数据来减少这一点，但是如果你想保证得到正确的答案，那么这将永远是你的最坏情况--这是不可避免的，在一般情况下发明节省内存的方法将使最坏情况下的内存更加匮乏。

最重要的是，你必须跟踪用户。对于每个用户，您需要存储他们访问的最后两个页面。假设在日志中按名称引用用户，则需要将用户的名称存储在哈希表中，加上两个页码，因此假设每个用户平均24字节(可能比较保守--我假设的是短用户名)。有1000个用户，为24 be；有1000000用户，为24 be。

显然，序列计数器控制了内存问题。

如果您只有1000页，那么在现代64位计算机中，4GB内存并不是不合理的，特别是有大量磁盘支持的虚拟内存。如果您没有足够的交换空间，您只需创建一个swap文件(在Linux上--我猜想Windows有类似的东西)，并且依赖于操作系统总是有内存中缓存的大多数用例。

因此，基本上，数学规定，如果你有大量的页面要跟踪，你想要能够应付最坏的情况，那么你将不得不接受，你将不得不使用磁盘文件。

我认为有限容量的哈希表可能是正确的答案。您可能可以根据可用内存对特定机器进行优化。这样，您就需要处理表达到容量的情况。如果你很少到那里的话，它可能不需要很高的效率。以下是一些想法：

• 删除了最常用的文件序列，从而保留了内存中最常见的序列。我需要两次通过这个表来确定哪一个级别低于平均水平，然后再进行驱逐。不知何故，你需要知道你把每个条目放在哪里，每当你得到一个散列遗漏，这可能会很棘手。
• 只是把整个表转储到文件中，然后从头构建一个新的表。重复一遍。最后，重新组合所有表中的匹配项。最后一部分可能也很棘手，
• 使用mmapped文件来扩展表。确保该文件主要用于最常用的序列，如我的第一个建议。基本上，您只需将其用作虚拟内存--在地址被遗忘之后，该文件将变得毫无意义，但您不需要将其保存那么长时间。我假设这里没有足够的常规虚拟内存，而且/或您不想使用它。显然，这只适用于64位系统.