19

这是一道面试题。假设有几台计算机，每台计算机都保存一个非常大的访问 URL 日志文件。查找前十个访问量最大的 URL。

例如：假设只有 3 台计算机，我们需要前两个访问量最大的 URL。

计算机 A：url1、url2、url1、url3
计算机 B：url4、url2、url1、url1
计算机 C：url3、url4、url1、url3

url1 在所有日志中出现 5 次
网址2 2
网址3 3
网址4 2

所以答案是 url1, url3

日志文件太大而无法放入 RAM 并通过网络复制它们。据我了解，使计算并行并使用所有给定的计算机也很重要。

你会怎么解决？

4

6 回答 6

17

这是一个非常标准的问题，有一个众所周知的解决方案。您只需按 URL 对每台计算机上的日志文件进行排序，然后通过“主”计算机上大小为 k（您想要的项目数）的优先级队列将它们合并。这种技术自 1960 年代就已经存在，并且至今仍以MapReduce的形式使用（尽管稍作修改） 。

在每台计算机上，从日志文件中提取 URL 和计数，然后按 URL 排序。由于日志文件大于内存，因此您需要进行磁盘合并。这需要读取日志文件的一块，按 URL 排序，将块写入磁盘。读取下一个块、排序、写入磁盘等。在某些时候，您有 M 个日志文件块，每个块都已排序。然后，您可以进行 M 路合并。但是，不是将项目写入磁盘，而是按排序顺序（即按 URL 排序）将它们呈现给“主”。

每台机器都会对自己的日志进行排序。

“主”计算机合并来自不同计算机的数据并进行前 K 个选择。这实际上是两个问题，但可以合二为一。

master 创建两个优先级队列：一个用于合并，一个用于前 K 选择。第一个大小为 N，其中 N 是它合并数据的计算机数量。第二个是大小 K：您要选择的项目数。我为此使用了最小堆，因为它既简单又相当快。

要设置合并队列，请初始化队列并从每台“工作”计算机中获取第一项。在下面的伪代码中，“从合并队列中获取最低项目”是指从合并队列中获取根项目，然后从提供该项目的任何工作计算机中获取下一个项目。因此，如果队列包含[1, 2, 3]，并且项目来自计算机 B、C、A（按此顺序），那么获取最低项目将意味着从计算机 B 获取下一个项目并将其添加到优先级队列中。

然后，master 执行以下操作：

working = get lowest item from merge queue
while (items left to merge)
{
    temp = get lowest item from merge queue
    while (temp.url == working.url)
    {
        working.count += temp.count
        temp = get lowest item from merge queue
    }
    // Now have merged counts for one url.
    if (topK.Count < desired_count)
    {
        // topK queue doesn't have enough items yet.
        // so add this one.
        topK.Add(working);
    }
    else if (topK.Peek().count < working.count)
    {
        // the count for this url is larger
        // than the smallest item on the heap
        // replace smallest on the heap with this one
        topK.RemoveRoot()
        topK.Add(working)
    }
    working = temp;
}
// Here you need to check the last item:
if (topK.Peek().count < working.count)
{
    // the count for this url is larger
    // than the smallest item on the heap
    // replace smallest on the heap with this one
    topK.RemoveRoot()
    topK.Add(working)
}

此时，topK队列中包含计数最高的 K 个项目。

因此，每台计算机都必须进行归并排序，即 O(n log n)，其中n是该计算机日志中的项目数。主服务器上的合并是 O(n)，其中n是来自各个计算机的所有项目的总和。挑选前 k 个项目是 O(n log k)，其中n是唯一url 的数量。

当然，这些排序是并行完成的，每台计算机都准备自己的排序列表。但是排序的“合并”部分是在主计算机合并的同时完成的，所以有一些协调，所有机器都在那个阶段参与。

于 2013-03-25T13:15:47.487 回答
3

鉴于日志文件的规模和问题的一般性质，这是一个很难解决的问题。我不认为所有情况都有一种最佳算法。这取决于日志文件内容的性质。例如，采取极端情况，即所有 URL 在所有日志文件中都是唯一的。在那种情况下，基本上任何解决方案都需要很长时间才能得出这个结论（如果它甚至达到那么远......），甚至没有答案，因为没有前十名。

我没有可以呈现的无懈可击的算法，但我会探索一种解决方案，它使用 URL 的哈希值直方图，而不是 URL 本身。这些直方图可以通过一次性文件读取来计算，因此它可以处理任意大小的日志文件。在伪代码中，我会选择这样的东西：

  • 使用具有有限目标空间（例如 10,000，注意预计会发生冲突的哈希值）的哈希函数来计算日志文件中每个项目的哈希值，并计算每个 has 值出现的次数。将生成的直方图传达给服务器（尽管也可以通过将结果多播到每个其他节点来完全避免中央服务器——但我将在这里坚持使用更明显的服务器方法）
  • 服务器应合并直方图并将结果传回。根据 URL 的分布，可能已经有许多清晰可见的峰值，其中包含访问次数最多的 URL。
  • 然后，每个节点都应该关注直方图中的峰值。它应该再次通过其日志文件，使用额外的哈希函数（同样具有有限的目标空间）为那些在其中一个峰值中具有其第一个哈希值的 URL（要关注的峰值数量）计算新的哈希直方图on 将是算法中要调整的参数，具体取决于 URL 的分布），并使​​用新的哈希值计算第二个直方图。结果应该传送到服务器。
  • 服务器应再次合并结果并分析新直方图与原始直方图。根据清晰可见的峰值，它可能已经能够得出关于前十个 URL 的两个哈希值的结论。或者它可能必须指示机器使用第二个散列函数计算更多的散列值，并且可能在那之后通过另一个散列函数进行第三遍散列计算。这必须继续，直到可以从直方图的集体组得出结论，峰值 URL 的哈希值是什么，然后节点可以从中识别不同的 URL。

请注意，这种机制需要对算法和散列函数的几个方面进行调整和优化。它还需要服务器编排，以便随时进行哪些计算。当无法得出结论时，可能还需要设置一些界限以便得出结论，换句话说，当 URL 哈希值的“频谱”太平而无法继续计算时。

但是，如果 URL 中有明确的分布，这种方法应该可以很好地工作。我怀疑，实际上，这个问题只在这种情况下才有意义。

于 2013-03-25T16:13:28.147 回答
1

假设以下条件为真：

  • 您需要 m 个主机的前 n 个 url。
  • 您不能将文件存储在 RAM 中
  • 有一个主节点

我会采取以下方法：

每个节点读取文件的一部分（即 MAX 个 url，其中 MAX 可以是，比如说 1000 个 url）并保存一个数组 arr[MAX]={url,hits}。

当一个节点从文件中读取了 MAX 个 urls 时，它会将列表发送到主节点，并重新开始读取，直到再次达到 MAX 个 urls。

当一个节点到达 EOF 时，他将剩余的 url 列表和一个 EOF 标志发送到主节点。

当主节点收到一个 url 列表时，它会将它与它的最后一个 url 列表进行比较，并生成一个新的、更新的。

当主节点从每个节点接收到EOF标志并完成读取他自己的文件时，他的列表的最后一个版本的前n个url就是我们正在寻找的那些。

或者

一种不同的方法可以让 master 不再做所有的工作：

每个节点读取它的文件并存储一个与上面相同的数组，一直读取到 EOF。

EOF时，节点会将列表的第一个url和命中数发送给m​​aster。

当 master 收集到每个节点的第一个 url 和命中数时，它会生成一个列表。如果主节点的 url 少于 n 个，它将要求节点发送第二个，依此类推。直到 master 对 n 个 url 进行排序。

于 2013-03-25T12:50:31.480 回答
1

预处理：每个计算机系统处理完整的日志文件并准备唯一 URL 列表并对其进行计数。

获取热门 URL：

  1. 计算每个计算机系统的 URL 计数
  2. 中央系统的整理过程（虚拟）
    • 按 DESC 顺序（即从最顶部开始）将带有计数的 URL 一个一个发送到中央处理单元
    • 在中央系统整理传入的 URL 详细信息
    • 重复直到来自传入 URL 的所有计数的总和小于主列表中第十个 URL 的计数。绝对确定的重要一步

PS：您将拥有跨系统的前十个 URL，不一定按此顺序。要获得实际订单，您可以反向排序。对于前十名的给定 URL，从 dist-computers 获得单独的计数并形成最终订单。

于 2013-03-25T12:45:40.010 回答
1

在每个节点上计算 URL 的出现次数。然后使用分片功能将 url 分发到另一个拥有 URL 密钥的节点。现在每个节点都有唯一的键。然后在每个节点上再次减少以获取 URL 的出现次数，然后找到前 N 个 URL。最后只发送前 N 个 url 到主节点，主节点将在 K*N 项中找到前 N 个 URls，其中 K 是节点数。

Eg: K=3
N1 - > url1,url2,url3,url1,url2
N2 - > url2,url4,url1,url5,url2
N3 - > url1,url4,url3,url1,url3

第 1 步：计算每个节点中每个 url 的出现次数。

 N1 -> (url1,2),(url2,2),(url3,1)
 N2 -> (url4,1),(url2,2),(url5,1),(url1,1)
 N3 -> (url1,2),(url3,2),(url4,1)

第二步：分片使用哈希函数（为简单起见，设为url数%K）

 N1 -> (url1,2),(url1,1),(url1,2),(url4,1),(url4,1)
 N2 -> (url2,2),(url2,2),(url5,1)
 N3 -> (url3,2),(url3,1)

步骤4：再次查找节点内每个键的出现次数。

N1 -> (url1,5),(url4,2)
N2 -> (url2,4),(url5,1)
N3 -> (url3,3)

第 5 步：仅将前 N 个发送给 master。令 N=1

Master -> (url1,5),(url2,4),(url3,3)

对结果进行排序并获得前 1 项，即 url1

第 1 步称为 map 侧缩减，这样做是为了避免在第 2 步中发生巨大的 shuffle。

于 2021-02-12T02:40:55.307 回答
0

下面的描述是解决方案的想法。它不是伪代码。
考虑您有一系列系统。
1.for each A: Collections(systems)
1.1）在每台计算机上运行一个守护进程A，探测日志文件的变化。
1.2) 当发现变化时，唤醒 AnalyzerThreadA
1.3) 如果 AnalyzerThreadA 使用一些正则表达式找到 URL，则使用 count++ 更新 localHashMapA。
（键 = URL，值 = 计数）。
2) 将localHashMapA 的前十个条目推送到将运行AnalyzeAll 守护程序的ComputerA。

上述步骤将是每个系统的最后一步，它将前十个条目推送到主系统，例如：computerA。

3) 在computerA 中运行的AnalyzeAll 将解析URL 的masterHashMap 中的重复项和更新计数。

4) 从 masterHashMap 打印 topTen。

于 2013-03-25T12:31:28.493 回答