Быстрый ввод и вывод

Задача: прочитать числа и найти рекорды. Решение — один проход, O(n). Отправляем — превышено время на тесте с миллионом чисел. Алгоритм тут ни при чём: на этом тесте почти всё время уходит на то, чтобы прочитать вход. Ниже — одна и та же работа, прочитанная и напечатанная разными способами, с временем, измеренным на сервере сайта.

В Python input() медленнее чтения всего входа сразу в несколько раз, а в Go fmt.Scan прямо со стандартного ввода — в десятки. Разница не в разборе чисел — он везде одинаковый, — а в том, сколько стоит каждое обращение за следующей порцией.

Идея

Каждое обращение ко вводу или выводу имеет постоянную цену: вызов функции, проверки, а иногда и системный вызов — просьба к операционной системе, которая стоит сотни наносекунд и больше. Если платить её за каждое число или каждый байт, на миллионе чисел цена сложится в секунды. Быстрое чтение и запись платят её редко: читают сразу много, пишут накопленное одним куском.

Это та же амортизация, что у динамического массива: дорогое действие — обращение к системе — делается редко и большими порциями, и в пересчёте на одно число становится почти бесплатным. Буфер на 4096 байт делит число системных вызовов в четыре тысячи раз.

Python: что делает input()

Если подсмотреть, что вызывает input(), подставив вместо стандартных потоков объекты, которые считают обращения, выяснится: на каждый вызов он спрашивает у стандартного ввода номер файла, чтобы проверить, не терминал ли это, сбрасывает буферы стандартного вывода и стандартного потока ошибок и только потом читает строку. В интерактивной программе это правильно: подсказка должна появиться на экране раньше, чем человек начнёт печатать. А на миллионе строк из файла эти проверки и сбросы стоят больше, чем само чтение.

• sys.stdin.readline() — читает строку из того же буфера, без проверок. В несколько раз быстрее input(); если сохранить метод в переменную (readline = sys.stdin.readline), ещё немного быстрее.
• sys.stdin.buffer.read().split() — весь вход одним куском и одно разрезание по пробелам. buffer — это байты без перевода в текст; int умеет читать байты. Самый быстрый способ, когда вход помещается в память.
• Вывод: print на каждое число — это вызов функции с разбором аргументов и запись в буфер. Собрать строку и записать один раз — sys.stdout.write("\n".join(map(str, xs)) + "\n") — быстрее в несколько раз.

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
xs = list(map(int, data[1:n + 1]))
# … решение …
sys.stdout.write("\n".join(map(str, answer)) + "\n")

Go: системный вызов на байт

В Go причина другая. os.Stdin не буферизован: каждое чтение из него — системный вызов. А fmt.Scan читает вход по одному символу, чтобы не забрать лишнего, — и если дать ему os.Stdin напрямую, на каждый байт входа приходится отдельный системный вызов. Миллион чисел — это несколько миллионов байт и столько же обращений к системе. В песочнице сайта, где программы работают под gVisor, системный вызов ещё дороже, чем на обычной машине.

• fmt.Fscan(bufio.NewReader(os.Stdin), &x) — одна строка лишнего кода убирает системные вызовы, но fmt разбирает аргументы через рефлексию, и это всё ещё заметно.
• bufio.Scanner с ScanWords и strconv.Atoi — в разы быстрее. Внимание: по умолчанию строка сканера не длиннее 64 КБ, для длинных строк нужен sc.Buffer.
• Разбор чисел прямо из bufio.Reader по байту — самый быстрый: ни строк, ни рефлексии. Так написано эталонное решение задачи ниже.
• Вывод: fmt.Println пишет в небуферизованный os.Stdout — системный вызов на каждую строку. bufio.NewWriter(os.Stdout) и defer w.Flush() собирают вывод в буфер. Забытый Flush — классическая ошибка: программа молча теряет конец вывода.

in := bufio.NewReaderSize(os.Stdin, 1<<16)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
fmt.Fscan(in, &n) // для пары чисел fmt годится, для миллиона — readInt
// … решение …
fmt.Fprintln(out, answer)

Код

Сколько раз программа обращается к системе при разных способах чтения? Модель файла считает вызовы read: по байту, как fmt.Scan без буфера, через буфер в 4096 байт, как bufio и файлы Python, и всё сразу.

Сорок две тысячи обращений против двенадцати — в три с половиной тысячи раз меньше. А вот замер, по которому построена гонка: каждый способ — отдельная программа, которой файл подан на стандартный ввод, как в проверяющей системе. Отдельная — потому что в песочнице сайта input() подменён и спрашивает ввод у страницы.

Сколько это стоит

Все способы — O(размер входа): каждый байт так или иначе прочитан и разобран. Различается постоянный множитель, и он огромен: в гонке выше способы одного языка расходятся в разы и в десятки раз. На входе в сотню чисел этого не видно; на входе в мегабайт это разница между «принято» и «превышено время». Цена — память: чтение целиком держит весь вход, и на гигабайтных файлах читают кусками, через тот же буфер.

Прежде чем ускорять ввод, полезно прикинуть: если чисел до 10⁵, разница — миллисекунды, и input() вполне годится. С 10⁶ и больше — стоит сразу писать быстрый ввод. А если программа медленная, а вход маленький, дело не во вводе — тогда поможет профилировщик.

Задачи

Задача, в которой нужен только быстрый ввод: миллион дней температуры, рекорды жары и холода. Один из тестов — настоящие 85 лет погоды Алматы.