我有两个文本文件。两者都包含数亿行。第二个大约大四倍。
两个文本文件各有两列。第一个是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
来加快整个过程,但并不能解决我的问题。
现在我有两个方向的问题:
第一个方向:
- 你认为有可能开发出一种解决方案吗;体面的";Python中的性能?或者你认为是否需要C/C++(提到C/C++,因为它们是我唯一掌握的至少足以解决这个问题的编译语言)
第二个方向:
- 你认为我必须使用哈希表或trie等方法进行查找吗?或者你认为如果正确,测试的简单表查找就足够了吗
- 如果你提出一个具体的方法,它会是什么(数据结构,方法)
编辑:
- 我有一台256 GB RAM和64个线程的机器
- 一个合适的速度是在大约1-2分钟内进行过滤
显然,有几种解决方案是可能的。由于您的计算机上有大量可用内存,因此可以逐行读取文件中的值列,并将每个值添加到一个集合中。
之后,逐行读取文件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
最后一句话
这当然不是一个完美的、完全优化的版本,当然也可以开发出更先进的解决方案,但也许这是你自己实验的起点。