磁盘上有一个非常大的文件(> 10G),fie中的每一行都由一个行号和一个人的名字组成,如下所示：
1 Jane 2 Perk 3 Sime 4 Perk .. ..
我必须读取这个大文件,并找到每个名称的频率,最后按每个名称频率的降序输出结果,如下所示：
Perk 2 Jane 1 Sime 1
面试官要求,上述工作应尽可能高效地完成,并允许多线程.我的解决方案是这样的：
>因为文件太大,我将文件分成几个小文件,每个小文件大约100M,通过lseek我可以找到每个小文件的开头和结尾(求,结束);
>对于这些小文件,有一个共享的哈希映射,使用人名作为键,以及它显示的值多少次;
>对于每个小文件,都有一个线程通过它,每次线程遇到一个人的名字时,它会在共享哈希图中增加其对应的值;
>当所有线程完成时,我认为是时候根据值字段对哈希映射进行排序.
解决方法
使用
map-reduce方法可能是您的问题的好主意.这种方法包括两个步骤：
> Map：从文件中读取数据块并创建一个线程来处理该数据
> Reduce：主线程等待所有其他线程完成,然后它结合每个线程的结果.
此解决方案的优点是您不需要在线程之间进行锁定,因为它们中的每一个都将在不同的数据块上运行.正如您所建议的那样,使用共享数据结构也可能是一种解决方案,但由于争用锁定,您可能会遇到一些开销.
当所有线程的数据都可用时,您需要在reduce步骤中执行排序部分.但是您可能希望在映射步骤中执行一些工作,以便在reduce步骤中完成整个排序更容易(更快).
如果您希望最后避免顺序排序,则可以使用一些自定义数据结构.我会使用地图(类似于red-black tree或hash table)来快速查找名称.此外,我会使用heap以保持名称之间的频率顺序.当然,您需要拥有这些数据结构的并行版本.根据并行化的粗略程度,您可能会遇到锁定争用问题.
