快速读取文件

Question

我有一个包含 2 个图和以下格式的顶点数的 txt 文件：

6
0 1 0 1 0 0
1 0 1 0 0 1
0 1 0 1 0 0
1 0 1 0 1 0
0 0 0 1 0 1
0 1 0 0 1 0
0 1 0 0 1 0
1 0 1 0 0 0
0 1 0 1 0 1
0 0 1 0 1 0
1 0 0 1 0 1
0 0 1 0 1 0

矩阵表示顶点邻接。如果两个顶点相邻，则它们对的值为 1。虽然这些图在视觉上没有分开，但第二张图是在第一张图的第 6 行之后开始的。每个图都可以有很多顶点，例如 5000 个，并且它们的大小相同（图）。我编写了一个算法来检查这两个图是否同构，我注意到读取这些图需要 8 秒，而实际算法需要 2.5 秒（对于 5000 个顶点）。由于我的目标是优化我的程序的整体速度，我想知道我是否可以改进（在速度方面）我当前从文件读取的代码：

FILE* file = fopen ("input.txt", "r");
fscanf (file, "%d", &i);
int n = i;
while (!feof (file))
{  
    fscanf (file, "%d", &i); 
    if (j < (n*n)) {  // first graph
        if (i==1) {
            adj_1[j/n][v_rank_1[j/n]] = j - (j/n)*n; // add the vertice to the adjacents of the current vertice
            v_rank_1[j/n] += 1;
        }
    }
    else if (j>=(n*n)) {   // second graph
        if (i==1) {
            adj_2[(j-(n*n))/n][v_rank_2[(j-(n*n))/n]] = (j-(n*n)) - ((j-(n*n))/n)*n; // add the vertice to the adjacents of the current vertice
            v_rank_2[(j-(n*n))/n] += 1;
        }
    }
    j++;
}
fclose (file);

adj_*table保存了一个顶点的相邻顶点的索引

v_rank_*table保存了一个顶点相邻的顶点数

重要的是我从图中获取了这个信息，而且只获取了这个信息。

Answer 1

您可以通过减少访问文件系统的频率来加快速度。您一次从文件中读取一个整数，因此每次通过循环访问该文件。

相反，尝试一次读取整个文件或文件的一大块。（这称为块读取）。您可以将其缓冲到数组中。在你的循环中，从内存缓冲区而不是文件中读取。如果您没有读入整个文件，请根据需要在循环内刷新您的内存缓冲区。

Answer 2

使用fgets()一次将一行读入行缓冲区。将行缓冲区解析为整数值。

此函数减少了您从文件中读取的次数，因为在幕后，fgets() 从文件中读取大量数据并且一次 returns 一行。它仅在其内部缓冲区中没有更多行时才尝试读取另一个块。

Answer 3

第一个优化是一次读取内存中的整个文件。在循环中访问内存将比调用 fread 更快。

第二个优化是做更少的算术运算，即使这意味着更多的代码。

第三个优化是将文件中的数据视为字符以避免整数转换。

结果可能是：

// bulk read file into memory
fseek(file, 0, SEEK_END);
long fsize = ftell(file);
fseek(file, 0, SEEK_SET);
char *memFile = malloc(fsize + 1);
if (memFile == NULL) return; // not enough memory !! Handle it as you wish
fscanf(file, "%d", &n);
fread(memFile, fsize, 1, file);
fclose(file);
memfile[fsize] = 0;

// more code but less arythmetic operations
int lig, col;
char *mem = memFile, c;
for (int lig = 0; lig < n; lig++) { // first graph
    for (int col = 0; col < n; col++) {
        for (;;)
        {
            c = *mem;
            if (c == 0) break;
            mem++;
            if (c == '1') {
                adj_1[lig][v_rank_1[lig]++] = col; // add the vertice to the adjacents of the current vertice
                k++; // ??
                break;
            }
            if (c == '0') break;
        }

    }
}
for (int lig = 0; lig < n; lig++) { // second graph
    for (int col = 0; col < n; col++) {
            c = *mem;
            if (c == 0) break;
            mem++;
            if (c == '1') {
                adj_2[(lig][v_rank_2[lig]++] = col; // add the vertice to the adjacents of the current vertice
                l++;  // ??
                break;
            }
            if (c == '0') break;
        }
    }
}
free(memFile);

备注：你没有提到变量k和l。

快速读取文件

Read from file fast

c

graph

input

text-files