这是C++中最快的输入方法

Question

我正在编写奥林匹克运动会的各种节目,并试图提高时间效率.我正在寻找最快的输入方式,使用没有任何外部库的gcc编译器.

我之前使用过cin和cout,但发现scanf和printf要快得多.还有更快的方法吗？我不太关心空间复杂性,我宁愿选择更好的时间.

Answer 1

那些流总是慢于C-API函数是一个非常常见的误解,因为默认情况下,它们与C层同步.所以,是的,这是一个功能,而不是一个错误.

在不牺牲类型安全性(和可读性,取决于您的品味)的情况下,您可以通过使用以下方式获得流的性能:

std::ios_base::sync_with_stdio (false);

一个小指标:

#include <cstdio>
#include <iostream>

template <typename Test> 
void test (Test t)
{
    const clock_t begin = clock();
    t();
    const clock_t end = clock();
    std::cout << (end-begin)/double(CLOCKS_PER_SEC) << " sec\n";
}

void std_io() {
    std::string line;
    unsigned dependency_var = 0;

    while (!feof (stdin)) {
        int c;
        line.clear();
        while (EOF != (c = fgetc(stdin)) && c!='\n')
            line.push_back (c);
        dependency_var += line.size();
    }

    std::cout << dependency_var << '\n';
}

void synced() {
    std::ios_base::sync_with_stdio (true);
    std::string line;
    unsigned dependency_var = 0;
    while (getline (std::cin, line)) {
        dependency_var += line.size();
    }
    std::cout << dependency_var << '\n';
}

void unsynced() {
    std::ios_base::sync_with_stdio (false);
    std::string line;
    unsigned dependency_var = 0;
    while (getline (std::cin, line)) {
        dependency_var += line.size();
    }
    std::cout << dependency_var << '\n';
}

void usage() { std::cout << "one of (synced|unsynced|stdio), pls\n"; }

int main (int argc, char *argv[]) {
    if (argc < 2) { usage(); return 1; }

    if (std::string(argv[1]) == "synced") test (synced);
    else if (std::string(argv[1]) == "unsynced") test (unsynced);
    else if (std::string(argv[1]) == "stdio") test (std_io);
    else { usage(); return 1; }

    return 0;
}

使用g ++ -O3和一个大文本文件:

cat testfile | ./a.out stdio
...
0.34 sec

cat testfile | ./a.out synced
...
1.31 sec

cat testfile | ./a.out unsynced
...
0.08 sec

这适用于您的情况取决于.修改这个玩具基准测试,增加更多的测试和比较例如像std::cin >> a >> b >> c用scanf ("%d %d %d", &a, &b, &c);.我保证,通过优化(即不处于调试模式),性能差异将是微妙的.

如果这不能满足您的需求,您可以尝试其他方法,例如首先读取整个文件(可能会或可能不会带来更多性能)或内存映射(这是一个非便携式解决方案,但大型桌面有它们).

更新

格式化输入:scanf与流

#include <cstdio>
#include <iostream>

template <typename Test> 
void test (Test t)
{
    const clock_t begin = clock();
    t();
    const clock_t end = clock();
    std::cout << (end-begin)/double(CLOCKS_PER_SEC) << " sec\n";
}

void scanf_() {
    char x,y,c;
    unsigned dependency_var = 0;

    while (!feof (stdin)) {
        scanf ("%c%c%c", &x, &y, &c);
        dependency_var += x + y + c;
    }

    std::cout << dependency_var << '\n';
}

void unsynced() {
    std::ios_base::sync_with_stdio (false);
    char x,y,c;
    unsigned dependency_var = 0;
    while (std::cin) {
        std::cin >> x >> y >> c;
        dependency_var += x + y + c; 
    }
    std::cout << dependency_var << '\n';
}

void usage() { std::cout << "one of (scanf|unsynced), pls\n"; }

int main (int argc, char *argv[]) {
    if (argc < 2) { usage(); return 1; }

    if (std::string(argv[1]) == "scanf") test (scanf_);
    else if (std::string(argv[1]) == "unsynced") test (unsynced);
    else { usage(); return 1; }

    return 0;
}

结果:

scanf: 0.63 sec
unsynced stream: 0.41 

Answer 2

通常,缓冲输入将是最快的.您必须刷新输入缓冲区的频率越低,输入就越快.有关完整且内容丰富的讨论,请参阅此问题.简而言之,具有大缓冲区大小的read()速度与您可以获得的速度一样快,因为它几乎直接位于操作系统中相应的系统调用之上.