簡單實現大文件的排序和去重

有一道校招生的面試題，是要給一個很大的文件（不能全部放內存，比如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）來分發文件內容，然后在小文件中實現去重就可以了。