2 jason   bourne Jason___Bourne 于 2015.07.25 21:05 提问

给你一个含有1亿个QQ号码的文件,如何快速的查找某个QQ号码? 50C

如题,我要找一个效率比较高的方法,欢迎大家来讨论。如果答案是暴力扫最快的话,我自扇耳光三百下!

73个回答

caozhy
caozhy   Ds   Rxr 2015.07.25 22:23

最简单的办法就是字典树。查找效率为Log(N)

caozhy
caozhy 回复qq_33951019: 构造的复杂度是O(n),但是查找的效率是O(Log(n))
大约一年之前 回复
qq_33951019
qq_33951019 构建字典树的复杂度依然是O(n)。。
大约一年之前 回复
wingfiring
wingfiring   2015.08.18 18:45

问一下题主,你要查几次?如果是查一次的话,你可以开始表演自扇了。

u011767611
u011767611   2015.07.26 11:25

取决于你的数据类型:
要是qq号以整型的方式保存在数据库,那么完全可以通过数值查找;
如果是字符型,可以通过双重遍历:(算法用python实现为)

 index = 0
  7     current_src = []
  8 
  9     """itering the dst_qqs"""
 10     for dst_qq in dst_qqs:
 11         print 'match -->',dst_qq,'in ',index
 12         for src_qq in src_qqs:
 13             if src_qq[index]==dst_qq:
 14                 current_src.append(src_qq)
 15                 print 'match:',src_qq
 16             else:
 17                 print 'not match:',src_qq
 18 
 19             time.sleep(1)
 20         index += 1
 21         src_qqs = current_src

原理:先遍历目标qq号,每次获取一位,并且内部遍历目标qq源,进行比对每一组qq的对应位,符合添加到列表中;
此时,设1亿位qq号中,0~9对应每一位的概率相同,则选出1000万组qq号;
继续遍历:(设目标qq号为9位)则遍历外部遍历9次,内部遍历依次为:
10000万 (即1亿)
1000万
100万
10万
1万
1000
100
10
1
时间复杂度可以自行演算;

zuishikonghuan
zuishikonghuan   2015.07.26 08:19

使用比较底层的编程语言
多线程
算法,优化
有条件的话分布式计算

zuishikonghuan
zuishikonghuan   2015.07.26 08:23

如果平台支持,还可以用平台提供的的接口,比如在Windows系统,可以内存映射文件,当然最好能编写驱动程序,在驱动程序中直接控制磁盘设备,避免了在应用层调用API,中断进内核,系统服务例程,I/O管理,缓冲区复制,过滤设备等等的影响读取速度

qq_27220973
qq_27220973   2015.07.26 12:29

建议使用数据挖掘的思想做一下,对数据进行预处理,分块分片处理,感觉会解决数据大,内存不够的问题

gtitanlq
gtitanlq   2015.07.25 21:47

struct node{
int a;
int flag;
long pos;
struct node *next[10];
struct node *father;
};

一个字符一个字符读,每个字符一个节点,判断下该字符节点是否存在,不存在动态创建个,遇到空格前面那个字符对应的节点flag赋值1
ftell得到位置,复制到节点的pos中,然后不断读啊写啊
最后构成了一个好大的树
最后查的时候循环遍历下去就行了吧

yufuerhuigood
yufuerhuigood 回复xiao千歌: 都是学渣了,就不用瞧不起了
2 年多之前 回复
gtitanlq
gtitanlq 不鸟我,不用瞧不起我这样的学渣吧
2 年多之前 回复
tabe123
tabe123   Rxr 2015.07.25 22:12

10叉树很不错 可以考虑

u010298834
u010298834   2015.07.25 21:32

如果QQ号是按照一定顺序排列的话,折半查找应该是最快的。如果不是按顺序排列的话,我认为还是并行查找比较快,即从头和尾同时查找。

qq_28193117
qq_28193117   2015.07.28 11:01

如果是有序的,那么拆办查找就相当有效了,如果是无序的,那只能通过提取长度和排列的数字进行筛选了,想不出其他办法了。

共73条数据 1 3 4 ... 尾页
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!