1

大家好，我正在解决编码竞赛中的一个问题，我必须提供非常大的输入。

如问题所述 - 输入文件大小可能达到近 8MB，因此请确保您使用的是快速 I/O 方法。

输入将作为测试用例的数量给出。然后是方阵的维数 n。然后整个矩阵为

2

3

2 6 4

4 8 9

7 9 4

2

8 4

15 4

我从网上某个地方得到了一个代码，但我认为它没有任何帮助，因为我也收到了超过时间限制的消息。请告诉以下代码是否会进行快速输入

#define BUF 406 // block size on my disk is 4KBs
char ibuf[BUF];
int ipt = BUF;
int read_uint() {
while (ipt < BUF && ibuf[ipt] < '0') ipt++;
if (ipt == BUF) 
{
    fread(ibuf, 1, BUF, stdin);
    ipt = 0;
    while (ipt < BUF && ibuf[ipt] < '0') ipt++;
}
int n = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
if (ipt == BUF) 
{
    fread(ibuf, 1, BUF, stdin);
    ipt = 0;
    while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
}
return n;
}

请告诉在这种情况下读取 int 输入的最快方法

非常感谢你提前

4

2 回答 2

2

您是否只是为了读取输入而获得 TLE？通过提交仅读取数据的代码来确定数据读取操作需要多少时间。以下gets基本代码大约需要0.50 秒来读取大约10MB的数据文件，而scanf版本大约需要1 秒

使用gets方法读取输入：

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

int matrix[100][100];

int main () {
    char arr[1200], *p;
    int n, j;
    clock_t tStart = clock();
    gets(arr);
    n = atoi(arr);
    for (; n--;) {        
        gets(arr);
        int siz = atoi(arr);
        for (int i=0; i<siz; i++) {
            gets(arr);
            p = strtok(arr, " ");
            j=0;
            while(p != NULL) {
                matrix[i][j++] = atoi(p);
                p = strtok(NULL, " ");
            }
        }
    }

    printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    return 0;
}

扫描版：

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

int matrix[100][100];

int main () {
    int n, j;
    clock_t tStart = clock();
    scanf("%d", &n);
    for (; n--;) { 
        int siz;
        scanf("%d", &siz);
        for (int i=0; i<siz; i++) {
            j=0;
            while(j<siz) {
                scanf("%d", &matrix[i][j++]);
            }
        }
    }

    printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    return 0;
}
于 2013-01-08T06:42:47.247 回答
2

getchar unlocked 在在线评委（如 SPOJ 或 Codechef 等）上输入问题时也非常快。这是从控制台读取整数的函数

#define gc getchar_unlocked

void scan_integer( int &x )
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for( ; ((c<48 || c>57) && c != '-'); c = gc() );
    if( c=='-' ) {
        neg=1;
        c=gc();
    }
    for( ;c>47 && c<58; c = gc() ) {
        x = (x << 1) + (x << 3) + c - 48;
    }
    if( neg )
        x=-x;
}

另一种非常快速的方法是使用缓冲区并在字符缓冲区中读取输入。解释如下

#define MAXIMUM_BUFFER_CAPACITY 15000000
char buffer_to[MAXIMUM_BUFFER_CAPACITY];
char *buffer_ptr = buffer_to;

int scan_integer()
{
    int k = 0;
    while( *buffer_ptr < 33 )
        buffer_ptr++;
    do {
        k = k*10 + *buffer_ptr++ - '0';
    } while(*buffer_ptr > 32);
    return k;
}

int main()
{
    fread(buffer_to, 1, MAXIMUM_BUFFER_CAPACITY, stdin);
    int n;
    n = scan_integer();
    /* Use n */
}
于 2014-08-19T16:10:14.003 回答