-2

这是一个算法问题。为了清楚起见，我对工作代码不感兴趣，而是对如何普遍处理任务感兴趣。

我们有一个有 4 个 CPU 的服务器，没有数据库。有 100,000 个 HTML 文档存储在磁盘上。每个文档的大小为 2MB。我们需要一种有效的方法来确定出现在该集合中的单词“CAMERA”（不区分大小写）的计数。

我的方法是

  • 解析 HTML 文档以仅提取单词
  • 然后对单词进行排序，
  • 然后对该集合使用二进制搜索。

换句话说，我会创建线程，让它们使用所有 4 个 CPU 将 HTML 文档解析为单个大型单词集合文本文件，然后对其进行排序，然后使用二进制搜索。

你觉得这怎么样？

4

5 回答 5

2

你试过grep吗？这就是我会做的。

可能需要进行一些实验才能找出传递大量数据的正确方法，并提前确保结果正确，因为这需要一点时间。

我不建议对那么多数据进行排序。

于 2013-01-05T21:24:44.573 回答
0

您可以使用 Boyer-Moore 算法。很难说哪种编程语言适合制作这样的应用程序，但是您可以使用 C++ 制作它，以便直接优化您的本机代码。显然你需要使用多线程。
在 HTML 文档解析库中，您可以选择 Xerces-C++。

于 2013-01-04T13:09:17.847 回答
0

如果您的文档位于单个本地硬盘驱动器上，您将受到 I/O 的限制，而不是 CPU。

我会使用非常简单的方法，简单地将每个文件串行加载到内存中并扫描内存以搜索目标词并增加计数器。

如果您尝试使用 4 个线程来加速它（例如每个线程 25000 个文件），它可能会使其变慢，因为 I/O 不喜欢来自竞争进程/线程的重叠访问模式。

但是，如果文件分布在多个硬盘驱动器上，则应启动与驱动器一样多的线程，并且每个线程应仅从该驱动器读取数据。

于 2013-01-04T10:51:38.780 回答
0

好吧，这不是一个完整的伪代码答案，但我认为没有。要获得最佳性能，您需要了解很多有关硬件架构的知识。以下是注释：

  1. 根本不需要对数据进行排序，也不需要使用二分查找。只需读取文件（从磁盘顺序读取每个文件），然后搜索是否出现相机一词。
  2. 程序中的瓶颈很可能是 IO（磁盘读取），因为磁盘访问比 CPU 计算慢得多。因此，要优化程序 - 应该专注于优化磁盘读取。
  3. 要优化磁盘读取，应该知道它的架构。例如，如果您只有一个磁盘（并且没有 RAID），假设磁盘可以同时处理单个请求，那么多线程实际上没有意义。如果是这种情况 - 使用单个线程。
  4. 但是，如果您有多个磁盘 - 无论您有多少内核，您都应该生成 #disks 线程（假设文件在磁盘之间均匀分离）。既然是瓶颈，通过多个线程同时向磁盘请求数据，你就可以让它们都工作，有效地减少时间消耗。
于 2013-01-04T10:53:44.793 回答
0

就像是？

htmlDocuments = getPathsOfHtmlDocuments()
threadsafe counter = new Counter(0)
scheduler = scheduler with max 4 threads
for(htmlDocument: htmlDocuments){
  scheduler.schedule(new SearchForCameraJob("Camera",htmlDocument,counter))
}
wait while scheduler.hasUnfinishedJobs
print Found camera +counter+ times


class SearchForCameraJob(searchString, pathToFile, counter){
    document = readFile(pathToFile);
    while(document.findNext(searchString)){
    counter.increment();    
   }
}
于 2013-01-04T10:54:40.490 回答