桶排序/计数大文件的排序
桶排序/计数大文件的排序
提问于 2022-03-31 19:59:46
我有一个非常大的文件，我想以粗略的方式对(10 S TB)进行排序。基本上，我散列了这个文件中的一个字段，取该散列的最后4位数，并将其作为一列附加。这给了我一个与每一行相关联的4位base16数字，这意味着每一行都可以放进65536个桶中的一个。然后，我想在65536个文件之间分发这个文件，每个文件代表一个桶。
我认为GNU排序不够聪明，无法加速这个操作--我不能指定只有65536个可能的密钥，所以我的假设是它会像其他任何排序操作一样接近这个值。
我目前的策略是打开65536个文件句柄并逐行遍历文件，将每一行写入相应的文件。这打破了单个用户的上限，我知道这是可以修改的，但我不确定这是否是一个好策略。以前有人做过这样的事吗？
现在，我有一个python脚本，如下所示：
bucketfilemap = { ... } # 65536 open files
s = time.time()
with open(infile, 'rb') as inf:
for line in inf:
tokens = line.split(delim)
bucketkey = tokens[keyloc]
bucketfilemap[bucketkey].write(line)
e = time.time()
print("time total:", (e - s))在我对较小文件的测试中，它比我想的要慢，尽管它确实与文件的大小成线性关系，这正是我想要的。
回答 1
Stack Overflow用户
发布于 2022-04-01 00:36:56
我设计了一个C程序来代替python脚本。做了一个奇怪的发现，但最终它要快得多。
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <fcntl.h>
#define N 65536
#define N2 4
// custom hex to integer
int hextoint(char* str) {
int t = 0;
for (int i = 0; i < N2; i++) {
char c = str[i];
if (c < 58) {
t |= ((int)(c-48))<<(i<<2); // each hex digits represents 4 bits, 16=2**4
} else {
t |= ((int)(c-87))<<(i<<2);
}
}
return t;
}
int bucketsort(char* infilename, char** outfilenames) {
FILE* buckets[N];
FILE* infile;
char lbuf[512];
int hashidx;
int cp;
int len;
for (int i = 0; i < N; i++) {
buckets[i] = fopen(outfilenames[i], "wb");
}
infile = fopen(infilename, "rb");
int j = 0;
while (1) {
cp = fgets(lbuf, sizeof(lbuf), infile);
if (cp == NULL) {
break;
}
len = strlen(lbuf);
hashidx = hextoint(lbuf); // file should be formatted such that the hex key always comes at the beginning of the line
fwrite(lbuf, 1, len, buckets[hashidx]);
j++;
}
for (int i = 0; i < N; i++) {
int r = fclose(buckets[i]);
}
return 0;
}
void main(int argc, char** argv) {
char* outfilesfilename = argv[2];
char* infilename = argv[1];
FILE* outfilefd = fopen(outfilesfilename, "r");
char lbuf[512];
char** outfilenames = malloc(sizeof(char*)*N);
for (int i = 0; i < N; i++) {
outfilenames[i] = malloc(sizeof(char)*256);
}
int i = 0;
while (fgets(lbuf, sizeof(lbuf), outfilefd)) {
int len = strlen(lbuf);
memcpy(outfilenames[i], lbuf, len-1);
i++;
}
bucketsort(infilename, outfilenames);
}我所做的奇怪发现是，fclose在C中可能非常慢，而且速度似乎取决于打开的文件描述符的数量。打开文件是快速的，给它们写也是快速的。但是，当我打开65536个文件时，执行65536 fcloses需要30-50秒.当我将N改为256 ( N2改为2)时，仅需十分之一秒。
640MB file
N = 256
1.970000 seconds elapsed on write
0.110000 seconds elapsed on close
N = 65536
4.550000 seconds elapsed on write
36.869999 seconds elapsed on close不管我是写500 30还是640 30，关闭文件总是需要30-50秒，而python ~0.24秒才能写出500 30到65536 30的文件。这仍然是更好的，因为它似乎是一种固定的成本，而不是按照文件的大小进行调整。例如，使用500 For文件：
500KB file
0.440000 seconds elapsed on write
45.889999 seconds elapsed on close页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71698563
复制相关文章
相似问题
腾讯云开发者
