c,stdin/out中的快速I/O.

Question

在此链接指定的编码竞赛中,您需要读取大量数据stdin,进行一些计算并提供大量数据stdout.

在我的基准测试中,尽管我尽可能地尝试优化它,但几乎只有I/O才需要时间.

你输入的是一个字符串(1 <= len <= 100'000)和q行的一对int,其中q也是1 <= q <= 100'000.

我在100倍大的数据集(len = 10M,q = 10M)上对我的代码进行基准测试,这就是结果:

 Activity            time      accumulated

 Read text:          0.004     0.004
 Read numbers:       0.146     0.150
 Parse numbers:      0.200     0.350
 Calc answers:       0.001     0.351
 Format output:      0.037     0.388
 Print output:       0.143     0.531

通过实现我自己的格式化和数字解析内联我设法将时间缩短到使用printf和时间的1/3 scanf.

然而,当我将我的解决方案上传到比赛网页时,我的解决方案需要1.88秒(我认为这是超过22个数据集的总时间).当我看到高分时,有几个实现(在c ++中)在0.05秒内完成,比我快了近40倍!怎么可能？

我想我可以通过使用2个线程来加速它,然后我可以开始计算并写入stdout,同时仍然从stdin读取.然而,这将减少min(0.150, 0.143)我的大型数据集的理论上最佳情况的时间.我仍然没有接近高分...

在下图中,您可以看到消耗时间的统计信息.

该程序由网站编译,具有以下选项:

gcc -g -O2 -std=gnu99 -static my_file.c -lm

和定时这样:

time ./a.out < sample.in > sample.out

我的代码看起来像这样:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN (100000 + 1)
#define ROW_LEN (6 + 1)
#define DOUBLE_ROW_LEN (2*ROW_LEN)

int main(int argc, char *argv[])
{
    int ret = 1;

    // Set custom buffers for stdin and out
    char stdout_buf[16384];
    setvbuf(stdout, stdout_buf, _IOFBF, 16384);
    char stdin_buf[16384];
    setvbuf(stdin, stdin_buf, _IOFBF, 16384);

    // Read stdin to buffer
    char *buf = malloc(MAX_LEN);
    if (!buf) {
        printf("Failed to allocate buffer");
        return 1;
    }
    if (!fgets(buf, MAX_LEN, stdin))
        goto EXIT_A;

    // Get the num tests
    int m ;
    scanf("%d\n", &m);

    char *num_buf = malloc(DOUBLE_ROW_LEN);
    if (!num_buf) {
        printf("Failed to allocate num_buffer");
        goto EXIT_A;
    }

    int *nn;
    int *start = calloc(m, sizeof(int));
    int *stop = calloc(m, sizeof(int));
    int *staptr = start; 
    int *stpptr = stop;
    char *cptr;
    for(int i=0; i<m; i++) {
        fgets(num_buf, DOUBLE_ROW_LEN, stdin);
        nn = staptr++;
        cptr = num_buf-1;
        while(*(++cptr) > '\n') {
            if (*cptr == ' ')
                nn = stpptr++;
            else
                *nn = *nn*10 + *cptr-'0';
        }
    }


    // Count for each test
    char *buf_end = strchr(buf, '\0');
    int len, shift;
    char outbuf[ROW_LEN];
    char *ptr_l, *ptr_r, *out;
    for(int i=0; i<m; i++) {
        ptr_l = buf + start[i];
        ptr_r = buf + stop[i];
        while(ptr_r < buf_end && *ptr_l == *ptr_r) {
            ++ptr_l;
            ++ptr_r;
        }

        // Print length of same sequence
        shift = len = (int)(ptr_l - (buf + start[i]));
        out = outbuf;
        do {
            out++;
            shift /= 10;
        } while (shift);
        *out = '\0';
        do {
            *(--out) = "0123456789"[len%10];
            len /= 10;
        } while(len);
        puts(outbuf);
    }



    ret = 0;

    free(start);
    free(stop);
EXIT_A:
    free(buf);
    return ret;
}

Answer 1

您应该连续分配所有缓冲区。分配一个缓冲区，该缓冲区的大小是所有缓冲区（num_buff、start、stop）的大小，然后按大小将点重新排列到相应的偏移量。这可以减少缓存未命中\页面错误。

由于读取和写入操作似乎消耗大量时间，因此您应该考虑添加线程。一个线程应该处理 I\O，另一个线程应该处理计算。（值得检查另一个打印线程是否也可以加快速度）。确保执行此操作时不使用任何锁。