问个算法问题

低调的MJ · 发表于 2009-9-21 01:10

假设A文件有100万条记录，B文件也有100万条记录，有什么算法可以快速地找出两文件中共有的记录？

自由自在 · 发表于 2009-9-21 14:46

我的笨方法:把 A文件的 key与行号加载进内存, 并按key 排好序. 然后顺序读取B文件的 key , 查找得相同记录的行号对应关系.

2002070344 · 发表于 2009-9-21 15:37

unoin all比left join快
用union all后
select a.a1 from ab group by a1 having count(*)>1

2002070344 · 发表于 2009-9-21 15:48

不好意思，看成数据库了

低调的MJ · 发表于 2009-9-21 17:31

4# 2002070344
其实数据库就是用B树来解决的，这也是一个思路

低调的MJ · 发表于 2009-9-21 17:33

2# 自由自在
效率很低……

皇家救星 · 发表于 2009-9-23 22:55

共有的定义是什么样　行号和内容一样？

如果只是内容一样可以排序(n*logn)

不过数据才100w　直接用map把一个文件放到内存，再读另一个在map中查找内存一般也吃得消的

adisonlee · 发表于 2009-10-7 03:01

关键是事先有没有建立索引~~索引是快速检索的关键。

低调的MJ · 发表于 2009-10-7 23:06

8# adisonlee
无……乱序，只是普通的文本文件

adisonlee · 发表于 2009-10-8 02:01

9# 低调的MJ

无序不能做到优化，需要用内存空间换取时间。这是基本原则。

没有办法只好续条读取检索。或者换个快点的硬盘吧，没有什么好的办法。

kids · 发表于 2009-10-16 22:46

看你的数据特征

		自动登录	找回密码
密码			加入后院