【探讨】给你1G内存，如何从3000万个手机号码中检索出你要的号码，要求每秒检索>1000次

给你1G内存，如何从3000万个手机号码中检索出你要的号码，要求每秒检索>1000次

大家来探讨，发表您的意见！

评论

25 楼 fly_hyp 2008-06-03  

终极解决方案：
将手机号用整数表示，一个手机号占4byte内存
将所有手机号排序放入3000万的整数数组中。
4 * 3000 * 10000 需要 120M内存

查询时使用二分法，足够满足你的速度要求

24 楼 gqf2008 2007-11-26  

3000个10000长度的数组就可以了

23 楼 Eastsun 2007-11-25  

唔,那怎么用一个10000长度的数组保存3000万个信息呢?
蛮神奇的.

22 楼 gqf2008 2007-11-25  

不用,主要是通过数组下标来定位,关键的问题是要把数组长度尽量缩小

21 楼 Eastsun 2007-11-23  

还是要进行二次检索,三次检索?

20 楼 Eastsun 2007-11-23  

抛出异常的爱 写道

13是表示手机
下几位是表示运营公司
再下几位是表示发行区域
最后几位才是人
所以只有最后几位是有必要放进数组中的
其它的可以压缩。。。。到4位以内

4位,也就是少于10^4 =10000= 1万个手机号码.

gqf2008 写道

给你1G内存，如何从3000万个手机号码中检索出你要的号码，要求每秒检索>1000次

大家来探讨，发表您的意见！

3000万 = 3*10^7

难道说这3000万手机号码里面有重复的?

19 楼 gqf2008 2007-11-23  

=================结贴=================

18 楼 gqf2008 2007-11-23  

抛出异常的爱 写道

13是表示手机
下几位是表示运营公司
再下几位是表示发行区域
最后几位才是人
所以只有最后几位是有必要放进数组中的
其它的可以压缩。。。。到4位以内

正解，怎么解决我想大家都明白了

17 楼 抛出异常的爱 2007-11-23  

13是表示手机
下几位是表示运营公司
再下几位是表示发行区域
最后几位才是人
所以只有最后几位是有必要放进数组中的
其它的可以压缩。。。。到4位以内

16 楼 gqf2008 2007-11-23  

抛出异常的爱 写道

gqf2008 写道

抛出异常的爱 写道

试试这个：
static long a = new long[20000000000]

插入： a[tel]=1;
删除： a[tel]=0;
查寻： if(a[tel]==0){return 不存在}
改：  查寻+删除+插入

每个手机号放入对应的位置

用数组下标作为手机号码想法不错，不过你的实现会把内存撑爆，不信你试试看！提示：手机号码是11位的，将来可能12位

10的11次方。。。。。。13XXXXX的13可以去掉了。

呵呵 15号段早就出来了，以后可能还有好多号段出来，不过你的想法已经离成功不远了，我想应该可以把号码按号段分开来实现比较合理，例如可以把前面7位和后面4为分开出来，这样应该就可以实现了

15 楼 抛出异常的爱 2007-11-23  

gqf2008 写道

抛出异常的爱 写道

试试这个：
static long a = new long[20000000000]

插入： a[tel]=1;
删除： a[tel]=0;
查寻： if(a[tel]==0){return 不存在}
改：  查寻+删除+插入

每个手机号放入对应的位置

用数组下标作为手机号码想法不错，不过你的实现会把内存撑爆，不信你试试看！提示：手机号码是11位的，将来可能12位

10的11次方。。。。。。13XXXXX的13可以去掉了。

14 楼 gqf2008 2007-11-22  

ddandyy 写道

不说了  删除

做人要厚道

13 楼 ddandyy 2007-11-22  

不说了  删除

12 楼 gqf2008 2007-11-22  

ddandyy 写道

不知道LZ在想的是什么

不过肯定没有你想的那么复杂

要求每秒1000次?  那肯定是并发了.....

既然是并发  那么单次的时间有多少又有什么关系呢  肯定会在1秒以内出来

过滤手机号码是一个很正常的事情，每秒1000次是最底要求，如果你知道了这个算法就不复杂了，可惜你我就是不知道，所以让大伙出出方案撒！

11 楼 gqf2008 2007-11-22  

抛出异常的爱 写道

试试这个：
static long a = new long[20000000000]

插入： a[tel]=1;
删除： a[tel]=0;
查寻： if(a[tel]==0){return 不存在}
改：  查寻+删除+插入

每个手机号放入对应的位置

用数组下标作为手机号码想法不错，不过你的实现会把内存撑爆，不信你试试看！提示：手机号码是11位的，将来可能12位

10 楼 Eastsun 2007-11-22  

二分法,时间复杂度 log N

9 楼 liangguanhui 2007-11-22  

是否可以做缓存？然后排序查找

8 楼 抛出异常的爱 2007-11-22  

ddandyy 写道

........
应该是手机号绑定其他的信息吧......

如果光是手机号 也不用检索什么的了......

我只是从需求的角度说的。。。。其它的不理
（要求的是速度，那只能这么作了）

多的信息，只能用分冶法了。

7 楼 ddandyy 2007-11-22  

........
应该是手机号绑定其他的信息吧......

如果光是手机号 也不用检索什么的了......

6 楼 抛出异常的爱 2007-11-22  

试试这个：
static long a = new long[20000000000]

插入： a[tel]=1;
删除： a[tel]=0;
查寻： if(a[tel]==0){return 不存在}
改：  查寻+删除+插入

每个手机号放入对应的位置