|
精华帖 (0) :: 良好帖 (9) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-01
taojingrui 写道 这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。
方法1 基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。 提示： 1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M 2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小） 3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次） 方法2 建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间） 楼上的方法第一个没看懂怎么能实现这个要求的； 第二个感觉不现实，你随便找一个数据库试试，插入1亿条要花多长时间 开头的分析很像一回事 |
| 返回顶楼 | |
|
发表时间：2010-04-01
感觉像是一道智力题。
最好的办法是数据拆分，分布式计算。 比如像前面有人所说的拆分成10W*1000这种形式的。 每次读取10W个数字到内存中进行排序，取出top100保存，然后释放刚刚读取的10W数字数组。如此，总共需要做1000次。最后会得到1000个包含top100的数组，将这些数组合并成一个总共为10W个数字的数组，最后再取top100。 这种算法应该是最有效率，最节约资源的。 |
| 返回顶楼 | |
|
发表时间：2010-04-01
luke_kai的TreeSet的思路是正确的。
|
| 返回顶楼 | |
|
发表时间：2010-04-01
这个题的条件应该不足吧
1.这1亿的数据在哪里？ 如果在内存里面。红黑树就够了 2.如果数据不在内存里，那说明有可能内存是肯定装不下的。如果在数据库里面。·给一个1亿的数据建个索引那是相当恐怖的。如果没有索引。就不要建索引了。采用分批的方式。比如每次取100w的数据红黑树。最后合并。如果有索引的话··直接取就是了吧。 |
| 返回顶楼 | |
|
发表时间：2010-04-01
最后修改：2010-04-01
J-catTeam 写道 这个题的条件应该不足吧
1.这1亿的数据在哪里？ 如果在内存里面。红黑树就够了 2.如果数据不在内存里，那说明有可能内存是肯定装不下的。如果在数据库里面。·给一个1亿的数据建个索引那是相当恐怖的。如果没有索引。就不要建索引了。采用分批的方式。比如每次取100w的数据红黑树。最后合并。如果有索引的话··直接取就是了吧。 |
| 返回顶楼 | |
|
发表时间：2010-04-01
wilddonkey 写道
taojingrui 写道
这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。
方法1 基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。 提示： 1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M 2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小） 3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次） 方法2 建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间） 楼上的方法第一个没看懂怎么能实现这个要求的； 第二个感觉不现实，你随便找一个数据库试试，插入1亿条要花多长时间 开头的分析很像一回事
其实第二种方法在实际应用中是经常存在的，似想一下，腾讯要在所有QQ用户（上亿用户）中找到某类的top100用户，该怎么找，怎么排序？QQ用户的信息早就存在数据库里了。方法二不是我想的，是当年考我类似这种题目的考官告诉我的，目的是要告诉我，面试的考题有些时候不仅仅是考算法能力，还考察一个人的发散思维。考官告诉我，10个人考这样的题，9个人拿起题就考虑怎样去通过自己写程序实现，但是其实很多东西用现成的就好。题目要求的是考“如何从大量数字中取出 top 100”，不是考如何导入数据。 至于第一种方法是针对内存处理的。类似QQ这样的系统，有上亿用户，平时在线的都有上千万，如果要在内存中保存上亿用户的登陆状态，该如何保存？要快速查找到某一个用户的登陆状态（或更改登陆状态）该如何处理？方法一就是解决办法之一。快速查找用户，和题目要求的取top100，实质上是要解决如何在大数据总量下快速查找特定数据。 其实方法二，不算特别了，我还见过更有趣的方法。怎么算？一个候选人说道，一般的算法都解决不了这么大的数目（内存不够），所以随便找一个算法（能处理1千万大小的排序就行），然后采用分布式，把1亿数字分成10份，起10个应用分别排序，每个应用算出自己的top100，然后将10个top100放到一起，再排序一次。候选人还补充说，他的方法别说1亿，就是1万亿的数目，都能处理，当然速度方面就另说了。至少我老板就非常欣赏这个候选人的想法，这个候选人也被成功录用了。 |
| 返回顶楼 | |
|
发表时间：2010-04-01
taojingrui 写道
wilddonkey 写道
taojingrui 写道
这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。
方法1 基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。 提示： 1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M 2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小） 3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次） 方法2 建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间） 楼上的方法第一个没看懂怎么能实现这个要求的； 第二个感觉不现实，你随便找一个数据库试试，插入1亿条要花多长时间 开头的分析很像一回事
其实第二种方法在实际应用中是经常存在的，似想一下，腾讯要在所有QQ用户（上亿用户）中找到某类的top100用户，该怎么找，怎么排序？QQ用户的信息早就存在数据库里了。方法二不是我想的，是当年考我类似这种题目的考官告诉我的，目的是要告诉我，面试的考题有些时候不仅仅是考算法能力，还考察一个人的发散思维。考官告诉我，10个人考这样的题，9个人拿起题就考虑怎样去通过自己写程序实现，但是其实很多东西用现成的就好。题目要求的是考“如何从大量数字中取出 top 100”，不是考如何导入数据。 至于第一种方法是针对内存处理的。类似QQ这样的系统，有上亿用户，平时在线的都有上千万，如果要在内存中保存上亿用户的登陆状态，该如何保存？要快速查找到某一个用户的登陆状态（或更改登陆状态）该如何处理？方法一就是解决办法之一。快速查找用户，和题目要求的取top100，实质上是要解决如何在大数据总量下快速查找特定数据。 其实方法二，不算特别了，我还见过更有趣的方法。怎么算？一个候选人说道，一般的算法都解决不了这么大的数目（内存不够），所以随便找一个算法（能处理1千万大小的排序就行），然后采用分布式，把1亿数字分成10份，起10个应用分别排序，每个应用算出自己的top100，然后将10个top100放到一起，再排序一次。候选人还补充说，他的方法别说1亿，就是1万亿的数目，都能处理，当然速度方面就另说了。至少我老板就非常欣赏这个候选人的想法，这个候选人也被成功录用了。
|
| 返回顶楼 | |
|
发表时间：2010-04-01
taojingrui 写道 这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。
方法1 基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。 提示： 1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M 2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小） 3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次） 方法2 建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间） 对于方法1, bit的确是解决很多问题的好方法. 但是我有一点疑问, 在这个问题中用bit数组, 数据如何初始化呢, i如何才能取到? 另外, 对于非整形数据, 这样就不适用了. |
| 返回顶楼 | |
|
发表时间：2010-04-01
大哥我看了下你的代码..内存不溢出就见鬼了
|
| 返回顶楼 | |
|
发表时间：2010-04-01
bit[]应该是比较好解决办法。
|
| 返回顶楼 | |
