一个面试题——文件内容按行排序问题

请用SHELL完成下列排序：

有一个文件，每行记录了字符串（长度为1-127字节），大约有1亿行，请排出重复次数最高的前1000条。（可以用awk、sed等工具）。

比如问如下：
aaa
ccc
ccc
ddd
aaa
aaa
bbb

那么重复次数为：
aaa 3次
ccc 2次
ddd 1次
bbb 1次


当然不局限于shell，这只是一个工具而已，关键在与排序算法

欢迎各位不吝赐教~~~

PS：请尽量考虑效率问题。因为数据量实在是太大了。。。。

您对本贴的看法：

| |

风云使者 CU编号： 692772 注册：2008-4-16 最后登录： 2009-04-09 帖子： 精华：0 状态：...在线... [] [] [博客]

[]     发表于 2009-4-7 10:39  sort file|uniq -c|sort -r 您对本贴的看法： __________________________________ GNU sed 版本 4.1.5    GNU awk 3.1.5 grep 2.5.1 b20c68726c6421686f20776f6848656c6c89e16301b004cd80b00131dbcd80 | |

(黑哥) 精灵使 CU编号： 631768 注册：2007-10-22 最后登录： 2009-04-09 帖子： 精华：0 状态：...在线... [] [] [博客]

[]     发表于 2009-4-7 10:41  回复 #1 diligent4pig 的帖子 try: CODE: sort urfile|uniq -c|sort -r |head -n 1000 您对本贴的看法： __________________________________ LIVE FREE OR DIE!     K.I.S.S. | |

(我在学习，我要进步) 精灵使 打破水锅问到底。 CU编号： 713644 注册：2008-6-3 最后登录： 2009-04-09 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 10:42  回复 #2 justlooks 的帖子 用一千万的数据测了一下 CODE: [test@ ~ ] $ time awk '{a[$1]=$1;b[$1]++}END{for (i in a ) print a[i],b[i]}' 2 aaa 4757211 ccc 3171474 bbb 1585737 ddd 1585737 real    0m12.042s user    0m11.975s sys     0m0.067s 您对本贴的看法： __________________________________ C 初学，请多多指教。 | |

(我在学习，我要进步) 精灵使 打破水锅问到底。 CU编号： 713644 注册：2008-6-3 最后登录： 2009-04-09 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 10:46  回复 #3 blackold 的帖子 [test@ ~ ] $ time sort 2|uniq -c|sort -r |head -n 1000       4757211 aaa 3171474 ccc 1585737 ddd 1585737 bbb real    2m14.546s user    2m23.612s sys     0m0.499s 您对本贴的看法： __________________________________ C 初学，请多多指教。 | |

天使 CU编号： 639775 注册：2007-11-10 最后登录： 2009-04-09 帖子： 精华：0 状态：...在线... [] [] [博客]

[]     发表于 2009-4-7 10:51  效率的话用awk的话可能会高一点吧？ 您对本贴的看法： __________________________________ 找工作中，深圳，哪里需要linux系统工程师或者系统管理员？？？ | |

(Tim) 法师 CU编号： 465018 注册：2006-9-13 最后登录： 2009-04-09 帖子： 精华：0 来自：长春 状态：...在线... [] [] [博客]

[]     发表于 2009-4-7 10:53  回复 #4 我是DBA 的帖子 这个 a[$1]=$1 是多余的，浪费了很多内存。 您对本贴的看法： __________________________________ 记住该记住的，忘记该忘记的。改变能改变的，接受不能改变的。 | |

天使 CU编号： 347943 注册：2005-12-11 最后登录： 2009-04-09 帖子： 精华：0 状态：...在线... [] [] [博客]

[]     发表于 2009-4-7 10:54  回复 #5 我是DBA 的帖子 你这个是还没排序和输出前1000 您对本贴的看法： __________________________________ shell新手&&awk新手 我的awk学习笔记 http://blog.chinaunix.net/u3/91453/showart_1798635.html | |

新手 CU编号： 1323563 注册：2009-4-7 最后登录： 2009-04-07 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 10:57  QUOTE: 原帖由 justlooks 于 2009-4-7 10:39 发表 sort file|uniq -c|sort -r 我觉得这样对所有行都排列了。。。而题目只需要找出次数出现最大的1000个数据就行， 所以这个算法效率应该不高~~~ 另外的那个awk，不是蛮懂，等我看看awk再评论，呵呵~~~ 继续期待高效率解决方案。。。 您对本贴的看法： | |

(我在学习，我要进步)

精灵使
打破水锅问到底。




CU编号： 713644
注册：2008-6-3
最后登录： 2009-04-09
帖子：
精华：0







状态：...离线...

[] [] [博客]

awk '{a[$1]++}END{for (i in a)print a,i }' 4|tail -1000

您对本贴的看法：

__________________________________

小学生

| |

风云使者 CU编号： 692772 注册：2008-4-16 最后登录： 2009-04-09 帖子： 精华：0 状态：...在线... [] [] [博客]

[]     发表于 2009-4-7 16:09  不对比还真不知道 time sort testfile|uniq -c|sort -r|head -10 real    10m10.407s user    7m10.591s sys     1m12.293s time awk '{a[$0]++}END{for(i in a)print a" "i}' testfile|sort -r|head -10 real    0m7.066s user    0m6.564s sys     0m0.252s time sort -r <(awk '{a[$0]++}END{for(i in a)print a" "i}' testfile)|head -10 real    0m14.158s user    0m0.012s sys     0m0.012s 差的真大 wc -l testfile 9999999 testfile 您对本贴的看法： __________________________________ GNU sed 版本 4.1.5    GNU awk 3.1.5 grep 2.5.1 b20c68726c6421686f20776f6848656c6c89e16301b004cd80b00131dbcd80 | |

新手 CU编号： 1324611 注册：2009-4-7 最后登录： 2009-04-08 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 21:12  QUOTE: 原帖由 justlooks 于 2009-4-7 16:09 发表 不对比还真不知道 time sort testfile|uniq -c|sort -r|head -10 real    10m10.407s user    7m10.591s sys     1m12.293s time awk '{a[$0]++}END{for(i in a)print a" "i}' testfile|sort -r|head  ... awk '{a[$0]++}END{for(i in a)print a" "i}'file |sort -r|head  ... [ 本帖最后由 jioyo源 于 2009-4-7 21:15 编辑 ] 您对本贴的看法： | |

新手 CU编号： 1324611 注册：2009-4-7 最后登录： 2009-04-08 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 21:14  QUOTE: 原帖由 wtuter 于 2009-4-7 14:29 发表 awk '{a[$1]++}END{for (i in a)print a,i }' 4|tail -1000 awk '{a[$1]++}END{for (i in a)print a [ i ] ,i }' 4|tail -1000 [ 本帖最后由 jioyo源 于 2009-4-7 21:16 编辑 ] 您对本贴的看法： | |

新手 CU编号： 1324611 注册：2009-4-7 最后登录： 2009-04-08 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 21:17  什么情况？为什么我打a[]出不来？非要a ［ ］才可以。 您对本贴的看法： | |

风云使者 皇家救星 CU编号： 796256 注册：2008-12-20 最后登录： 2009-04-09 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 21:25  连着的[ i ]在帖子里是表示斜体的意思 您对本贴的看法： __________________________________ 三分天注定 七分靠打拼 | |

禁止访问－侠客 CU编号： 1322960 注册：2009-4-7 最后登录： 2009-04-08 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-8 09:21  网赚 *** 作者被禁止或删除 内容自动屏蔽 ***

风云使者 CU编号： 804020 注册：2009-1-17 最后登录： 2009-04-09 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-8 09:49  哪位懂perl，用perl测试下。总听人说perl处理数据效率高，不过自己还不懂呢~ 您对本贴的看法： __________________________________ [e-mail] [e-mail] | |

侠客 CU编号： 771611 注册：2008-10-11 最后登录： 2009-04-08 帖子： 精华：0 状态：...离线... [] [] [博客]

[]     发表于 2009-4-8 10:37  回复 #17 diligent4pig 的帖子 恩，用所谓的置换排序。 (1)按字符串的第一个字符的ASCII码(10进制表示)HASH创建或者取得文件，比如字符串"abc"，就创建（如果不存在）或者打开(如果存在)文件97.temp (2)将该字符串存入该文件，比如"abc"存入文件"a.temp"。存入的方法一条记录，格式为"字符串：频率"。如果该字符串在文件中已经有了，则频率加1，如果没有，追加之。 (3)如果输入的数据平均分布的话，在按照上面的方式处理完所有的数据（几亿）后，你会得到文件名为0.temp一直到127.temp的128个文件。 如果要处理的数据更多，你也可以按照字符串的前两个字符HASH来得到文件(可得到128 * 128个文件)。总之，HASH的方式你可以根据输入的复杂度来取舍。 (4)把0.temp文件排序并得到前1000个。当然，如果0.temp文件很大的话（输入数据分布不均匀），还可以对它在按照上述方式HASH之（HASH方法自己决定），得到更多的子文件。 (5)从其他文件中依次取出记录，与内存中的第1000个记录比较，如果新字符串比该记录的频率高，则置换之，否则继续。 (6)用step5处理完所有数据后，内存中的这1000个即为所求。 PS: 楼主说的对，公司给出1亿这个数字没有实际用处，只是告诉你文件很大很大，必须先外排序(可以用数据库或者文件) 您对本贴的看法： | |

天使 CU编号： 161265 注册：2004-5-27 最后登录： 2009-04-08 帖子： 精华：0 状态：...保密... [] [] [博客]

[]     发表于 2009-4-8 17:18  用sort就已经是正解了，如果你想了解真正的排序原理和动作的话,用c去写吧！sort也不过是读取一遍文件而已！ 您对本贴的看法： | |

[]    

发表于 2009-4-7 11:00 

回复 #7 ly5066113 的帖子

谢谢指教，我改。

您对本贴的看法：

__________________________________

C 初学，请多多指教。