通过多线程处理大文件

发布时间：2020-12-14 23:31:56 所属栏目：Java 来源：网络整理

导读：磁盘上有一个非常大的文件( 10G),fie中的每一行都由一个行号和一个人的名字组成,如下所示： 1 Jane2 Perk3 Sime4 Perk.. .. 我必须读取这个大文件,并找到每个名称的频率,最后按每个名称频率的降序输出结果,如下所示： Perk 2Jane 1Sime 1 面试官要求,上述工

磁盘上有一个非常大的文件(> 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以保持名称之间的频率顺序.当然,您需要拥有这些数据结构的并行版本.根据并行化的粗略程度,您可能会遇到锁定争用问题.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!