Как ускорить консольный ввод и вывод ? c++

Question

Есть консольная программа, работу которой очень замедляет ввод и вывод данных. Количество запросов - до 100000, в одном запросе число от -1 до 1, пробел, число от -10 в 9 степени, до 10 в 9 степени. С scanf, printf работает слишком медленно. Пытался использовать getchar, но он записывает только 1 символ.

#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

int main()
{
    int n, a, N, I, J;
    vector<int> vec;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a, &N);
        if (a == 1)
        {
            I = 0;
            J = vec.size();
            if (vec.size() != 0)
            {
                while (J - I > 0)
                {
                    if (N < vec[(I + J) / 2])
                    {
                        J = (I + J) / 2;
                    }
                    else
                    {
                        I = (I + J) / 2;
                        if (J - I <= 1)
                        {
                            I = J;
                            break;
                        }
                    }
                }
                vector<int>::iterator it = vec.begin() + J;
                vec.insert(it, N);
            }
            else vec.push_back(N);
        }
        else if (a == -1)
        {
            auto f = lower_bound(vec.begin(), vec.end(), N);
            vec.erase(f);
        }
        else
        {
            printf("%d\n", vec[vec.size() - N]);
        }
    }
}

Answer 1

Давайте проверим как много времени потребляет ввод и вывод в этой задаче.

Сгенерируем вход максимального размера:

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror generate_input.cpp

#include <cstdio>

int main() {
    const int n = 100000;
    printf("%d\n", n);
    for (int i = 0; i < n; ++i) {
        switch (i % 3) {
            case 0: printf("+1 1000000000\n"); break;
            case 1: printf("0 1000000000\n"); break;
            case 2: printf("-1 1000000000\n"); break;
        }
    }
}

$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror generate_input.cpp
$ ./a.out >input
$ wc input 
 100001  200001 1366674 input
$ head input 
100000
+1 1000000000
0 1000000000
-1 1000000000
+1 1000000000
0 1000000000
-1 1000000000
+1 1000000000
0 1000000000
-1 1000000000

Затем сымитируем чтение и запись:

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror process_input.cpp

#include <cstdio>

int main() {
    int n;
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    for (int i = 0; i < n; ++i) {
        int c, k;
        if (scanf("%d%d", &c, &k) != 2) {
            return 1;
        }
        if (c == 0) {
            printf("%d\n", k);
        }
    }
}

$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror process_input.cpp
$ ./a.out <input >output
$ wc output
33333  33333 366663 output
$ head output
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

Прогоним обработку несколько раз:

$ time ./a.out <input >output

real  0m0.022s
user  0m0.016s
sys   0m0.004s

$ time ./a.out <input >output

real  0m0.023s
user  0m0.020s
sys   0m0.000s

$ time ./a.out <input >output

real  0m0.020s
user  0m0.012s
sys   0m0.004s

Худшее время 23ms. Проблема в алгоритме, не в чтении или записи.

БЛОГ НА HUSL

Как ускорить консольный ввод и вывод ? c++

Ответы (1 шт):