我正在尝试用 C 语言实现字典,发现/usr/share/dict/words
这是一个非常适合测试的文件。无论出于何种原因,我想将单词文件复制到我的工作目录中,但令我惊讶的是,程序读取文件的速度明显较慢。什么可以解释这种行为?这两个文件是相同的。
如果我不得不猜测,可能是/usr/share/dict/words
因为它是经常使用的文件而已经缓冲在内存中?
#define _GNU_SOURCE
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#define GET_TIME(now) \
do { \
struct timeval t; \
gettimeofday(&t, NULL); \
now = t.tv_sec + t.tv_usec / 1000000.0; \
} while (0)
#define REPORT(msg, time) \
do { \
printf("%-10s- %f\n", msg, time); \
} while (0)
#define SHOW_INVALID 0
struct dict {
int n;
char *data[110000];
};
int valid_word(char *input)
{
for (int i = 0; input[i]; i++) {
if (!islower(input[i]) && !(input[i] == '\n')) {
return 0;
}
}
return 1;
}
struct dict *get_dict(char *file)
{
struct dict *dict = calloc(1, sizeof(struct dict));
FILE *fp = fopen(file, "r");
char input[128];
while (fgets(input, 128, fp)) {
if (valid_word(input)) {
dict->data[dict->n++] = strdup(input);
} else {
#if SHOW_INVALID == 1
printf("Skipping invalid word %s", input);
#endif
}
}
fclose(fp);
return dict;
}
void destroy_dict(struct dict *dict)
{
for (int i = 0; i < dict->n; i++) {
free(dict->data[i]);
}
free(dict);
}
int search(struct dict *dict, int l, int r, char *word)
{
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (!strcmp(dict->data[mid], word)) return mid;
if (strcmp(dict->data[mid], word) > 0) return search(dict, l, mid - 1, word);
return search(dict, mid + 1, r, word);
}
int match(struct dict *dict, char *word)
{
return search(dict, 0, dict->n - 1, word);
}
void test(struct dict *dict, char *file)
{
FILE *fp = fopen(file, "r");
char input[128];
while (fgets(input, 128, fp)) {
if (valid_word(input)) {
assert(match(dict, input) != -1);
} else {
assert(match(dict, input) == -1);
}
}
fclose(fp);
}
int main(void)
{
double init, start, end;
GET_TIME(init);
GET_TIME(start);
struct dict *dict = get_dict("words");
GET_TIME(end);
REPORT("setup", end - start);
GET_TIME(start);
test(dict, "words");
GET_TIME(end);
REPORT("words", end - start);
GET_TIME(start);
test(dict, "words_random");
GET_TIME(end);
REPORT("randwords", end - start);
GET_TIME(start);
destroy_dict(dict);
GET_TIME(end);
REPORT("teardown", end - start);
puts("");
REPORT("total", end - init);
return 0;
}
答案1
正如 @Vilinkameni 指出的,如果正在访问的文件位于不同的物理设备或文件系统类型上,GNU/Linux 中的 I/O 性能可能会有所不同。
就我而言,WSL2 使用虚拟硬盘,但我的工作目录(WSL 的目标目录cd
)实际上位于我的C:/
驱动器上。因此,在访问/usr/share/dict/words
文件时,我仍保留在 WSL2 VHD 中,但如果我将文件复制到我的C:/
驱动器,这就是性能受到影响的地方,因为它必须读取另一个“文件系统”上的文件。
我通过将程序移动到/usr/share/dict/
并在那里创建文件的副本来测试这一点words
,现在性能是相同的。