找到比较两个巨大但已排序文件的行的有效方法
Efficient way to find to compare lines of two huge but sorted files
我实际上被困在某事上，需要一些帮助..
我有两个巨大的 txt 文件 （制表符分隔符），格式如下：
文件 1 :
1 robert youh xpla@ioaio.fr
2 patrick yuad qqqq@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
文件 2 :
1 baby france paris
2 father usa detroit
3 mother uk london
4 baby italy milan
两个文件都已排序，但 File1 比 File2 大。我需要从 File1 中找到未出现在 File2 中的行（根据第一列，因此仅第一列用于比较）。
我尝试了很多方法：
- awk：没有找到一种方法来做到这一点（因为长度不同）
- python（with for which line statement and fileinput.input ...），我的脚本花了大约 5 分钟来执行 0.3% 行。
结果：我能够使用 python 检索正确的结果（对小文件进行了测试），但我无法处理非常大的文件。
有什么帮助吗？
我的文件每个大约有 200 万行。
假设 - 如您所述 - 文件已排序（我没有测试它，但它应该有效）
FILE1_POS = 0
FILE2_POS = 1
MAX_POS = 2
missing = []
get_rec_no = lambda l, f=FILE1_POS: int(l.split(None, MAX_POS)[f])
with open('File1') as source, open('File2') as trgt:
trgt = iter(trgt)
for line in source:
src_rec_no = get_rec_no(line)
try:
trgt_rec_no = get_rec_no(trgt.next(), FILE2_POS)
while trgt_rec_no < src_rec_no:
missing.append(src_rec_no)
trgt_rec_no = get_rec_no(trgt.next(), FILE2_POS)
except StopIteration:
break
for line in source:
missing.append(get_rec_no(line))
编辑：
我按你的要求改的
如果您因为性能问题而遇到问题，您可能需要考虑使用 Hadoop/MapReduce 之类的方法将文件拆分为多个较小的文件，然后您可以 运行 每个子进程在不同的处理器上实现加速。
作为一个简单的例子，将文件一分为二，您可以有一个子文件，其中包含 [A-M]、[M-Z] 之间的所有键。这样，如果您知道一个文件的密钥，您就知道要搜索哪个子文件来寻找可能的匹配项。理论上，如果将文件一分为二，搜索时间就会减半（但是，不能完全减半，因为会涉及开销）。
基本上，编程将涉及编写 mapper.py 和 reducer.py。如果您不熟悉 Hadoop/MapReduce，有很多关于在 Python 中设置 MapReduce 作业的好教程，但我建议的是名为 "Intro to Hadoop and MapReduce" 的 Udacity 课程，它解决了一些问题使用 Python 和 MapReduce 的类似问题。
此外，您可能需要考虑编辑标签以包含 Hadoop MapReduce，在这种情况下，您可以获得一些有关编写 mapper.py 和 reducer.py 的更具体的帮助。
在 bash 试试这个：
join -v 1 -j 1 file1.txt file2.txt
结果是：
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
参数如下：
-j 1 是要加入的字段，即第一个字段
-v 1 表示抑制第一个文件中的行
文件长度不同这一事实并不排除 awk 解决方案。接受你的两个输入：
[ damien $] cat file1
cat: file1: No such file or directory
[ damien $] cat file1.txt
1 robert youh xpla@ioaio.fr
2 patrick yuad qqqq@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
[ damien $] cat file2.txt
1 baby france paris
2 father usa detroit
3 mother uk london
4 baby italy milan
[ damien $]
考虑以下脚本：
[ damien $] cat n_join.awk
#!/usr/bin/gawk -f
NR==FNR{
# file2[]=[=11=];
file2[]=1;
}
NR!=FNR{
if(!( in file2)){
# print current record if not in file2
print ;
}else{
# if from file1 has been found.
# if it's really unique in file1, it
# can be deleted from file2. Otherwise
# comment this line:
delete file2[];
}
}
[ damien $]
给出输出：
[ damien $] chmod +x n_join.awk
[ damien $] ./n_join.awk file2.txt file1.txt
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
[ damien $]
注意必须先传入file2.txt。我不知道这是否适用于 200 万行长的文件，但很想知道您是否有时间尝试一下。 :)
如果你能让文件可用（不太可能），我会自己试试...:D
编辑：我知道你已经接受了你的回答并且可能已经开始了你的生活，但是，我想补充一些额外的信息。
如果我创建两个您指定类型的大文件：file1.bit.txt 包含 500 万条记录：
[ damien $] seq 1 1 5000000 > file1.big.txt
[ damien $] sed -i 's|$| bob fsgfq ddd@ioaio.fr|' file1.big.txt
[ damien $] head file1.big.txt
1 bob fsgfq ddd@ioaio.fr
2 bob fsgfq ddd@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
4 bob fsgfq ddd@ioaio.fr
5 bob fsgfq ddd@ioaio.fr
6 bob fsgfq ddd@ioaio.fr
7 bob fsgfq ddd@ioaio.fr
8 bob fsgfq ddd@ioaio.fr
9 bob fsgfq ddd@ioaio.fr
10 bob fsgfq ddd@ioaio.fr
[ damien $] tail file1.big.txt
4999991 bob fsgfq ddd@ioaio.fr
4999992 bob fsgfq ddd@ioaio.fr
4999993 bob fsgfq ddd@ioaio.fr
4999994 bob fsgfq ddd@ioaio.fr
4999995 bob fsgfq ddd@ioaio.fr
4999996 bob fsgfq ddd@ioaio.fr
4999997 bob fsgfq ddd@ioaio.fr
4999998 bob fsgfq ddd@ioaio.fr
4999999 bob fsgfq ddd@ioaio.fr
5000000 bob fsgfq ddd@ioaio.fr
[ damien $]
[ damien $]
[ damien $]
[ damien $]
和
[ damien $]
[ damien $] seq 2 2 5000000 > file2.big.txt
[ damien $] sed -i 's|$| baby france paris|' file2.big.txt
[ damien $] head file2.big.txt
2 baby france paris
4 baby france paris
6 baby france paris
8 baby france paris
10 baby france paris
12 baby france paris
14 baby france paris
16 baby france paris
18 baby france paris
20 baby france paris
[ damien $] tail file2.big.txt
4999982 baby france paris
4999984 baby france paris
4999986 baby france paris
4999988 baby france paris
4999990 baby france paris
4999992 baby france paris
4999994 baby france paris
4999996 baby france paris
4999998 baby france paris
5000000 baby france paris
[ damien $]
只有偶数键。 运行 我的脚本给出：
[ damien $]
[ damien $] time ./n_join.awk file2.big.txt file1.big.txt > output.big
real 0m4.154s
user 0m3.893s
sys 0m0.207s
[ damien $]
[ damien $] head output.big
1 bob fsgfq ddd@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
5 bob fsgfq ddd@ioaio.fr
7 bob fsgfq ddd@ioaio.fr
9 bob fsgfq ddd@ioaio.fr
11 bob fsgfq ddd@ioaio.fr
13 bob fsgfq ddd@ioaio.fr
15 bob fsgfq ddd@ioaio.fr
17 bob fsgfq ddd@ioaio.fr
19 bob fsgfq ddd@ioaio.fr
[ damien $] tail output.big
4999981 bob fsgfq ddd@ioaio.fr
4999983 bob fsgfq ddd@ioaio.fr
4999985 bob fsgfq ddd@ioaio.fr
4999987 bob fsgfq ddd@ioaio.fr
4999989 bob fsgfq ddd@ioaio.fr
4999991 bob fsgfq ddd@ioaio.fr
4999993 bob fsgfq ddd@ioaio.fr
4999995 bob fsgfq ddd@ioaio.fr
4999997 bob fsgfq ddd@ioaio.fr
4999999 bob fsgfq ddd@ioaio.fr
[ damien $] wc -l output.big
2500000 output.big
[ damien $]
整个过程在大约 4 秒内完成，这似乎一点也不令人望而却步。要么数据集有很大差异，要么你的脚本运行方式与我的有很大不同。也许这对某人有用。 :/
Ps。根据 /proc/cpuinfo
，我有一个 i7-3770 CPU @ 3.40GHz
我实际上被困在某事上，需要一些帮助..
我有两个巨大的 txt 文件 （制表符分隔符），格式如下：
文件 1 :
1 robert youh xpla@ioaio.fr
2 patrick yuad qqqq@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
文件 2 :
1 baby france paris
2 father usa detroit
3 mother uk london
4 baby italy milan
两个文件都已排序，但 File1 比 File2 大。我需要从 File1 中找到未出现在 File2 中的行（根据第一列，因此仅第一列用于比较）。
我尝试了很多方法： - awk：没有找到一种方法来做到这一点（因为长度不同） - python（with for which line statement and fileinput.input ...），我的脚本花了大约 5 分钟来执行 0.3% 行。
结果：我能够使用 python 检索正确的结果（对小文件进行了测试），但我无法处理非常大的文件。
有什么帮助吗？
我的文件每个大约有 200 万行。
假设 - 如您所述 - 文件已排序（我没有测试它，但它应该有效）
FILE1_POS = 0
FILE2_POS = 1
MAX_POS = 2
missing = []
get_rec_no = lambda l, f=FILE1_POS: int(l.split(None, MAX_POS)[f])
with open('File1') as source, open('File2') as trgt:
trgt = iter(trgt)
for line in source:
src_rec_no = get_rec_no(line)
try:
trgt_rec_no = get_rec_no(trgt.next(), FILE2_POS)
while trgt_rec_no < src_rec_no:
missing.append(src_rec_no)
trgt_rec_no = get_rec_no(trgt.next(), FILE2_POS)
except StopIteration:
break
for line in source:
missing.append(get_rec_no(line))
编辑：
我按你的要求改的
如果您因为性能问题而遇到问题，您可能需要考虑使用 Hadoop/MapReduce 之类的方法将文件拆分为多个较小的文件，然后您可以 运行 每个子进程在不同的处理器上实现加速。
作为一个简单的例子，将文件一分为二，您可以有一个子文件，其中包含 [A-M]、[M-Z] 之间的所有键。这样，如果您知道一个文件的密钥，您就知道要搜索哪个子文件来寻找可能的匹配项。理论上，如果将文件一分为二，搜索时间就会减半（但是，不能完全减半，因为会涉及开销）。
基本上，编程将涉及编写 mapper.py 和 reducer.py。如果您不熟悉 Hadoop/MapReduce，有很多关于在 Python 中设置 MapReduce 作业的好教程，但我建议的是名为 "Intro to Hadoop and MapReduce" 的 Udacity 课程，它解决了一些问题使用 Python 和 MapReduce 的类似问题。
此外，您可能需要考虑编辑标签以包含 Hadoop MapReduce，在这种情况下，您可以获得一些有关编写 mapper.py 和 reducer.py 的更具体的帮助。
在 bash 试试这个：
join -v 1 -j 1 file1.txt file2.txt
结果是：
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
参数如下：
-j 1 是要加入的字段，即第一个字段
-v 1 表示抑制第一个文件中的行
文件长度不同这一事实并不排除 awk 解决方案。接受你的两个输入：
[ damien $] cat file1
cat: file1: No such file or directory
[ damien $] cat file1.txt
1 robert youh xpla@ioaio.fr
2 patrick yuad qqqq@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
[ damien $] cat file2.txt
1 baby france paris
2 father usa detroit
3 mother uk london
4 baby italy milan
[ damien $]
考虑以下脚本：
[ damien $] cat n_join.awk
#!/usr/bin/gawk -f
NR==FNR{
# file2[]=[=11=];
file2[]=1;
}
NR!=FNR{
if(!( in file2)){
# print current record if not in file2
print ;
}else{
# if from file1 has been found.
# if it's really unique in file1, it
# can be deleted from file2. Otherwise
# comment this line:
delete file2[];
}
}
[ damien $]
给出输出：
[ damien $] chmod +x n_join.awk
[ damien $] ./n_join.awk file2.txt file1.txt
8 tim qqjh hjahj@uayua.com
9 john ajkajk rtaeraer@auiaui.com
[ damien $]
注意必须先传入file2.txt。我不知道这是否适用于 200 万行长的文件，但很想知道您是否有时间尝试一下。 :)
如果你能让文件可用（不太可能），我会自己试试...:D
编辑：我知道你已经接受了你的回答并且可能已经开始了你的生活，但是，我想补充一些额外的信息。
如果我创建两个您指定类型的大文件：file1.bit.txt 包含 500 万条记录：
[ damien $] seq 1 1 5000000 > file1.big.txt
[ damien $] sed -i 's|$| bob fsgfq ddd@ioaio.fr|' file1.big.txt
[ damien $] head file1.big.txt
1 bob fsgfq ddd@ioaio.fr
2 bob fsgfq ddd@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
4 bob fsgfq ddd@ioaio.fr
5 bob fsgfq ddd@ioaio.fr
6 bob fsgfq ddd@ioaio.fr
7 bob fsgfq ddd@ioaio.fr
8 bob fsgfq ddd@ioaio.fr
9 bob fsgfq ddd@ioaio.fr
10 bob fsgfq ddd@ioaio.fr
[ damien $] tail file1.big.txt
4999991 bob fsgfq ddd@ioaio.fr
4999992 bob fsgfq ddd@ioaio.fr
4999993 bob fsgfq ddd@ioaio.fr
4999994 bob fsgfq ddd@ioaio.fr
4999995 bob fsgfq ddd@ioaio.fr
4999996 bob fsgfq ddd@ioaio.fr
4999997 bob fsgfq ddd@ioaio.fr
4999998 bob fsgfq ddd@ioaio.fr
4999999 bob fsgfq ddd@ioaio.fr
5000000 bob fsgfq ddd@ioaio.fr
[ damien $]
[ damien $]
[ damien $]
[ damien $]
和
[ damien $]
[ damien $] seq 2 2 5000000 > file2.big.txt
[ damien $] sed -i 's|$| baby france paris|' file2.big.txt
[ damien $] head file2.big.txt
2 baby france paris
4 baby france paris
6 baby france paris
8 baby france paris
10 baby france paris
12 baby france paris
14 baby france paris
16 baby france paris
18 baby france paris
20 baby france paris
[ damien $] tail file2.big.txt
4999982 baby france paris
4999984 baby france paris
4999986 baby france paris
4999988 baby france paris
4999990 baby france paris
4999992 baby france paris
4999994 baby france paris
4999996 baby france paris
4999998 baby france paris
5000000 baby france paris
[ damien $]
只有偶数键。 运行 我的脚本给出：
[ damien $]
[ damien $] time ./n_join.awk file2.big.txt file1.big.txt > output.big
real 0m4.154s
user 0m3.893s
sys 0m0.207s
[ damien $]
[ damien $] head output.big
1 bob fsgfq ddd@ioaio.fr
3 bob fsgfq ddd@ioaio.fr
5 bob fsgfq ddd@ioaio.fr
7 bob fsgfq ddd@ioaio.fr
9 bob fsgfq ddd@ioaio.fr
11 bob fsgfq ddd@ioaio.fr
13 bob fsgfq ddd@ioaio.fr
15 bob fsgfq ddd@ioaio.fr
17 bob fsgfq ddd@ioaio.fr
19 bob fsgfq ddd@ioaio.fr
[ damien $] tail output.big
4999981 bob fsgfq ddd@ioaio.fr
4999983 bob fsgfq ddd@ioaio.fr
4999985 bob fsgfq ddd@ioaio.fr
4999987 bob fsgfq ddd@ioaio.fr
4999989 bob fsgfq ddd@ioaio.fr
4999991 bob fsgfq ddd@ioaio.fr
4999993 bob fsgfq ddd@ioaio.fr
4999995 bob fsgfq ddd@ioaio.fr
4999997 bob fsgfq ddd@ioaio.fr
4999999 bob fsgfq ddd@ioaio.fr
[ damien $] wc -l output.big
2500000 output.big
[ damien $]
整个过程在大约 4 秒内完成，这似乎一点也不令人望而却步。要么数据集有很大差异，要么你的脚本运行方式与我的有很大不同。也许这对某人有用。 :/
Ps。根据 /proc/cpuinfo
，我有一个 i7-3770 CPU @ 3.40GHz