6

磁盘上有一个相当大的文件（>10G），文件中的每一行由一个行号和一个人的名字组成，如下所示：

1 Jane
2 Perk
3 Sime
4 Perk
.. ..

我必须阅读这个大文件，找到每个名字的频率，最后按每个名字的频率降序输出结果，如下所示：

Perk 2
Jane 1
Sime 1

按照面试官的要求，上面的工作应该尽可能高效地完成，并且允许多线程。我的解决方案是这样的：

  1. 因为文件太大，我把文件分割成几个小文件，每个小文件大约100M，通过lseek我可以定位每个小文件的开头和结尾(beg, end)；

  2. 对于这些小文件，有一个以人名作为键的共享哈希映射，以及它显示的次数作为值；

  3. 对于每个小文件，都有一个单独的线程经过，每次线程遇到一个人的名字，都会value在共享的hash-map中增加对应的值；

  4. 当所有线程都完成后，我认为是时候根据value字段对哈希图进行排序了。

但是由于该文件中的名称可能太多，因此排序会很慢。我没有想出如何按降序输出名称的好主意。

希望任何人都可以帮助我解决上述问题，给我一个更好的解决方案，告诉我如何通过多线程和排序的东西来完成这项工作。

4

5 回答 5

7

使用map-reduce方法可能是解决您的问题的好主意。该方法将包括两个步骤：

  1. Map：从文件中读取数据块并创建一个线程来处理该数据
  2. Reduce：主线程等待所有其他线程完成，然后结合每个单独线程的结果。

此解决方案的优点是您不需要在线程之间进行锁定，因为它们中的每一个都将对不同的数据块进行操作。正如您所提议的那样，使用共享数据结构也可能是一种解决方案，但是由于争用锁定，您可能会有一些开销。

当所有线程的数据都可用时，您需要在 reduce 步骤中进行排序部分。但是您可能希望在 map 步骤中做一些工作，以便在 reduce 步骤中更容易（更快）完成完整的排序。

如果您希望避免最后的顺序排序，您可以使用一些自定义数据结构。我会使用地图（类似于红黑树或哈希表）来快速查找名称。此外，我会使用堆来保持名称之间的频率顺序。当然，您需要拥有这些数据结构的并行版本。根据并行化的粗糙程度，您可能会遇到锁定争用问题。

于 2012-07-19T10:18:51.210 回答
6

如果我在面试问题中使用“高效”这个词问这个问题，我会期望得到类似“cut -f 2 -d ' ' < file | sort | uniq -c”的答案，因为效率通常是关于不浪费时间解决问题已经解决了问题。实际上，这是个好主意，我会在我们的面试问题中添加类似的内容。

您的瓶颈将是磁盘，因此各种多线程都在过度设计解决方案（这也会影响“效率”）。如果有旋转的磁盘，像这样拆分你的读取会使事情变慢，或者至少会使缓冲区缓存更加混乱，并且不太可能启动落后算法。坏主意，不要这样做。

于 2012-07-19T10:52:46.080 回答
3

我不认为多线程是一个好主意。程序的“慢”部分是从磁盘读取，多线程从磁盘读取不会使其更快。它只会使它变得更加复杂（例如，对于每个块，您必须找到第一个“完整”行，并且您必须协调各个线程，并且每次访问时都必须锁定共享哈希映射） . 您可以使用“本地”哈希映射，然后在最后合并它们（当所有线程完成时（在 10gb 的末尾），部分哈希映射被合并）。现在您不需要同步对共享地图的访问。

我认为对生成的哈希映射进行排序将是最简单的部分，如果可以将完整的哈希映射保存在内存中:-) 你只需将它复制到一个malloc(ed) 内存块中，qsort然后通过它的计数器来复制它。

于 2012-07-19T10:13:48.613 回答
3

您在解决方案中的 (2) 和 (4) 步骤使其基本上是连续的（第二个引入了锁定以保持哈希映射一致，最后一个是您尝试对所有数据进行排序的地方）。

最后对 hash-map 进行一步排序有点奇怪，你应该使用增量排序技术，如 heapsort（锁定所需的数据结构）或 mergesort（对“直方图”文件的部分进行排序，但避免合并一切“最后都在一个主线程中”-尝试创建排序网络并在排序的每个步骤中混合输出文件的内容）。

多线程读取可能是一个问题，但对于现代 SSD 驱动器和激进的读取缓存，多线程并不是主要的减速因素。这都是关于同步结果排序过程的。

这是合并排序的并行化示例：http: //dzmitryhuba.blogspot.com/2010/10/parallel-merge-sort.html

再一次，正如我所说，一些排序网络可能有助于实现高效的并行排序，但不是简单的“等待所有子线程和排序结果”。也许，如果你有很多处理器，双音排序。

于 2012-07-19T10:21:11.663 回答
3

面试官最初的问题是“......并且允许使用多线程”。这个问题的措辞可能有点模棱两可，但问题的精神很明显：面试官要求候选人编写一个程序来解决问题，并分析/证明在建议的解决方案。这是一个简单的问题，用于测试候选人思考大规模问题并解释他们做出的算法选择的能力，确保候选人没有在不理解的情况下从互联网网站上反刍。

鉴于此，无论是否使用多线程，这个特定的面试问题都可以在 O( n log n )（渐近地说）内有效地解决，并且多线程还可以用于以对数方式加速实际执行时间。

解决方案概述

如果您被顶级公司问到 OP 的问题，以下方法将表明您确实了解问题和所涉及的问题。在这里，我们提出了一个两阶段的方法：

  1. 该文件首先被分区并读入内存。

  2. 分区上使用了特殊版本的合并排序，该分区在对文件进行排序时同时记录每个名称的频率。

例如，让我们考虑一个具有 32 个名称的文件，每个名称长一个字母，并且每个名称的初始频率计数为 1。上述策略可以形象化如下：

1. File:           ARBIKJLOSNUITDBSCPBNJDTLGMGHQMRH                32 Names

2. A|R|B|I|K|J|L|O|S|N|U|I|T|D|B|S|C|P|B|N|J|D|T|L|G|M|G|H|Q|M|R|H 32 Partitions
   1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1 with counts

3.  AR  BI  JK  LO  NS  IU  DT  BS CP  BN  DJ  LT  GM  GH  MQ  HR  Merge #1
    11  11  11  11  11  11  11  11 11  11  11  11  11  11  11  11  and tally

4.   ABRI    JKLO    INSU    BDST   BCNP    DJLT    GHM     HMQR   Merge #2
     1111    1111    1111    1111   1111    1111    211     1111   and tally

5.     ABIJKLOR         BDINSTU       BCDJLNPT         GHMQR       Merge #3
       11111111         1111211       11111111         22211       and tally

6.           ABDIJKLNORSTU                  BCDGHJLMNPQRT          Merge #4
             1212111111211                  1112211211111          and tally

7.                       ABCDGHIJKLMNOPQRSTU                       Merge #5
                         1322111312132113121                       and tally

因此，如果我们从头到尾读取内存中的最终列表，它会产生排序列表：

A|B|C|D|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
1|3|2|2|1|1|1|3|1|2|1|3|2|1|1|3|1|2|1 = 32 Name instances (== original file).


为什么解决方案是有效的

无论是否使用哈希表（如原始海报所建议的那样），以及是否使用多线程，这个问题的任何解决方案都不能比 O( n log n ) 更有效地解决，因为必须执行排序。鉴于此限制，可以采用两种策略：

  1. 从磁盘读取数据，使用哈希表管理名称/频率总计，然后对哈希表内容进行排序（原发帖人建议的方法）

  2. 从磁盘读取数据，用文件中的频率总数初始化每个名称，然后合并排序名称，同时对每个名称的所有总数求和（此解决方案）。

方案（1）要求在读入所有数据后对哈希表进行排序。方案（2）在排序时进行频率统计，从而消除了哈希表的开销。完全不考虑多线程，我们已经可以看到，即使对于解决方案 (1) 使用最有效的哈希表实现，解决方案 (2) 已经更有效，因为它根本没有哈希表的开销。

多线程的约束

在解决方案 (1) 和解决方案 (2) 中，假设解决方案 (1) 使用了有史以来最有效的哈希表实现，两种算法都在 O( n log n ) 中渐近执行相同的操作；只是它们的操作顺序略有不同。然而，虽然多线程解决方案 (1) 实际上会减慢其执行速度，但多线程解决方案 (2) 将在速度上获得显着提高。这怎么可能？

如果我们使用多线程解决方案 (1)，无论是在从磁盘读取还是在之后的排序中，都会遇到哈希表争用问题，因为所有线程都试图同时访问哈希表。特别是对于写入表，这种争用可能会大大削弱解决方案 (1) 的执行时间，以至于在没有多线程的情况下运行它实际上会提供更快的执行时间。

为了使多线程能够加快执行时间，有必要确保每个线程执行的每个工作块都独立于其他每个线程。这将允许所有线程以最大速度运行而不会争用共享资源并更快地完成工作。解决方案 (2) 正是这样做的，它完全删除了哈希表并使用了Merge Sort，这是一种分而治之的算法，允许将问题分解为彼此独立的子问题。

多线程和分区以进一步缩短执行时间

为了多线程合并排序，可以将文件划分为多个分区，并创建一个新线程来合并每个连续的分区对。由于文件中的名称是可变长度的，因此必须从头到尾连续扫描文件才能进行分区；不能对文件进行随机访问。但是，由于任何解决方案都必须至少扫描一次文件内容，因此仅允许对文件进行串行访问仍然会产生最佳解决方案。

多线程解决方案 (2) 可以预期什么样的执行时间加速？鉴于其简单性，该算法的分析非常棘手，并且是各种白皮书的主题。但是，将文件分成n 个分区将使程序的执行速度 ( n / log( n )) 比在没有文件分区的单个 CPU 上快几倍。简单来说，如果单个处理器需要 1 小时来处理一个 640GB 的文件，那么将文件分成 64 个 10GB 的块并在具有 32 个 CPU 的机器上执行将使程序在大约 6 分钟内完成，增加了 10 倍（忽略磁盘开销）。

于 2012-07-30T05:47:30.713 回答