C中更快IO的其他选择是什么?

我实现了合并排序,并将其用作此codechef问题的解决方案。 这是提交的内容 。 代码放在下面。

我认为导致执行缓慢的问题是我的IO在main函数中很慢。 我知道输入的元素数量,因此必须有一些更快的方式来读取输入而不是我正在做的方式。

是否有更快的IO方法而不是我在main函数中使用的方法? 我听说过使用buffer, fgetssscanf但我不知道它们是否更快。

任何代码示例都会有所帮助。

 #include #include void merge_parts(int arr[], int length) { int *ans; int i, j, k; int temp = length/2; ans = malloc(sizeof(int) * length); //This while and next if-else puts the merged array into temporary array ans for (j = temp, i = k = 0; (i < temp && j < length); k++){ ans[k] = (arr[i] = temp){ while(j < length){ ans[k++] = arr[j++]; } } else{ while(i < temp){ ans[k++] = arr[i++]; } } //This while loops puts array ans into original array arr for(i = 0; i  1) { merge_sort(&arr[0], (length/2)); merge_sort(&arr[length/2], (length - length/2)); merge_parts(arr, length); } } int main() { int length; int *arr; scanf("%d", &length); arr = malloc(sizeof(int) * length); for(int i = 0; i < length; i++) scanf("%d", &arr[i]); merge_sort(arr, length); for(int i = 0; i < length; i++) printf("%d ", arr[i]); free(arr); return 0; } 

EDIT3:

[我删除了编辑和编辑2,因为它们不再相关]

我正在使用的merge_sort算法

 void merge_parts(int arr[], int length) { int ans[length]; int i, j, k; int temp = length/2; //This while and next if-else puts the merged array into temporary array ans for (j = temp, i = k = 0; (i < temp && j < length); k++){ ans[k] = (arr[i] = temp){ while(j < length){ ans[k++] = arr[j++]; } } else{ while(i < temp){ ans[k++] = arr[i++]; } } //This while loops puts array ans into original array arr for(i = 0; i  1) { merge_sort(&arr[0], (length/2)); merge_sort(&arr[length/2], (length - length/2)); merge_parts(arr, length); } } 

merge1.c

 #include #include #include #include #define SORTING_ALGO_CALL merge_sort char buffer[4096]; int bufcount; int bufpos; int get_next_char() { if (!bufcount) { bufcount = fread(buffer, 1, 4096, stdin); bufpos = 0; if (!bufcount){ return EOF; } } bufcount--; return buffer[bufpos++]; } int readnum() { int res = 0; char ch; do { ch = get_next_char(); } while (!isdigit(ch) && ch != EOF); if (ch == EOF){ return 0xbaadbeef; // Don't expect this to happen. } do { res = (res * 10) + ch - '0'; ch = get_next_char(); } while(isdigit(ch)); return res; } int main() { clock_t time1, time2; double time_taken; //FIRST READ time1 = clock(); int length = readnum(); while (length < 1) { printf("\nYou entered length = %d\n", length); printf("\nEnter a positive length: "); length = readnum(); } //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nReading length = %f\n", time_taken); time1 = clock(); int *arr; if ((arr = malloc(sizeof(int) * length)) == NULL) { perror("The following error occurred"); exit(-1); } //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nAllocating array = %f\n", time_taken); time1 = clock(); for (int i = 0; i < length; i++){ arr[i] = readnum(); } //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nReading array = %f\n", time_taken); time1 = clock(); SORTING_ALGO_CALL(arr, length); //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nSorting array = %f\n", time_taken); time1 = clock(); /* for (int i = 0; i < length; i++){ printf("%d ", arr[i]); } */ //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nPrinting Sorted array = %f\n", time_taken); time1 = clock(); free(arr); //SECOND READ, PRINT time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nFreeing array = %f\n", time_taken); return 0; } 

merge2.c

 #include #include #include #define SORTING_ALGO_CALL merge_sort int main() { clock_t time1, time2; double time_taken; //FIRST READ time1 = clock(); int length; scanf("%d", &length); while (length < 1) { printf("\nYou entered length = %d\n", length); printf("\nEnter a positive length: "); scanf("%d", &length); } //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nReading length = %f\n", time_taken); time1 = clock(); int *arr; if ((arr = malloc(sizeof(int) * length)) == NULL) { perror("The following error occurred"); exit(-1); } //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nAllocating array = %f\n", time_taken); time1 = clock(); for (int i = 0; i < length; i++){ scanf("%d", &arr[i]); } //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nReading array = %f\n", time_taken); time1 = clock(); SORTING_ALGO_CALL(arr, length); //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nSorting array = %f\n", time_taken); time1 = clock(); /* for (int i = 0; i < length; i++){ printf("%d ", arr[i]); } */ //SECOND READ, PRINT AND NEXT FIRST READ time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nPrinting Sorted array = %f\n", time_taken); time1 = clock(); free(arr); //SECOND READ, PRINT time2 = clock(); time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC; printf("\nFreeing array = %f\n", time_taken); return 0; } 

merge1.c和merge2.c都包含merge-sort的2个函数。

我用于生成 2个文件的最坏情况(递减顺序)输入的文件。

 #include int main() { int j = 100000; printf("%d\n", j); for(int i = j; i > 0; i--) printf("%d\n", i); return 0; } 

merge1.c的计时结果

 Reading length = 23.055000 Allocating array = 0.000000 Reading array = 0.010000 Sorting array = 0.020000 Printing Sorted array = 0.000000 Freeing array = 0.000000 

merge2.c的计时结果

 Reading length = 22.763000 Allocating array = 0.000000 Reading array = 0.020000 Sorting array = 0.020000 Printing Sorted array = 0.000000 Freeing array = 0.000000 

通过编写自己的小函数来读取数字,几乎可以肯定地击败scanf

如果所有数字都是decimal并且由不是数字的东西分隔,那么这将起作用:

  char buffer[4096]; int bufcount; int bufpos; int get_next_char() { if (!bufcount) { bufcount = fread(buffer, 1, 4096, stdin); bufpos = 0; if (!bufcount){ return EOF; } } bufcount--; return buffer[bufpos++]; } int is_digit(int ch) { if (ch >= '0' && ch <= '9') return 1; return 0; } int readnum() { int res = 0; int ch; do { ch = get_next_char(); } while(!is_digit(ch) && ch != EOF); if (ch == EOF) { return 0xbaadbeef; // Don't expect this to happen. } do { res = (res * 10) + (ch - '0'); ch = get_next_char(); } while(is_digit(ch)); return res; } 

scanf中的代码比这复杂得多,并且极有可能调用getcfgetc ,这比上面的代码效率低一点。 但是,值得准确测量您花时间的位置。 打印每个function的时间作为输出的一部分。

我会补充Mats的答案,而不是使用stdin ,将文件名作为输入。 然后打开文件(如果在Windows上,则采用二进制格式)。 获取文件长度, malloc足够大的缓冲区,将整个文件读入其中,然后关闭文件。 然后我会使用字符指针解析到缓冲区。 这样,获取下一个字符不需要函数调用。 这很难超越速度。

解析整数的代码是:

 num = 0; while(isdigit(*pc)){ num = num*10 + (*pc++ - '0'); } 
  • 在优化问题中,经验法则是最好的。 尝试获取数值在每个步骤中花费的时间的价值。 加载 – 排序 – 等…您可以使用分析器(如gprof )。

  • 要加快IO速度,您应该考虑减少对scanf的调用。 由于你有scanf的数量要求,你可以为这个特定的部分设计一个更好的算法。

  • Scanf做了很多事情,解析了第一个arg,然后读取字节并将其转换为格式。 如果我们想要更快,我们将使用“数据问题”跳过一些步骤。 首先,我们知道我们只是在N(数学)上使用数字定义。 其次,我们知道每个字节都是数字或分隔符。 我们可以用这个。

所以我们使用read()系统调用,它可以从文件描述符中读取一些字节。 标准输入的文件描述符在操作系统之间变化,但通常为0。

宏算法可以是:

 index = 0 buffer = new array[10000]; numberOfByteRead = 1 while there is byte that have been read at last call of read. numberOfByteRead = read said 10000 byte to buffer; parse the buffer ;; parse(buffer,numberOfByteRead) for all true byte in buffer : switch (buffer[0]) case '0': { the mathematical operation on arr[index] that fit for '0'; break; } case '1': { ... break;} case ' ': {index++; break;} ;; 

代码并不是一个非常有趣的部分,但比scanf更快。 较大的值为10000,会减少IO时间,但会增加内存。 你必须平衡。

 static char buff[8*1000000]; int i, length, blen; int *ap, *p; int n = 0; char ch, *cp = buff; scanf("%d%*c", &length); p = ap = malloc(sizeof(*ap) * length); blen = fread(buff, 1, 8*1000000, stdin); while(blen--){ if(isdigit(ch=*cp++)){ n = n * 10 + ch - '0'; } else { *p++ = n; n = 0; } }