低调的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

看你的数据特征
页: [1]
查看完整版本: 问个算法问题