Быстрый консольный ввод на .NET15.12.2022 22:16

Во времена, когда .NET был закрытой технологией только для Windows, за ним и языком C# закрепилась репутация платформы, которая отлично подходит для решения бизнес-задач, но непригодна для соревновательного программирования и написания высокопроизводительного кода.

Часто приходится слышать, что «шарпы медленные», особенно в контексте алгоритмических задач, например с timus.online и codeforces.com. И, увы, не только слышать, но и сталкиваться с реальными проблемами, связанными с особенностями платформы, получая Wrong Answer, Runtime Error, Memory Limit, Time Limit при корректном алгоритме.

Большинство этих проблем кроется в особенностях консольного ввода и вывода. Да и часто куда проще написать cin >> nили sc.nextInt(), чем int.Parse(Console.ReadLine()) или Console.ReadLine().Split().Select(int.Parse).ToArray(), из-за чего выбор падает на другой язык.

Далее я расскажу о распространённых проблемах с консольным вводом-выводом в .NET, и о том, как сделать ввод быстрым и удобным.


Плавающая запятая

Иногда требуется считать или вывести число с плавающей точкой. Но легко забыть, что плавающие точки в .NET бывают запятыми, в зависимости от локали. Об этом особенно легко забыть, если пользоваться английской локалью в своей операционной системе.

Варианта решения два:


  • задать локаль потока: Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
  • передавать CultureInfo.InvariantCulture явно в такие методы, как (Try)Parse и ToString

Также в современном .NET есть параметр рантайма InvariantGlobalization, позволяющий избежать подобных проблем.


Ввод и вывод

Представим, что нам дана простая задача: нужно считать $N (N <= 2*10^5)$ строк по 4 числа int в каждой $(a_i < 10^6)$, числа разделёны пробелами. Требуется вывести сумму чисел для каждой строки.

int n = int.Parse(Console.ReadLine());
for (int i = 0; i < n; ++i)
{
  var result = Console.ReadLine().Split().Select(int.Parse).Sum();
  Console.WriteLine(result);
}

Может ли в этом коде что-то привести к вердикту, отличному от Accepted? Запросто.


Особенности форматирования

В условии ничего не сказано про количество пробелов, которыми разделены числа. И в итоге, если где-то пробелов больше одного, Console.ReadLine().Split() вернёт массив, содержащий пустые строки. А int.Parse упадёт с исключением, что приведёт к вердикту Runtime Error. Может показаться, что такого не бывает на контестах, но увы, случай вполне реальный.

Исправляем код: 

int n = int.Parse(Console.ReadLine());
for (int i = 0; i < n; ++i)
{
  var result = Console.ReadLine()
    .Split(' ', StringSplitOptions.RemoveEmptyEntries)
    .Select(int.Parse)
    .Sum();

  Console.WriteLine(result);
}

Неприятный нюанс, о котором надо помнить. Кстати, если раньше код обрабатывал все пробельные символы как разделители, то теперь только пробелы. Исправить можно, но будет чуть длиннее.

Проблема возникает только при построчном чтении ввода. В языках, где есть готовые способы для считывания с консоли чисел (например int n; cin >> n), проблемы не возникает вообще.


Console Flush

Потоки ввода и вывода stdin/stdout/stderr устроены на основе буфера в памяти, в который один процесс может записать данные, а другой — прочитать. Обращаться к этому буферу ради нескольких байт — дорого, поэтому для эффективности каждый процесс может дополнительно буферизовать ввод/вывод. Продвижение данных в буфер потока происходит либо при заполнении локального, либо при вызове .Flush().

Вызов .Flush() имеет большой смысл для интерактивных консольных приложений — пользователю нужно показать вывод в терминале сразу, а не копить его в памяти. Большинство платформ изначально адаптированы под этот сценарий и вызывают .Flush() автоматически после каждой записи.


Обратите внимание, что бывают и задачи, в которых требуется интерактивный ввод-вывод (request-response семантика). Например задачи, в которых требуется вычислить ответ, задавая «вопросы» проверяющей системе (простейший пример — программа, угадывающее слово в условном «Поле чудес», «общающаяся» с программой-ведущим)

Чтобы сэкономить на Flush, в C++ iostreams пишут: 

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

А в C# можно использовать StreamWriter для stdout вместо Console: 

const int bufferSize = 16384;
using var input = new StreamReader(
  Console.OpenStandardInput(), bufferSize: bufferSize);
using var output = new StreamWriter(
  Console.OpenStandardOutput(), bufferSize: bufferSize);

int n = int.Parse(input.ReadLine());
for (int i = 0; i < n; ++i)
{
  var result = input.ReadLine()
    .Split(' ', StringSplitOptions.RemoveEmptyEntries)
    .Select(int.Parse)
    .Sum();

  output.WriteLine(result);
}

Проверим, оказывает ли .Flush() влияние на производительность замерами. Версия с Console.WriteLine отрабатывает на моём компьютере за ~490ms, а с использованием StreamWriter — за 105ms. Т.е. причина плохой производительности оказалась вовсе не в LINQ. В проверяющей системе c более медленным железом можно запросто получить Time Limit Exceed, если не учитывать автоматический .Flush(). Кстати, на заметку, в энтерпрайз приложениях проблема тоже встречается — в логировании.

Замерял на Linux, рантайм .NET 7 NativeAOT — так достигается минимальный оверхед на старте программы, порядка 1.5 ms. На Windows как минимум старт процесса был бы порядка 10 ms, даже для C++.

Для чтения также можно использовать StreamReader вместо Console. Это позволяет сэкономить на проверке, не переопределён ли Console.In при каждом чтении и использовать увеличенный буфер, но выигрыш куда менее впечатляющий — единицы миллисекунд

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


Задача на ввод: аллокации

Задача 1510 с Тимуса. Для этой задачи есть два решения — за линию и с сортировкой. Её все сдают легко на том же C++, но на C# даже с умным алгоритмом из-за особенностей стандартного ввода будет Memory Limit Exceed. Почему?

В задаче установлен Memory Limit в 16 MB. Зачем? Не знаю, сохранить все числа в памяти и отсортировать он никак не мешает, ведь 500000 чисел по 4 байта — всего лишь 2 MB. Но в C# чтение ввода через Console.ReadLine приводит к аллокации строк. А строка с числом из 10 цифр, это не 4 байта, а, как минимум:


  • 16 байт на заголовок объекта и указатель на Method Table
  • 4 байта на хранение длины
  • 20 байт на 10 символов в UTF-16
  • 2 байта на null terminator для совместимости с нативным кодом, его ожидающим

Т.е. уже 42 байта на 10 символов. А 500000 раз по 42 байта — это уже 21 MB.

Но они же короткоживущие?! Читаем строку, сразу парсим, GC как-нибудь соберёт. Но срабатывание GC — не гарантированно, освобождение памяти обратно в ОС — тоже, а принудительный вызов через GC.Collect() может привести уже к Time Limit Exceed.

Как же быть? Писать ввод самостоятельно


Кастомный ввод


Дедовское решение

По C++ вспоминается решение с посимвольным чтением чисел.

Перепишем его на C# с использованием Console.Read(), а лучше — StreamReader.Read(). В этом случае использовать StreamReader оправдано, потому что обращаться к Console на каждый символ гораздо дороже, чем на каждую строку при использовании ReadLine.

После этого задача не представляет никакой сложности. На моём компьютере посимвольное чтение отрабатывает в 2 раза быстрее, чем с Console.ReadLine().


fastscan 
StreamReader reader = new StreamReader(Console.OpenStandardInput(), bufferSize: 32768);

int fastscan()
{
    bool negative = false;
    bool read_start = false;

    int number = 0;

    while (true)
    {
        int c = reader.Read();

        if (c=='-')
        {
            negative = true;
            read_start = true;
            continue;
        }

        if (c>47 && c<58)
        {
            number = number * 10 + (c - 48);
            read_start = true;
            continue;
        }

        if (read_start)
            break;
    }

    if (negative)
        number *= -1;
    return number;
}

Решение, однако, не идеально. Этот метод подходит для целых чисел, а сделать корректный парсинг чисел с плавающей точкой нетривиально, легко попасть на граничные случаи и ошибиться с точностью. Чтобы это понять, достаточно посмотреть Pull Request.


Тиктокерское решение

В современном .NET есть перегрузки методов Parse и TryParse принимающие ReadOnlySpan вместо строки. Вместо ручного парсинга чисел, можно записать фрагмент символов с числом в буфер и вызвать стандартный метод для парсинга.

Это решит проблему с парсингом чисел с плавающей точкой «дедовского» решения, а также сделает ввод кода удобнее, избавив от необходимости писать конструкции вида Console.ReadLine().Split().Select(int.Parse).ToArray(). Сам код настолько прост, что может быть легко написан прямо во время контеста (но не учитывает, например, переполнение буфера, если вам это важно):


SpanScanner 
class Scanner
{
    StreamReader input = new(Console.OpenStandardInput(), bufferSize: 16384);
    char[] buffer = new char[4096];

    public int ReadInt()
    {
        int length = 0;
        bool readStart = false;
        while (true)
        {
            int ch = input.Read();
            if (ch == -1)
                break;

            if (char.IsWhiteSpace((char)ch))
            {
                if (readStart) break;
                continue;
            }

            readStart = true;
            buffer[length++] = (char)ch;
        }

        return int.Parse(buffer.AsSpan(0, length), CultureInfo.InvariantCulture);
    }
}

Да, работает медленнее «дедовского» варианта, но на уровне с общепринятыми способами ввода, не аллоцирует memory traffic, и уж точно не станет причиной попадания в Time или Memory Limit.


На C++ и других языках можно написать и более эффективные варианты консольного ввода. scanf и cin взяты только для того, чтобы ориентироваться на способы чтения ввода, которые обычно укладываются в пределы Time Limit

Для .NET 7 и C# 11 можно сделать generic версию на основе статического метода интерфейса ISpanParsable. Правда, в проверяющих системах C# 11 ещё не поддерживается.


SpanParsableScanner 
class Scanner
{
    StreamReader input = new(Console.OpenStandardInput(), bufferSize: 16384);
    char[] buffer = new char[4096];

    public T Read() where T : ISpanParsable
    {
        int length = 0;
        bool readStart = false;
        while (true)
        {
            int ch = input.Read();
            if (ch == -1)
                break;

            if (char.IsWhiteSpace((char)ch))
            {
                if (readStart) break;
                continue;
            }

            readStart = true;
            buffer[length++] = (char)ch;
        }

        return T.Parse(buffer.AsSpan(0, length), CultureInfo.InvariantCulture);
    }
}

Также я подготовил более эффективный вариант кода на основе TryParse(ReadOnlySpan), но он слишком длинный, чтобы поместиться здесь. Он разгоняется в моём тесте до 24 мс за счёт чтения данных блоками.


Отказываемся от StreamReader

StreamReader — прослойка между Console Stream, в который обычно попадают ASCII-символы и .NET-строками в кодировке UTF-16. Переделаем код для работы со Stream напрямую.

Метод для парсинга, принимающий ReadOnlySpan уже не подойдёт. К счастью, в .NET есть класс под названием Utf8Parser— наследие разработки библиотеки System.Text.Json, решающее ту же задачу для спана байтов. Не обманывайтесь тем, что в названии есть Utf8 — парсить все 100500 цифр, которые есть в Unicode он не умеет. Зато с обычными ASCII-цифрами справляется на ура!

Достоинство Utf8Parser.TryParse в сравнении с T.TryParse— возможность парсить значение с префикса, без заранее подготовленного токена. Сравните: 

bool TryParse(ReadOnlySpan span, out int value, IFormatProvider provider);
bool TryParse(ReadOnlySpan span, out int value, out int bytesConsumed, char format='\0')

Первый метод заставляет заранее заглянуть вперёд и найти разделитель. Затем данные читаются снова для парсинга.

Второй же умеет останавливаться при парсинге токена сам, позволяя распарсить данные за один проход по буферу.

Т.к. Utf8Parser — достаточно узкоспециализированный класс, он не поддерживает IFormatProvider и локали. Но нам это только в радость — десятичная запятая нам здесь никак не помешает.

При использовании Utf8Parser нужно учитывать, что если данных в буфере осталось мало — результат может оказаться неверным. Если какой-то из текстовых токенов разобьётся на два разных чтения из потока данных, например [.........12][34...........], то Utf8Parser прочитает этот токен как два разных числа — 12 и 34. Или же для [........1e][7.......] вернётся false для 1e, и придётся делать дополнительную проверку: или это невалидный double или же просто не хватило данных.

Для упрощения реализации, буду требовать наличия в буфере некоторого минимального количества данных или признака окончания потока данных. Сам код тоже довольно прост и занимается только загрузкой данных из потока и пропуском разделителей, которыми здесь считаются все символы по пробел включительно. По желанию можно также пропускать символы, например, с кодами >= 128, на случай если в поток данных попадёт мусор.

Но во время контеста я бы лучше использовал предыдущий вариант на основе StreamReader и Span — он всё же гораздо проще


AsciiScanner 
class Scanner
{
    private const int MaxTokenLength = 1200;

    Stream? input = Console.OpenStandardInput();
    byte[] buffer = new byte[32768];
    Span Fragment => buffer.AsSpan(offset, length - offset);

    int offset;
    int length;

    public int ReadInt()
    {
        while (input != null && length - offset < MaxTokenLength)
        {
            if (offset != 0)
            {
                var remaining = Fragment.Length;
                Fragment.CopyTo(buffer);
                offset = 0;
                length = remaining;
            }

            var count = input.Read(buffer, length, buffer.Length - length);
            if (count <= 0)
            {
                input = null;
                break;
            }

            length += count;
            while (offset < length && buffer[offset] <= ' ') offset++;
        }
        while (offset < length && buffer[offset] <= ' ') offset++;

        var parsed = Utf8Parser.TryParse(Fragment, out int value, out int bytesConsumed);
        if (!parsed)
            Throw();
        offset += bytesConsumed;
        return value;
    }

    void Throw() => throw new Exception();
}


Замеры

В качестве тестовых данных использовался файл с 200000 строками шестизначных чисел по 4 числа в каждой (~5MB). Каждая программа считала XOR каждой из колонок и выводила ответ в конце. Таким образом, тестировалась только производительность ввода рассмотренными способами, с возможностью проверить корректность при тестировании. Входные данные предварительно загружались в память программы, производящей запуск тестируемых программ и подавались на stdin.

В качестве рантайма использовался .NET 7 NativeAOT на Linux. Этот вариант даёт меньше всего оверхеда на старте программы. C JIT на Windows оверхед составил ~36 мс, на Linux — ~70. Очерёдность по скорости для .NET-программ на Windows не отличается.

Тест не претендует на максимальную корректность, ставилась лишь цель оценить порядок разницы между способами чтения ввода.


Выводы


  • На .NET можно писать программы с интенсивным консольным IO.
  • Для достижения максимальной производительности рекомендуется:
    • не использовать статические методы Console.Write/WriteLine, а писать в stdout через StreamReader
    • для чтения большого количества чисел с консоли (или просто для удобства написания кода) использовать описанные способы: например с дополнительным буфером и неаллоцирующим TryParse(ReadOnlySpan)
    • правильно оценивать задачу и не переусложнять код без необходимости


Ссылки


© Habrahabr.ru