C чтение большого файла в char * массив слишком медленно

Question

Я бы хотел прочитать большой файл, в то время как первый символ строки не является "". Но код, который я написал, очень медленный. Как я могу ускорить процедуру? Есть ли лучшее решение вместо getline?

void readString(const char *fn) 
{ 
    FILE *fp; 
    char *vString; 
    struct stat fdstat; 
    int stat_res; 

    stat_res = stat(fn, &fdstat); 
    fp = fopen(fn, "r+b"); 

    if (fp && !stat_res) 
    { 
     vString = (char *)calloc(fdstat.st_size + 1, sizeof(char)); 

     int dataEnd = 1; 
     size_t len = 0; 
     int emptyLine = 1; 
     char **linePtr = malloc(sizeof(char*)); 
     *linePtr = NULL; 

     while(dataEnd) 
     { 
     // Check every line 
     getline(linePtr, &len, fp); 

     // When data ends, the line begins with space (" ") 
     if(*linePtr[0] == 0x20) 
      emptyLine = 0;   

     // If line begins with space, stop writing 
     if(emptyLine) 
      strcat(vString, *linePtr); 
     else 
      dataEnd = 0; 
     } 

     strcat(vString, "\0"); 
     free(linePtr); 
     linePtr = NULL; 
    } 
} 

int main(int argc, char **argv){ 
    readString(argv[1]); 
    return EXIT_SUCCESS; 
} 

Answer 1

Как я могу ускорить процедуру?

Самый подозрительный аспект вашей программы - это strcat(). При каждом вызове ему нужно отсканировать всю строку назначения с начала, чтобы найти место для добавления исходной строки. В результате, если строки вашего файла имеют длину, ограниченную константой (даже большой), то производительность вашего подхода масштабируется с квадратом длины файла.

Анализ асимптотической сложности не обязательно отражает всю историю. Часть ввода-вывода вашего кода масштабируется линейно с длиной файла, а поскольку I/O намного дороже, чем манипуляция с памятью в памяти, это будет доминировать над вашей производительностью для файлов с небольшим количеством файлов. Если вы находитесь в этом режиме, вы, вероятно, не будете делать намного лучше, чем вы уже делаете. В этом случае, однако, вы могли бы еще сделать немного лучше, читая весь файл сразу через fread(), а затем сканировать его с истекшим данных через strstr():

size_t nread = fread(vString, 1, fdstat.st_size, fp); 

// Handle nread != fdstat.st_size ... 

// terminate the buffer as a string 
vString[nread] = '\0'; 

// truncate the string after the end-of-data: 
char *eod = strstr(vString, "\n "); 
if (eod) { 
    // terminator found - truncate the string after the newline 
    eod[1] = '\0'; 
} // else no terminator found 

Это масштабируется линейно, поэтому он обращается ваша проблема асимптотической сложности тоже, но если интересующие данные часто будут намного короче, чем файл, тогда это оставит вас в тех случаях, когда вы делаете намного более дорогостоящие операции ввода-вывода, чем вам нужно. В этом случае одним из вариантов было бы читать куски, как предположил @laissez_faire. Другим было бы настроить ваш оригинальный алгоритм для отслеживания конца vString, чтобы использовать strcpy() вместо strcat(), чтобы добавить каждую новую строку. Ключевая часть этой версии будет выглядеть примерно так:

char *linePtr = NULL; 
size_t nread = 0; 
size_t len = 0; 

*vString = '\0'; // In case the first line is end-of-data 
for (char *end = vString; ; end += nread) { 
    // Check every line 
    nread = getline(&linePtr, &len, fp); 

    if (nread < 0) { 
     // handle eof or error ... 
    } 

    // When data ends, the line begins with space (" ") 
    if (*linePtr == ' ') { 
     break; 
    } 
    strcpy(end, *linePtr); 
} 

free(linePtr); 

Кроме того, обратите внимание, что

• вам не нужно изначально нулевой заполнения памяти, выделенной для *vString, так как вы просто переписывая эти нули с данными реального интереса (а затем игнорируя остальную часть буфера).

• Вы не должны указывать возвращаемое значение malloc() -семейных функций, включая calloc().

Answer 2

Вы пробовали читать файл, используя Fread и прочитать большую порцию данных на каждом этапе, а затем анализировать данные после прочтения? Что-то вроде:

#include <stdio.h> 
#include <string.h> 
#include <sys/types.h> 
#include <sys/stat.h> 
#include <unistd.h> 
#include <stdlib.h> 

char *readString(const char *fn) 
{ 
    FILE *fp; 
    char *vString; 
    struct stat fdstat; 
    int stat_res; 

    stat_res = stat(fn, &fdstat); 
    fp = fopen(fn, "r+b"); 

    if (fp && !stat_res) { 
    vString = (char *) calloc(fdstat.st_size + 1, sizeof(char)); 

    int newline = 1; 
    int index = 0; 
    while (index < fdstat.st_size) { 
     int len = 
     fdstat.st_size - index > 
     4096 ? 4096 : fdstat.st_size - index; 
     char *buffer = (char *) malloc(len); 
     int read_len = fread(buffer, 1, len, fp); 
     int i; 
     if (newline) { 
     if (read_len > 0 && buffer[0] == ' ') { 
      return vString; 
     } 
     newline = 0; 
     } 
     for (i = 0; i < read_len; ++i) { 
     if (buffer[i] == '\n') { 
      if (i + 1 < read_len && buffer[i + 1] == ' ') { 
      memcpy(vString + index, buffer, i + 1); 
      return vString; 
      } 
      newline = 1; 
     } 
     } 
     memcpy(vString + index, buffer, read_len); 
     index += read_len; 
    } 
    } 
    return vString; 
} 

int main(int argc, char **argv) 
{ 
    char *str = readString(argv[1]); 
    printf("%s", str); 
    free(str); 
    return EXIT_SUCCESS; 
}