i***r
发帖数: 1035 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: iiiir (哎呀我最牛), 信区: Programming
标 题: 【包子求助】20M*20M的loop怎么搞？
发信站: BBS 未名空间站 (Fri Sep 14 14:51:39 2012, 美东)
我有2个文件A和B，各自约20 million lines
现在我要check的是，B的每一行中的第一个数字，是否落入A的某一行的第一第二数字
之间。
比较直观的是，我写2个loop
for i=1:length(A)
for k=1:length(B)
do what I want to check...
end
end
问题是20M*20M似乎太长，我的电脑化了2个小时，才算到i=600左右，也就是跑了600*
20M loops
请问大虾们，怎么整。我用的是matlab，C也可以用，python也可以考虑。。。
多谢了，解决问题的发包子 |
c*******h
发帖数: 1096 | 2 区间树，nlogn，CLRS的伪代码照抄
或者线段树，可以找A的所有行，但是文件A的数据不能变
【在 i***r 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: iiiir (哎呀我最牛), 信区: Programming
: 标 题: 【包子求助】20M*20M的loop怎么搞？
: 发信站: BBS 未名空间站 (Fri Sep 14 14:51:39 2012, 美东)
: 我有2个文件A和B，各自约20 million lines
: 现在我要check的是，B的每一行中的第一个数字，是否落入A的某一行的第一第二数字
: 之间。
: 比较直观的是，我写2个loop
: for i=1:length(A)
: for k=1:length(B)
|
d*****u
发帖数: 17243 | 3 简单说，先把A里的第一个数字排个序
如果用比较的方法，这个是nlogn
然后就只需要考虑比B里面小的数字，
对于B里每一个数字，查找这个区间是logn
如果B里有n个数，则是nlogn
同样，把A里的第二个数字做类似处理
然后找出比B里的大的
再跟前面的取交集
最后就是O(nlogn)
【在 i***r 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: iiiir (哎呀我最牛), 信区: Programming
: 标 题: 【包子求助】20M*20M的loop怎么搞？
: 发信站: BBS 未名空间站 (Fri Sep 14 14:51:39 2012, 美东)
: 我有2个文件A和B，各自约20 million lines
: 现在我要check的是，B的每一行中的第一个数字，是否落入A的某一行的第一第二数字
: 之间。
: 比较直观的是，我写2个loop
: for i=1:length(A)
: for k=1:length(B)
|
i***r
发帖数: 1035 | |
K****n
发帖数: 5970 | 5 取N次交集的复杂度是多少？
【在 d*****u 的大作中提到】
: 简单说，先把A里的第一个数字排个序
: 如果用比较的方法，这个是nlogn
: 然后就只需要考虑比B里面小的数字，
: 对于B里每一个数字，查找这个区间是logn
: 如果B里有n个数，则是nlogn
: 同样，把A里的第二个数字做类似处理
: 然后找出比B里的大的
: 再跟前面的取交集
: 最后就是O(nlogn)
|
