在两个文本文件之间搜索数百万个字符串以查找完全匹配(allvsall)

Question

我有两个文本文件。两者都包含数亿行。第二个大约大四倍。

两个文本文件各有两列。第一个是ID(密钥)，第二个是必须在两个文件之间进行比较的Value字符串。

EDIT2:两个文件的Value中可能存在重复项。

两个文本文件的结构：

ID                      Value
B00CC0:2610:20880:13730 cd99AABABBABABABABABABABABA
B00CC0:2549:10230:33301 cd99BABABBABBBABBBBBBAAABBB
B00CC0:1272:8504:27179  cd99BBBBBBBBAAAAAAAAABBBBBB
B00CC0:1556:10628:35055 cd99AAAABBBBABABAAAAAAAAAAB
...                     ...

现在我想输出第二个文件中的每一行，其中包含第一个文件中出现的Value(完全匹配，而不是子字符串！)。

我在Python中尝试了一个简单的实现，只需将两个文件加载到数据帧中，然后执行过滤：

import sys
import modin.pandas as pd
import ray
ray.init()
# load 1st file
data_one = pd.read_csv(filename1, compression='gzip', header=0, sep='t', usecols=[1], names=['Value'])
data_one_list = data_tso['Value'].tolist()
# load 2nd file
data_two = pd.read_csv(filename2, compression='gzip', header=0, sep='t', usecols=[0,1], names=['ID','alue'])
# filter
data_two_filtered = data_two[data_two['Value'].isin(data_one_list)]

然而，只有当我对第一个文件进行子集设置时，这才有效，否则它太大，Python脚本就会崩溃(占用所有RAM)。而且它太慢了。我试图使用modin.pandas来加快整个过程，但并不能解决我的问题。

现在我有两个方向的问题：

第一个方向：

1. 你认为有可能开发出一种解决方案吗；体面的"；Python中的性能？或者你认为是否需要C/C++(提到C/C++，因为它们是我唯一掌握的至少足以解决这个问题的编译语言)

第二个方向：

1. 你认为我必须使用哈希表或trie等方法进行查找吗？或者你认为如果正确，测试的简单表查找就足够了吗
2. 如果你提出一个具体的方法，它会是什么(数据结构，方法)

编辑：

1. 我有一台256 GB RAM和64个线程的机器
2. 一个合适的速度是在大约1-2分钟内进行过滤

Answer 1

显然，有几种解决方案是可能的。由于您的计算机上有大量可用内存，因此可以逐行读取文件中的值列，并将每个值添加到一个集合中。

之后，逐行读取文件2，并检查每个值是否在集合中。如果是，则输出当前行缓冲区。

这样的C程序是用<100行代码，尤其是在使用现有集合实现的情况下。我选择了https://github.com/barrust/set因为它看起来不错并且易于集成，所以只需将set.c和set.h复制到您的项目中即可。为了进行快速测试，我创建了一个包含1亿行随机数据的文件，其结构与您的问题所示类似。

使用set_init_alt，您似乎已经可以为哈希表设置高容量了。

与gtime -f "CPU: %UstReal: %estRAM: %MKB" ./search file1.txt file2.txt我在8.6GBRAM下测量了大约45秒，用于在我的笔记本电脑上构建哈希，这似乎是一个不错的结果。

C程序

C程序假定第1列和第2列由空格分隔。如果要使用其他分离器，它很容易适应。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "set.h"
#define MAX_LINE_LENGTH 128
static char *get_value(char *buf);
static void error_exit(char *prefix, char *msg) {
fprintf(stderr, "%s: %sn", prefix, msg);
exit(-1);
}
static void build_set(char *fileName, SimpleSet *set) {
char buf[MAX_LINE_LENGTH];
FILE *fp;
if ((fp = fopen(fileName, "r")) == NULL) {
error_exit("failure opening file1", strerror(errno));
}
while (fgets(buf, sizeof(buf), fp) != NULL) {
char *value = get_value(buf);
set_add(set, value);
}
if (ferror(fp)) {
error_exit("error reading from file1", strerror(errno));
}
fclose(fp);
}
static void query_set(char *fileName, SimpleSet *set) {
char buf[MAX_LINE_LENGTH];
FILE *fp;
if ((fp = fopen(fileName, "r")) == NULL) {
error_exit("failure opening file2", strerror(errno));
}
while (fgets(buf, sizeof(buf), fp) != NULL) {
char *value = get_value(buf);
if (set_contains(set, value) == SET_TRUE) {
printf("%sn", buf);
}
}
if (ferror(fp)) {
error_exit("error reading from file2", strerror(errno));
}
fclose(fp);
}
static char *get_value(char *buf) {
char *ptr = buf;
while (*ptr && *ptr != ' ')
ptr++;
while (*ptr == ' ')
ptr++;
char *value = ptr;
while (*ptr && *ptr != 'n')
ptr++;
*ptr = '';
return value;
}
int main(int argc, char *argv[]) {
if (argc != 3) {
error_exit("usage", "search <file1> <file2>");
}
SimpleSet set;
set_init_alt(&set, 500000000, NULL);  /* use default hash */
build_set(argv[1], &set);
query_set(argv[2], &set);
//the cleanup takes some time, but since the program terminates anyway, not necessary
//set_destroy(&set);
return 0;
}

构建命令

gcc -Wall -Wextra main.c set.c -O3 -o search

最后一句话

这当然不是一个完美的、完全优化的版本，当然也可以开发出更先进的解决方案，但也许这是你自己实验的起点。