В конкурсе кодирования, указанном в эта ссылка, есть задача, в которой вам нужно прочитать много данных на 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
При внедрении моего собственного форматирования и синтаксического анализа строк inline мне удалось сократить время до 1/3 времени при использовании printf и scanf.
Однако, когда я загрузил свое решение на веб-страницу конкурсов, мое решение заняло 1,88 секунды (я думаю, что это общее время более чем 22 наборов данных). Когда я смотрю в высоком баллате, есть несколько реализаций (в С++), которые закончились за 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;
}
