Как быстро ввести миллионы целых чисел в C ++?

Question

Я занимаюсь программированием структуры данных о стеке в C ++.

В этом задании я должен прочитать много целых чисел (в худшем случае я должен прочитать 1 600 000 целых чисел) и, наконец, вывести несколько строк.

Будучи студентом, я отправляю свой исходный файл cpp, и веб-сайт оценивает и оценивает мой исходный код. Я получил 100%, но я хочу сделать лучше. Ограничение времени этого назначения составляет 2 секунды, а время выполнения моего исходного кода составляет 128 миллисекунд. Тем не менее, лучший ученик использовал только 52 миллисекунды для выполнения задачи. Поэтому я хочу знать, как сделать мой код быстрее.

Мой исходный код в основном состоит из трех частей:

1. используйте cin для чтения большого числа целых чисел из системы OnlineJudge (до 1 600 000 целых чисел).
2. попытаться найти решение и сохранить его в массиве символов.
3. используйте cout для вывода массива char.

OnlineJudge сообщает мне время выполнения моего кода. Первая часть занимает 100 миллисекунд, вторая часть - 20 миллисекунд, а третья часть - 12 миллисекунд. Поэтому, если я хочу ускорить мой код, я должен улучшить скорость ввода.

Ввод OnlineJudge выглядит следующим образом:

5 2
1 2 3 5 4

1-я строка - это два целых числа n и m, 2-я строка - это n целых чисел, разделенных пробелами. Ограничения: 1 <= n <= 1 600 000 и 0 <= m <= 1 600 000. Чтобы прочитать более 1 миллиона целых чисел, мой код выглядит так: </p>

#include <iostream>
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int *exit = new int[1600000];
    cin>>n>>m;
    for (int i=0;i<n;++i)
        cin>>exit[i];
    return 0;
}

Если n мало, OnlineJudge говорит, что время выполнения составляет 0 миллисекунд. если n очень большое, например 1600000. OnlineJudge говорит, что этот код занимает 100 миллисекунд. Если я удалю

std::ios::sync_with_stdio(false);
cin.tie(NULL);

Тогда код занимает 424 миллисекунды. Тем не менее, чтение целых чисел необходимо в этом задании, поэтому мне действительно любопытно, как лучший ученик может закончить «cin, find the solution, cout» всего за 52 миллисекунды.

У вас есть идеи по улучшению скорости ввода?

2019.4.17 ： Кто-то предлагает использовать vector или std :: from_chars, но в этом назначении они запрещены. Если я напишу

#include <vector>

или

#include <charconv>

или

#include <array>

тогда OnlineJudge говорит: «Ошибка компиляции».

Кто-то предлагает использовать scanf, мой код такой:

for (int i=0;i<n;++i)
    scanf("%d", &exit[i]);

Но время выполнения составляет 120 миллисекунд. Кстати, я не думаю, что scanf быстрее, чем cin, Использование scanf () в программах на C ++ быстрее, чем использование cin?

Кто-то предлагает использовать getline. Я редко использую эту функцию, мой код выглядит так:

stringstream ss;
string temp;
getline(cin, temp);
ss<<temp;ss>>n;ss>>m;
ss.clear();temp.clear();
getline(cin, temp);ss<<temp;
for (int i=0;i<n;++i)
    ss>>exit[i];

Время выполнения также составляет 120 миллисекунд.

Кто-то предлагает использовать mmap. Я никогда не слышал эту функцию раньше. Кажется, эта функция доступна только в Unix? Но я использую Visual Studio 2010. Мой код выглядит так:

#include <unistd.h>
#include <sys/mman.h>
    //to load 1,600,000 integers
    int *exit = static_cast<int*>(mmap(NULL,1600*getpagesize(),PROT_READ,MAP_ANON|MAP_SHARED,0,0));
    for (int i=0;i<n;++i)
        cin>>*(exit+i);

OnlineJudge говорит «Ошибка времени выполнения (сигнал 11)» вместо «Ошибка компиляции», сигнал 11 означает «Недопустимая ссылка на память», этот сигнал отправляется процессу, когда он делает недопустимую ссылку на виртуальную память или ошибку сегментации, т.е. когда он выполняет нарушение сегментации. Я не знаю, если что-то не так с моим Mmap. Надеюсь, вы можете сказать мне.

2019.4.22 ： Спасибо за вашу помощь. Теперь я успешно решаю эту проблему. Ключевой функцией является mmap. Код выглядит так:

#include <sys/mman.h>
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    string temp;

    int n,m;
    int *exit = new int[1600000];

    const int input_size = 13000000;
    void *mmap_void = mmap(0,input_size,PROT_READ,MAP_PRIVATE,0,0);
    char *mmap_input = (char *)mmap_void;
    int r=0,s=0;
    while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
    while (mmap_input[s]>='0' && mmap_input[s]<='9')
    { r=r*10+(mmap_input[s]-'0');++s; }
    n=r;r=0;
    while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
    while (mmap_input[s]>='0' && mmap_input[s]<='9')
    { r=r*10+(mmap_input[s]-'0');++s; }
    m=r;r=0;
    while (mmap_input[s]<'0' || mmap_input[s]>'9') ++s;
    for (int i=0;i<n;++i)
    {
        while (mmap_input[s]>='0' && mmap_input[s]<='9')
        { r=r*10+(mmap_input[s]-'0');++s; }
        ++s;
        exit[i]=r;r=0;
    }

Время выполнения mmap и преобразования символов в целые числа занимает 8 миллисекунд. Теперь общее время выполнения этого домашнего задания занимает 40 миллисекунд, что быстрее 52 миллисекунд.

Answer 1

Несколько идей:

1. Читайте целые числа, используя std::scanf, а не std::istream.Последний, как известно, медленнее по нескольким причинам, даже при вызове std::ios::sync_with_stdio(false).
2. Чтение файла путем сопоставления его с памятью.
3. Разбор целых чисел быстрее, чем scanf и strtol.

Пример:

#include <cstdio>

int main() {
    int n, m, a[1600000];
    if(2 != std::scanf("%d %d", &n, &m))
        throw;
    for(int i = 0; i < n; ++i)
        if(1 != std::scanf("%d", a + i))
            throw;
}

Вы также можете развернуть этот цикл scanf для чтения нескольких целых чисел за один вызов.Например:

#include <cstdio>

constexpr int step = 64;
char const fmt[step * 3] =
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d "
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d "
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d "
    "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d"
    ;
void main() {
    int a[1600000];
    int n, m;
    if(2 != std::scanf("%d %d", &n, &m))
        throw;

    for(int i = 0; i < n; i += step) {
        int expected = step < n - i ? step : n - i;
        int* b = a + i;
        int read = scanf(fmt + 3 * (step - expected),
                         b + 0x00, b + 0x01, b + 0x02, b + 0x03, b + 0x04, b + 0x05, b + 0x06, b + 0x07,
                         b + 0x08, b + 0x09, b + 0x0a, b + 0x0b, b + 0x0c, b + 0x0d, b + 0x0e, b + 0x0f,
                         b + 0x10, b + 0x11, b + 0x12, b + 0x13, b + 0x14, b + 0x15, b + 0x16, b + 0x17,
                         b + 0x18, b + 0x19, b + 0x1a, b + 0x1b, b + 0x1c, b + 0x1d, b + 0x1e, b + 0x1f,
                         b + 0x20, b + 0x21, b + 0x22, b + 0x23, b + 0x24, b + 0x25, b + 0x26, b + 0x27,
                         b + 0x28, b + 0x29, b + 0x2a, b + 0x2b, b + 0x2c, b + 0x2d, b + 0x2e, b + 0x2f,
                         b + 0x30, b + 0x31, b + 0x32, b + 0x33, b + 0x34, b + 0x35, b + 0x36, b + 0x37,
                         b + 0x38, b + 0x39, b + 0x3a, b + 0x3b, b + 0x3c, b + 0x3d, b + 0x3e, b + 0x3f);
        if(read != expected)
            throw;
    }
}

---

Другим вариантом является ручной анализ целых чисел (здесь может помочь отображение файла в память, и есть гораздо более быстрые алгоритмы синтаксического анализа целых чисел, чем этот и стандартный atoi/strtol, см. Fastware - Андрей Александреску ):

int main() {
    int n, m, a[1600000];
    if(2 != std::scanf("%d %d", &n, &m))
        throw;

    for(int i = 0; i < n; ++i) {
        int r = std::getchar();
        while(std::isspace(r))
            r = std::getchar();
        bool neg = false;
        if('-' == r) {
            neg = true;
            r = std::getchar();
        }
        r -= '0';
        for(;;) {
            int s = std::getchar();
            if(!std::isdigit(s))
                break;
            r = r * 10 + (s - '0');
        }
        a[i] = neg ? -r : r;
    }
}

---

Еще один способ - отобразить файл в память и быстрее его проанализировать:

#include <boost/iostreams/device/mapped_file.hpp>

inline int find_and_parse_int(char const*& begin, char const* end) {
    while(begin != end && std::isspace(*begin))
        ++begin;
    if(begin == end)
        throw;
    bool neg = *begin == '-';
    begin += neg;
    int r = 0;
    do {
        unsigned c = *begin - '0';
        if(c >= 10)
            break;
        r = r * 10 + static_cast<int>(c);
    } while(++begin != end);
    return neg ? -r : r;
}

void main() {
    boost::iostreams::mapped_file f("random-1600000.txt", boost::iostreams::mapped_file::readonly);
    char const* begin = f.const_data();
    char const* end = begin + f.size();
    int n = find_and_parse_int(begin, end);
    int m = find_and_parse_int(begin, end);

    int a[1600000];
    for(int i = 0; i < n; ++i)
        a[i] = find_and_parse_int(begin, end);
}

---

Исходный код эталонного теста .

Обратите внимание, что результаты могут значительно различаться в разных версиях компиляторов и стандартных библиотек:

• CentOS выпуск 6.10, g ++ - 6.3.0, Intel CoreПроцессор i7-4790 @ 3,60 ГГц

---- Best times ----
seconds,    percent, method
0.167985515,  100.0, getchar
0.147258495,   87.7, scanf
0.137161991,   81.7, iostream
0.118859546,   70.8, scanf-multi
0.034033769,   20.3, mmap-parse-faster

• Ubuntu 18.04.2 LTS, g ++ - 8.2.0, процессор Intel Core i7-7700K @ 4,20 ГГц

---- Best times ----
seconds,    percent, method
0.133155952,  100.0, iostream
0.102128208,   76.7, scanf
0.082469185,   61.9, scanf-multi
0.048661004,   36.5, getchar
0.025320109,   19.0, mmap-parse-faster

Answer 2

время моего исходного кода составляет 128 миллисекунд.Тем не менее, лучший ученик использовал только 52 миллисекунды

Чтобы запустить всю программу, это попадает в область погрешности.Настройка процессов в современной ОС занимает некоторое время, как и все, что вводит входные данные, и, если сервер является общим ресурсом, возникают проблемы с конфликтом ресурсов.Сколько варьируется отправка одного и того же точного кода?

int * exit = new int [1600000];

Выделения памяти имеют стоимость.В высокопроизводительных циклах и тому подобном их часто полностью избегают, хотя маловероятно, что одно выделение будет иметь существенное общее различие.

Ввод OnlineJudge выглядит следующим образом:

5 2
1 2 3 5 4

1-я строка - это два целых числа n и m, 2-я строка - это n целых чисел, разделенных пробелами.Ограничения: 1 <= n <= 1 600 000 и 0 <= m <= 1 600 000.Чтобы прочитать более 1 миллиона целых чисел, мой код выглядит следующим образом: </p>

Я обнаружил, что std::cin и т. Д. Могут быть медленными, а в некоторых случаях так же могут работать функции разбора чисел.Если вы можете прочитать, скажем, всю строку за один раз, а затем проанализировать, это может быть быстрее.Для синтаксического анализа выигрыш, как правило, происходит за счет синтаксического анализа небезопасными способами , если вы можете использовать входные данные, например,

• Всегда ли '' является разделителем?Похоже, что это так, и вы можете особый случай до конца.Например, прочитайте всю «строку» в буфер, затем замените '\ n' на ''.
• Известно ли количество цифр?Всегда ли это 1 или какое-то другое небольшое число, например, меньше 5?
• Всегда ли числа находятся в допустимом диапазоне?
• Всегда ли входное значение является допустимым числом, нет случайных символов для проверки?
• Есть ли когда-нибудь отрицательные числа?

Зная эти вещи, которые вы могли бы сказать:

/*1 or 2 digit int, space delimiter. Advance p number of consumed chars.*/
int parse_small_int(char **p)
{
    int v = (*p)p[0] - '0';
    char c2 = (*p)[1];
    if (c2 == ' ') // 1 digit
    {
        return v;
    }
    else // assume 2 digit
    {
        v *= 10;
        v += (c2 - '0')
        (*p) += 2;
    }
}

Есть ли у вас какие-либо идеи по улучшению вводаскорость?

То же самое относится и к выводу, вы не показываете код, но std :: cout может быть таким же медленным.А если вам известны некоторые сведения о числах и разрешенном формате вывода, вы можете легко набрать <<, std::to_string, itoa и т. Д.

• Допустимы ли начальные нули?Если это так, вы можете написать безусловный форматер для максимально допустимого значения.
• Выполните такое форматирование в предварительно выделенном буфере, а затем напечатайте всю строку.

, например

// always write 2 chars to p
void format_int_2_digit(int i, char *p)
{
    p[0] = '0' + (i / 10);
    p[1] = '0' + (i % 10);
}

Другая возможность - обойти библиотеку C ++ и даже C, хотя это может быть запрещено в вашем назначении.

Например, в Linux вы можете использовать read и write функции с STDIN_FILENO и STDOUT_FILENO.Я никогда не сравнивал их лично с версиями CRT, но, возможно, есть заметная разница.В Windows есть ReadConsole, WriteConsole и т. Д., или , используйте GetStdHandle, а затем ReadFile, WriteFile и т. Д.Опять же, я никогда не измерял это.