Как быстро читать из консоли в C#?

Question

Я изучаю C#, решаю задачи на https://acm.timus.ru/. Решения принимаются системой, однако по времени работы мои решения существенно медленней других в рейтинге. Прочитал, что, вероятно, узкое место в чтении из консоли и выводе в нее. Есть ли какой-то способ считывать быстро? UPD: Для примера привожу достаточно простую задачу https://acm.timus.ru/problem.aspx?space=1&num=1491

using System;
using System.Linq;
using System.Text;

namespace Task1491
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = Int32.Parse(Console.ReadLine());
            var coins = new int[n];
            var str = new int[3];

            for (int i = 0; i < n + 1; i++)
            { 
                str = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();
                if (str[2] > 0)
                {
                    coins[str[0] - 1] += str[2];
                    if (str[1] < n)
                        coins[str[1]] -= str[2];
                }
            }

            for (int i = 1; i < n; i++)
            {
                coins[i] += coins[i - 1];
            }

            Console.WriteLine(string.Join(" ", coins));
        }
    }
}

Это решение выполняется на за 0.109 при лимите 1 с. На мой взгляд сложность алгоритма O(N), поправьте, если ошибаюсь. Однако, в рейтинге решений на C# есть успешная попытка за 0,062. Это только пример, есть задачи, где в топе есть решения за 0,015 с, где я с линейным алгоритмом имею 0,100-0,150 с.

Answer 1

Что в вашем примере можно сделать:

Парсить числа со строки вручную
Подготовить вывод самому
Считать ввод с консоли только 1 раз (эта оптимизация не поможет, просто было интересно проверить)

Вот что у меня получилось

using System;
using System.IO;
using System.Text;

namespace Task1491
{
    class Program
    {
        static void Main(string[] args)
        {
            var sr = new StringReader(Console.In.ReadToEnd());

            var str = new int[3];
            var n = GetNumbers(str, sr.ReadLine())[0];

            var coins = new int[n + 1];

            for (int i = 0; i <= n; i++)
            {
                GetNumbers(str, sr.ReadLine());
                coins[str[0] - 1] += str[2];
                coins[str[1]] -= str[2];
            }

            var sb = new StringBuilder(n * 10);
            sb.Append(coins[0]);

            for (int i = 1; i < n; i++)
            {
                coins[i] += coins[i - 1];
                sb.Append(' ');
                sb.Append(coins[i].ToString());
            }

            Console.WriteLine(sb.ToString());
        }

        static int[] GetNumbers(int[] data, string input)
        {
            int dataIdx = 0;
            int inputIdx = 0;

            while (inputIdx < input.Length)
            {
                int acc = 0;
                while (inputIdx < input.Length && input[inputIdx] == ' ') inputIdx++;
                while (inputIdx < input.Length && input[inputIdx] != ' ')
                {
                    acc *= 10;
                    acc += input[inputIdx] - '0';
                    inputIdx++;
                }
                data[dataIdx++] = acc;
            }
            return data;
        }
    }
}

Отработало за 0,093.

Сложность такая же, как у вас - линейная.

Тот результат, о котором вы говорили - 0.063 - он был получен на другом компиляторе и скорее всего другой версией фреймворка, потому я бы не стал на него ровняться.

БЛОГ НА HUSL

Как быстро читать из консоли в C#?

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