Alc*_*ott 6 c algorithm large-files
磁盘上有一个非常大的文件(> 10G),fie中的每一行都由一个行号和一个人的名字组成,如下所示:
1 Jane
2 Perk
3 Sime
4 Perk
.. ..
我必须读取这个大文件,并找到每个名称的频率,最后按每个名称频率的降序输出结果,如下所示:
Perk 2
Jane 1
Sime 1
面试官要求,上述工作应尽可能高效地完成,并允许多线程.我的解决方案是这样的:
因为文件太大,我把文件分成几个小文件,每个小文件都是关于100M,通过lseek我可以找到每个小文件的开头和结尾(beg, end);
对于这些小文件,有一个使用人名作为键的共享哈希映射以及它显示的值多少次;
对于每个小文件,都有一个线程通过它,每次线程遇到一个人的名字时,它会value在共享的哈希图中增加其对应的;
当所有线程完成后,我认为是时候根据value字段对哈希映射进行排序.
但是因为该文件中的名称可能太多,所以排序会很慢.我没有想出如何按降序输出名称.
希望任何人都能帮助我解决上述问题,通过多线程和排序方法为我提供更好的解决方案.
使用map-reduce方法可能是您的问题的好主意.这种方法包括两个步骤:
此解决方案的优点是您不需要在线程之间进行锁定,因为它们中的每一个都将在不同的数据块上运行.正如您所建议的那样,使用共享数据结构也可能是一种解决方案,但由于争用锁定,您可能会遇到一些开销.
当所有线程的数据都可用时,您需要在reduce步骤中执行排序部分.但是您可能希望在映射步骤中执行一些工作,以便在reduce步骤中完成整个排序更容易(更快).
如果您希望最后避免顺序排序,则可以使用一些自定义数据结构.我会使用地图(类似于红黑树或哈希表)来快速查找名称.而且,我会使用堆来保持名称之间的频率顺序.当然,您需要拥有这些数据结构的并行版本.根据并行化的粗略程度,您可能会遇到锁定争用问题.
如果我使用"有效"这个词作为面试问题,我会期待一个类似"cut -f 2 -d"'<file | sort | uniq -c"的答案,因为效率通常不会浪费时间来解决问题.已经解决了问题.实际上,这是一个好主意,我会在面试问题中添加这样的内容.
您的瓶颈将是磁盘,因此各种多线程都在过度设计解决方案(这也会影响"效率").如果存在旋转磁盘或者至少使缓冲区缓存更加混乱并且不太可能启用后退算法,那么拆分这样的读取将使速度变慢.不好的主意,不要这样做.