Chinaunix

标题: 求解一道笔试算法题 [打印本页]

作者: thehig 时间: 2011-11-08 09:52
标题: 求解一道笔试算法题
500MHz cpu，1M内存的手机，实现对50万好友的模糊检索
有什么好的思路呢？

作者: x5miao 时间: 2011-11-08 11:36
1M内存？现在有这样的手机吗？

作者: MMMIX 时间: 2011-11-08 12:22

500MHz cpu，1M内存的手机，实现对50万好友的模糊检索
有什么好的思路呢？
thehig 发表于 2011-11-08 09:52

手机？50万好友？

作者: thehig 时间: 2011-11-08 14:33

题目是这样的写的。。。。
那抛开这些硬件条件，有什么比较好的方法或思路来解决这个问题？

作者: 鸡丝拌面 时间: 2011-11-08 16:38
典型的思路如同尿路的鼻屎题。

作者: l2y3n2 时间: 2011-11-08 16:54
模糊搜索的定义是啥？

作者: srdgame 时间: 2011-11-08 17:16
难道是为了强调内存很小，要尽量节约内存？

作者: btdm123 时间: 2011-11-08 17:50
hash

作者: goldenfort 时间: 2011-11-08 19:19
回复 1# thehig

这公司没钱，也干不出啥事情来，耍面试的了，连这都没看出来

作者: lhy0416 时间: 2011-11-08 19:57
回答：云计算。50万条都在云端，我在手机上发个指令就行了。

作者: lhy0416 时间: 2011-11-08 20:05
本帖最后由 lhy0416 于 2011-11-08 20:06 编辑

50万小于等于500K
500k条 1M内存一条2个字节，1M就满了……
2个字节一共16位，就算是二进制存储，也只能存2^16=64K条不同的信息……
这50万信息中平均8个人重名

作者: keytounix 时间: 2011-11-25 16:21
回复 1# thehig

50W好友

一个好友名字占用3个汉字，算2个char，对不？
电话号码占用11个char 考虑首位 1可以忽略对不？

那么一条号码需要 10+3*2=16个字符

50W条*16=50*16*10K
=8000K
=8M
显然不能一次占用了

现在我们想一个办法

第一次
我们分20次加载这些数据

然后利用hash()%20函数
对每次加载的数据进行处理

得到结果相同的

存放在同一个文件中

20次后

得到了0-19这20个文件

然后对搜索的关键词进行 hash()%20操作

得到的值假设为 9

最后到文件名称为 9的文件中进行搜索操作就可以了

每一次加载的文件大概为4KB左右

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)