最新消息:

大文件的排序和去重 超级简单的实现

linux admin 2293浏览 0评论

有一道校招生的面试题,是要给一个很大的文件(不能全部放内存,比如1T)按行来排序和去重。

一种简单解决方案就是分而治之,先打大文件分词大小均匀的若干个小文件,然后对小文件排好序,最后再Merge所有的小文件,在Merge的过程中去掉重复的内容。

在Linux下实现这个逻辑甚至不用自己写代码,只要用shell内置的一些命令: split, sort就足够了。我们把这个流程用脚本串起来,写到shell脚本文件里。文件名叫sort_uniq.sh.

#!/bin/bash
lines=$(wc -l $1 | sed 's/ .*//g')
lines_per_file=`expr $lines / 20`
split -d -l $lines_per_file $1 __part_$1

for file in __part_*
do
{
  sort $file > sort_$file
} &
done
wait

sort -smu sort_* > $2
rm -f __part_*
rm -f sort_*

使用方法:./sort_uniq.sh file_to_be_sort file_sorted

这段代码把大文件分词20或21个小文件,后台并行排序各个小文件,最后合并结果并去重。

如果只要去重,不需要排序,还有另外一种思路:对文件的每一行计算hash值,按照hash值把该行内容放到某个小文件中,假设需要分词100个小文件,则可以按照(hash % 100)来分发文件内容,然后在小文件中实现去重就可以了。

转自:http://www.cnblogs.com/yangxudong/p/3848453.html

 

 

转载请注明:jinglingshu的博客 » 大文件的排序和去重 超级简单的实现


Warning: Use of undefined constant PRC - assumed 'PRC' (this will throw an Error in a future version of PHP) in /usr/share/nginx/html/wp-content/themes/d8/comments.php on line 17
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址