如何快速(以C为单位)读取和解析带有数字的文本文件？

Question

最后一次更新:我的同学用来fread()将整个文件的大约三分之一读成一个字符串,这可以避免内存不足.然后处理此字符串,将此字符串分隔到您的数据结构中.请注意,您需要关心一个问题:在此字符串的末尾,这些最后几个字符可能不能包含一个整数.考虑一种检测这种情况的方法,这样您就可以将这些字符与下一个字符串的前几个字符连接起来.每个数字对应于数据结构中的不同变量.您的数据结构应该非常简单,因为每次将数据插入到一个数据结构中时,它都非常慢.大部分时间花在将数据插入数据结构中.因此,处理这些数据的最快方法是:使用fread()将此文件读入字符串,将此字符串分隔为不同的一维数组.例如(只是一个例子,不是来自我的项目),我有一个文本文件,如:

72     24      20
22     14      30
23     35      40
42     29      50
19     22      60
18     64      70
 .
 .
 .

每行是一个人的信息.第一栏是指人的年龄,第二栏是他的存款,第二栏是他妻子的年龄.然后我们用fread()这个文本文件读成字符串,然后我用stroke()它来分隔它(你可以用更快的方式将它分开).不要使用数据结构来存储分离的数据!我的意思是,不要这样做:

struct person
{
    int age;
    int deposit;
    int wife_age;
};
struct person *my_data_store;
my_data_store=malloc(sizeof(struct person)*length_of_this_array);
//then insert separated data into my_data_store

不要使用数据结构来存储数据!存储数据的最快方法是这样的:

int *age;
int *deposit;
int *wife_age;

age=(int*)malloc(sizeof(int)*age_array_length);
deposit=(int*)malloc(sizeof(int)*deposit_array_length);
wife_age=(int*)malloc(sizeof(int)*wife_array_length);
// the value of age_array_length,deposit_array_length and wife_array_length will be known by using `wc -l`.You can use wc -l to get the value in your C program
// then you can insert separated data into these arrays when you use `stroke()` to separate them.

第二次更新:最好的方法是使用freed()将文件的一部分读入字符串,然后将这些字符串分成您的数据结构.顺便说一句,不要使用任何可以将字符串格式化为整数的标准库函数,那就慢,比如fscanf() or atoi(),我们应该编写自己的函数将字符串转换为n整数.不仅如此,我们还应该设计一个更简单的数据结构来存储这些数据.顺便说一下,我的同学可以在7秒内读取这个1.7G文件.有一种方法可以做到这一点.这种方式比使用多线程要好得多.我没有看到他的代码,在看到他的代码后,我会第三次更新,告诉你怎么可以这样做.这将是我们课程结束后两个月.

更新:我使用多线程来解决这个问题!! 有用!注意:不要使用clock()来计算使用多线程的时间,这就是我认为执行时间增加的原因.

我要澄清的一件事是,在不将值存储到我的结构中的情况下读取文件的时间大约是20秒.将值存储到我的结构中的时间大约是60秒."读取文件的时间"的定义包括读取整个文件并将值存储到我的结构中的时间.读取文件的时间=扫描文件+将值存储到我的结构中.因此,有一些存储价值更快的建议吗？(顺便说一下,我无法控制inout文件,它是由我们的教授生成的.我正在尝试使用多线程来解决这个问题,如果它有效,我会告诉你结果.)

我有一个文件,它的大小是1.7G.看起来像:

1   1427826
1   1427827
1   1750238
1   2
2   3
2   4
3   5
3   6
10  7
11  794106
.
.

和儿子.它在文件中有大约一千万行.现在我需要读取此文件并在15秒内将这些数字存储在我的数据结构中.我试图用来freed()读取整个文件然后strtok()用来分隔每个数字,但它仍然需要80秒.如果我使用fscanf(),它会更慢.我该如何加快速度？也许我们不能少于15秒.但80秒阅读它太长了.如何尽可能快地阅读？

这是我阅读代码的一部分:

int Read_File(FILE *fd,int round)
{
clock_t start_read = clock();


int first,second;
first=0;
second=0;


fseek(fd,0,SEEK_END);
long int fileSize=ftell(fd);
fseek(fd,0,SEEK_SET);
char * buffer=(char *)malloc(sizeof(char)*fileSize);
char *string_first;
long int newFileSize=fread(buffer,1,fileSize,fd);
char *string_second;
     while(string_first!=NULL)

    {
        first=atoi(string_first);

        string_second=strtok(NULL," \t\n");

        second=atoi(string_second);

        string_first=strtok(NULL," \t\n");

        max_num= first > max_num ? first : max_num ;
        max_num= second > max_num ? second : max_num ;
        root_level=first/NUM_OF_EACH_LEVEL;

        leaf_addr=first%NUM_OF_EACH_LEVEL;

        if(root_addr[root_level][leaf_addr].node_value!=first)
        {
            root_addr[root_level][leaf_addr].node_value=first;
            root_addr[root_level][leaf_addr].head=(Neighbor *)malloc(sizeof(Neighbor));
            root_addr[root_level][leaf_addr].tail=(Neighbor *)malloc(sizeof(Neighbor));

            root_addr[root_level][leaf_addr].g_credit[0]=1;

            root_addr[root_level][leaf_addr].head->neighbor_value=second;

           root_addr[root_level][leaf_addr].head->next=NULL;
            root_addr[root_level][leaf_addr].tail=root_addr[root_level][leaf_addr].head;
            root_addr[root_level][leaf_addr].degree=1;
        }
        else
        {
            //insert its new neighbor
            Neighbor *newNeighbor;
            newNeighbor=(Neighbor*)malloc(sizeof(Neighbor));

            newNeighbor->neighbor_value=second;

            root_addr[root_level][leaf_addr].tail->next=newNeighbor;
            root_addr[root_level][leaf_addr].tail=newNeighbor;

            root_addr[root_level][leaf_addr].degree++;
        }
        root_level=second/NUM_OF_EACH_LEVEL;

        leaf_addr=second%NUM_OF_EACH_LEVEL;
        if(root_addr[root_level][leaf_addr].node_value!=second)
        {
            root_addr[root_level][leaf_addr].node_value=second;
            root_addr[root_level][leaf_addr].head=(Neighbor *)malloc(sizeof(Neighbor));
            root_addr[root_level][leaf_addr].tail=(Neighbor *)malloc(sizeof(Neighbor));

            root_addr[root_level][leaf_addr].head->neighbor_value=first;

            root_addr[root_level][leaf_addr].head->next=NULL;
            root_addr[root_level][leaf_addr].tail=root_addr[root_level][leaf_addr].head;

            root_addr[root_level][leaf_addr].degree=1;

            root_addr[root_level][leaf_addr].g_credit[0]=1;
        }
        else
        {
            //insert its new neighbor
            Neighbor *newNeighbor;
            newNeighbor=(Neighbor*)malloc(sizeof(Neighbor));

            newNeighbor->neighbor_value=first;

            root_addr[root_level][leaf_addr].tail->next=newNeighbor;
            root_addr[root_level][leaf_addr].tail=newNeighbor;

            root_addr[root_level][leaf_addr].degree++;
        }
    }

Answer 1

一些建议:

a)考虑将文件转换(或预处理)为二进制格式; 旨在最小化文件大小,并大幅降低解析成本.我不知道您的值的范围,但各种技术(例如,使用一位来判断数字是小还是大,并将数字存储为7位整数或31位整数)可以将文件减半IO(并且从磁盘读取文件的速度加倍)并将解析成本降低到几乎为零.注意:为了获得最大效果,您首先要修改创建文件的软件.

b)在解析之前将整个文件读入内存是一个错误.它使所需的RAM量增加了一倍(以及分配/释放的成本),并且CPU缓存存在缺点.而是读取少量文件(例如16 KiB)并处理它,然后读取下一个片段并处理它,依此类推; 这样你就可以不断重复使用相同的小缓冲存储器.

c)对文件IO使用并行性.在处理上一段文件时(通过使用2个线程或使用异步IO),读取文件的下一部分应该不难.

d)为"邻居"结构预先分配内存,并malloc()从循环中删除大部分/全部调用.最好的情况是使用静态分配的数组作为池 - 例如Neighbor myPool[MAX_NEIGHBORS];,malloc()可以替换为&myPool[nextEntry++];.这减少/消除了开销,malloc()同时还改善了数据本身的缓存局部性.

e)使用并行性来存储值.例如,您可以有多个线程,其中第一个线程处理所有情况root_level % NUM_THREADS == 0,第二个线程处理所有情况root_level % NUM_THREADS == 1,等等.

有了以上所有(假设是现代的4核CPU),我认为你可以将总时间(用于读取和存储)缩短到不到15秒.

Answer 2

我的建议是形成一个处理管道并对其进行处理.读取文件是一个I/O绑定任务,解析它是CPU绑定的.它们可以同时并行完成.