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

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

[]     发表于 2009-4-7 10:29  请用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编号： 713644 注册：2008-6-3 最后登录： 2009-05-04 帖子： 精华：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 您对本贴的看法： __________________________________ 有时候回答问题是信口开河...... 因此不保证所有回复问题的答案的准确性. 如果正好是对的,那是碰到了死耗子..呵呵. 想着休息,不想做事! | |

(暗夜星空) 精灵使 休息休息 CU编号： 713644 注册：2008-6-3 最后登录： 2009-05-04 帖子： 精华：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 您对本贴的看法： __________________________________ 有时候回答问题是信口开河...... 因此不保证所有回复问题的答案的准确性. 如果正好是对的,那是碰到了死耗子..呵呵. 想着休息,不想做事! | |

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

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

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

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

天使 CU编号： 347943 注册：2005-12-11 最后登录： 2009-05-04 帖子： 精华：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-13 帖子： 精华：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-05-04 帖子： 精华：0 来自：广州<-->杭州 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 11:00  回复 #7 ly5066113 的帖子 谢谢指教，我改。

回复 #9 diligent4pig 的帖子

不处理完所有数据怎么知道各自重复的次数？

您对本贴的看法：

__________________________________

shell新手&&awk新手
我的awk学习笔记
http://blog.chinaunix.net/u3/91453/showart_1798635.html

| |

(暗夜星空) 法王 休息休息 CU编号： 306408 注册：2005-8-25 最后登录： 2009-05-04 帖子： 精华：0 来自：广州<-->杭州 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 11:02  QUOTE: 原帖由 我是DBA 于 2009-4-7 11:00 发表 谢谢指教，我改。 内存多就不在乎了~:mrgreen: :mrgreen: 您对本贴的看法： __________________________________ 有时候回答问题是信口开河...... 因此不保证所有回复问题的答案的准确性. 如果正好是对的,那是碰到了死耗子..呵呵. 想着休息,不想做事! | |

(暗夜星空) 法王 休息休息 CU编号： 306408 注册：2005-8-25 最后登录： 2009-05-04 帖子： 精华：0 来自：广州<-->杭州 状态：...离线... [] [] [博客]

[]     发表于 2009-4-7 11:03  QUOTE: 原帖由 diligent4pig 于 2009-4-7 10:57 发表 我觉得这样对所有行都排列了。。。而题目只需要找出次数出现最大的1000个数据就行， 所以这个算法效率应该不高~~~ 另外的那个awk，不是蛮懂，等我看看awk再评论，呵呵~~~ 继续期待高效率解决方案。。。 数据处理,不读所有的数据怎么知道那个最多?~? 您对本贴的看法： __________________________________ 有时候回答问题是信口开河...... 因此不保证所有回复问题的答案的准确性. 如果正好是对的,那是碰到了死耗子..呵呵. 想着休息,不想做事! | |

天使 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 您对本贴的看法： __________________________________ 我要用我的双手，为大秦澡堂，搓出一个大大的市场!!! | |

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

[]     发表于 2009-4-7 12:10  第一遍扫描统计重复行数，剩下的工作也就是排序了，考数据结构么？ 您对本贴的看法： __________________________________ GNU sed 版本 4.1.5    GNU awk 3.1.5 grep 2.5.1 我新搭的blog,http:://justlooks.8800.org   施工中欢迎大家来送IP b20c68726c6421686f20776f6848656c6c89e16301b004cd80b00131dbcd80 | |

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

[]     发表于 2009-4-7 12:31  排序汇总吧　如果数据量实在太大那就分割排序，　最后合并汇总 您对本贴的看法： __________________________________ 三分天注定 七分靠打拼