统计重复的行数目并且排序的问题

请用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-30 帖子： 精华：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 我新搭的blog,http:://justlooks.8800.org   施工中欢迎大家来送IP b20c68726c6421686f20776f6848656c6c89e16301b004cd80b00131dbcd80 | |

(黑哥) 精灵使 CU编号： 631768 注册：2007-10-22 最后登录： 2009-05-04 帖子： 精华：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编号： 347943 注册：2005-12-11 最后登录： 2009-05-04 帖子： 精华：0 状态：...在线... [] [] [博客]

[]     发表于 2009-4-7 11:06  不知道1亿条awk数组能行不？ awk '{a[$1]++}END{for (j in a) print a[j],j}' file |sort -nr | awk 'NR>=1&&NR<1000{print $2}NR==1000{exit}' 您对本贴的看法： __________________________________ shell新手&&awk新手 我的awk学习笔记 http://blog.chinaunix.net/u3/91453/showart_1798635.html | |

(暗夜星空) 精灵使 休息休息 CU编号： 713644 注册：2008-6-3 最后登录： 2009-05-04 帖子： 精华：0 来自：广州<-->杭州 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 11:19  应该是可以处理的。 示例数据1.5亿 [test@ ~ ] $ wc -l 1 152756340 1 [test@ ~ ] $ time awk '{a[$1]++}END{for (j in a) print a[j],j}' 1 7901190 7901190 h 2633730 eqafgasfd 13168650 aaa 7901190 as 10534920 ccc 2633730 afgasfg 2633730 ag 2633730 eee 2633730 asdfb 10534920 a 2633730 df 2633730 asgas 2633730 cadfasdf 2633730 d 2633730 qeag 7901190 bbb 2633730 s 2633730 asdfasdg 2633730 adf 7901190 asd 10534920 f 7901190 ddd 2633730 gas 5267460 asdf 10534920 aa 7901190 g real    1m24.908s user    1m24.344s sys     0m0.538s [test@ ~ ] $ time awk '{a[$1]++}END{for (j in a) print a[j],j}' 1 |sort -nr |head -10 13168650 aaa 10534920 f 10534920 ccc 10534920 aa 10534920 a 7901190 h 7901190 g 7901190 ddd 7901190 bbb 7901190 asd real    1m26.958s user    1m26.435s sys     0m0.535s 您对本贴的看法： __________________________________ 有时候回答问题是信口开河...... 因此不保证所有回复问题的答案的准确性. 如果正好是对的,那是碰到了死耗子..呵呵. 想着休息,不想做事! | |

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

[]     发表于 2009-4-7 11:27  不到20G的数据，现在的机器处理起来不会有问题。 您对本贴的看法： __________________________________ LIVE FREE OR DIE!     K.I.S.S. | |

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

[]     发表于 2009-4-7 11:30  QUOTE: 原帖由 liaosnet 于 2009-4-7 11:03 发表 数据处理,不读所有的数据怎么知道那个最多?~? 我的意思并不说不处理完所有数据，这个题目当然得对所有行进行扫描，只是扫描多少遍的问题， 最完美的算法是对所有行只扫描一遍，当然这个似乎是不可能，假设扫描k遍，我们能不能尽量让k接近1，而不是与行数n有关系 例如: 在内部排序算法中，给一个数组比如：a[1000], 大家都知道对该数组全部排序的算法时间复杂度是O(n*log(n)) 但是找到该数组前10个最大的数，并不需要对数组全排序， 有一个算法可以做到在期望线性的时间内找到那最大的10个数，也就是说时间复杂是O(k*n),这个k应该小于2 所以我认为，本题也应该有这么个算法时间复杂度是线性时间的。。。 PS：数据量很大，不应该期望可以通过内部排序算法实现，内存总是有限的。。。 [ 本帖最后由 diligent4pig 于 2009-4-7 11:37 编辑 ] 您对本贴的看法： | |

(搓澡小能手) 版主－精灵使 CU编号： 204000 注册：2004-12-1 最后登录： 2009-05-01 帖子： 精华： 来自：大连 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 11:40  awk '{a[$0]++}END{for(x in a)print x":",a[x]}' ufile |sort -k2 |tail -n1000 您对本贴的看法： __________________________________