11
this link에 지정된 코딩 경쟁에서 stdin에 많은 데이터를 읽고, 몇 가지 계산을 수행하고 stdout에 많은 데이터를 표시해야하는 작업이 있습니다.고속 입출력 (표준 입출력)
필자는 벤치마킹에서 최대한 많은 것을 최적화하려고했지만 거의 시간이 걸린다.
입력 내용은 문자열 (1 <= len <= 100'000)이고 q 쌍의 정수 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 및 scanf을 사용할 때 시간의 1/3까지 감소합니다.
그러나 내 솔루션을 경기 웹 페이지에 업로드 할 때 솔루션에 1.88 초가 걸렸습니다 (총 22 개 이상의 데이터 세트가 있다고 생각합니다). 높은 점수를 볼 때 0.05 초 만에 완성 된 몇 가지 구현 (C++)이 내 것보다 거의 40 배 빠릅니다! 어떻게 가능합니까?
2 스레드를 사용하여 속도를 높일 수 있다고 생각합니다. 그런 다음 stdout에서 계산하면서 stdout에 쓰기 시작할 수 있습니다. 그러나 큰 데이터 세트의 이론상 가장 좋은 경우에는 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) = ""[len%10];
len /= 10;
} while(len);
puts(outbuf);
}
ret = 0;
free(start);
free(stop);
EXIT_A:
free(buf);
return ret;
}
왜 개별 int에 대해 메모리를 할당하고 있습니까? 너 무슨 시스템있어? Linux에서 stdio는 Windows에서 iostream보다 빠르며 빠릅니다. Windows에서는 iostream이 stdio를 능가합니다. stdio는 iostream (AFAIK)에 대한 그러한 요구 사항이없는 동안 POSIX가 stdio가 호출에 대해 재귀 적 잠금을 사용하도록 요구하므로 IO 함수의 잠금 해제 된 변형 (puts 대신에 puts_unlocked 등)을 사용하여 다소 빨리 수행 할 수 있습니다. – PSkocik
루프를 통해 매번 출력을 수행하는 것처럼 보입니다. 속도를 위해 메모리를 교환하고 더 큰 버퍼를 할당 한 다음 전체 출력을 한꺼번에 인쇄한다면 어떨까요? 또는 실행 가능한 출력이 너무 많으면 버퍼링을 통해 출력을 실질적으로 통합 할 수 있습니다. 'puts'가 실제적으로 당신의 병목이라면 문제를 해결할 수 있습니다. 나는 당신이 그 시간에 도착하기 위해 어떻게 측정하고 있는지 확실하지 않습니다. 모든 작업이 "출력물 출력"측정에 포함되어 있습니까? –
사소한 :'cptr = num_buf-1;'은 정의되지 않은 행동이다. – chux