2 jason   bourne Jason___Bourne 于 2015.07.25 21:05 提问

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

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

67个回答

sun_xiaofan
sun_xiaofan   2015.08.18 20:01

这个问题不在于算法,主要是数据的存储方式,你一个文件存放1亿个QQ号码,这个文件就得超过几G大小,如果你内存够大,全读到内存中虽然也可以,但一般来说不能这样,因为你读文件的复杂度已经是O(n)的量级了。
因为你为了查找一个qq号,就得读取几个G数据到内存,这个开销就太大了,所以这个问题不是算法问题,是数据在磁盘中的结构应如何存储。
一般来说,像数据库这种有自建索引的,比较好弄,但如果你想自建维护磁盘存储结构,就很复杂了,这里说一种简单易懂的。
直接利用磁盘目录做简易索引,由于磁盘本身是有B树索引的,所以管理效率也不低。例如,将QQ号码的前六位作为索引,所有前六位相同的QQ号,都处理存放到一个文件中。然后文件名就以该六位qq号命名。所有文件全放到一个文件夹下可能较难管理,那么可以利用这种思路,上一级目录就用前5位QQ做索引,依次管理,最后整个目录就是一个10叉树。
以前效率不高的原因就是因为读取全部文件太费时间,你将文件打散后存放,读取文件时就很快了,查找的范围也很小了。
整体复杂度 = 几次文件寻找时的随机磁盘寻址+1M左右磁盘读取,接下来直接线性查找都很快。
其实我们发现,这个数量级的查找,复杂度已经不是在内存上了,而是要避免大量从磁盘上的数据读取。数据库做这个事情一般比用文件快,原因是,第一数据库有缓存,之前查过的集合会缓存一段时间,其次,磁盘上有原生的索引结构,比咱们自己用文件树模拟来的高效。

hadues
hadues   2015.07.25 23:58

一个含有1亿个QQ号码的文件,面对这种大数据处理,还要满足最快查找到QQ的需求,如果是我,我会先从这几方面考虑。

一、硬件配置

二、编程语言

三、算法

四、查前判断

五、存储区域

-------------------------------且听我慢慢道来---------------------------

一、硬件配置——命令行下运行的最快的计算机

                 想快点查找,兵器必须要好,那么就得做到以下几点:

                                     1. 操作系统

                                            放弃图形用户界面用命令行界面的操作系统,不解释。如果Windows和Linux之间,貌似只得选Linux了。

                                     2. 采用世界上最快的计算机

                                            国产的天河二号超级计算机,Cray超级计算机,、量子计算机,生物计算机,哪个最快就用哪个吧。

                                     3.世界上最快的计算机构成的服务器集群来最优共同合作处理。

二、编程语言——尽量接近底层的编程语言

                 高级语言貌似总是没有低级语言的处理速度快,因此应该尽量使用接近底层的编程语言。

三、算法——操作系统分页原理+时间复杂度最低的算法

                题目中只求查询速度快即可,那么意思是不是只要时间复杂度低点,多牺牲点空间似乎也无所谓。

                                    始终觉得操作系统的分页查询原理很不错,在此基础上再使用一种时间复杂度最低的算法,那么速度应该会提高不少。

四、查前判断

                  1.查询前先判断QQ位数

                                        查询之前,先判断QQ位数,可缩小一部分分页查询范围。

                                2.逐位位数分页判断

                    从最高位开始判断每一位都进行判断,该位属于从哪一页,哪个表。

五、存储区域——构造高速缓冲区

                尽量存储到一个存取速度比较快的数据结构内,并放到存取速度最快的存储区内,位数判断后将满足的页加载到内存。

异想天开班门弄斧胡言乱语一番,梦中不知所云。

caozhy
caozhy   Ds   Rxr 2015.07.25 22:23

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

caozhy
caozhy 回复qq_33951019: 构造的复杂度是O(n),但是查找的效率是O(Log(n))
11 个月之前 回复
qq_33951019
qq_33951019 构建字典树的复杂度依然是O(n)。。
11 个月之前 回复
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:23

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

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叉树很不错 可以考虑

zuishikonghuan
zuishikonghuan   2015.07.26 08:19

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

qq_27220973
qq_27220973   2015.07.26 12:29

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

共67条数据 1 3 4 ... 尾页
Csdn user default icon
上传中...
上传图片
插入图片