【请教】一个面试题——文件内容按行排序问题

diligent4pig

请用SHELL完成下列排序：

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

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

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


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

欢迎各位不吝赐教~~~

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

justlooks

sort file|uniq -c|sort -r

blackold

try:

1. sort urfile|uniq -c|sort -r |head -n 1000

复制代码

我是DBA

用一千万的数据测了一下

1. [test@ ~ ] $ time awk '{a[$1]=$1;b[$1]++}END{for (i in a ) print a[i],b[i]}' 2
   
2. aaa 4757211
   
3. ccc 3171474
   
4. bbb 1585737
   
5. ddd 1585737
   
6. 
   
7. real    0m12.042s
   
8. user    0m11.975s
   
9. sys     0m0.067s

复制代码

我是DBA

[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

飞鸿无痕

效率的话用awk的话可能会高一点吧？

ly5066113

这个 a[$1]=$1 是多余的，浪费了很多内存。

ywlscpl

你这个是还没排序和输出前1000

diligent4pig

原帖由 justlooks 于 2009-4-7 10:39 发表
sort file|uniq -c|sort -r

我觉得这样对所有行都排列了。。。而题目只需要找出次数出现最大的1000个数据就行，
所以这个算法效率应该不高~~~

另外的那个awk，不是蛮懂，等我看看awk再评论，呵呵~~~

继续期待高效率解决方案。。。

我是DBA

谢谢指教，我改。