Эффективный ввод-вывод в разных языках программирования

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

Задача

В первой строке записано число n(n≤106). В следующих n строках записаны пары чисел. Посчитайте и выведите суммы чисел для каждой из n строк.

Пример ввода:

3
1 2
10 20
100 200 

Пример вывода:

3
30
300 

В системе Яндекс.Контест чтение из файла input.txt и из стандартного потока ввода мало отличаются. Мы будем использовать чтение из стандартного ввода как более простой способ. Если при тестировании программы вам нужно считать данные не с клавиатуры, а из файла, переписывать программу необязательно. Достаточно при запуске программы перенаправить содержимое файла с тестом в стандартный поток ввода программы. В командной строке это можно сделать, например, так: python solution.py < input.txt.

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

Во многих языках есть возможность считать все входные данные за раз и разбить их на строки. Не стоит пользоваться этим подходом, так как он чреват ошибками, которые трудно обнаружить. Например, в конце файла может как стоять символ новой строки, так и отсутствовать. Из-за этого иногда программа может считать на одну строку больше, чем нужно. Кажется, что проблемы можно было бы избежать, просто отбросив последнюю строку, если она пустая, но иногда пустая строка является корректными входными данными для программы. Гораздо надёжнее будет прямо следовать формату, указанному в тексте задачи.

Ещё одна проблема с переносами строки может возникнуть из-за того, что некоторые функции считывают строку вместе с символом перевода на новую строку, а некоторые функции его автоматически отбрасывают. Тщательно следите за тем, какие данные вы считали и как их обработали.

Также обратите внимание, что в файлах, созданных в Linux и macOS, строки разделяются символом '\n', а в Windows строки разделяются сразу парой символов: "\r\n".

Рассмотрим эффективные решения нашей задачи, написанные на разных языках программирования.

С++

#include <iostream>
using namespace std;

int main() {
    int num_lines;
    cin >> num_lines;
    for (int i = 0; i < num_lines; ++i) {
        int value_1, value_2;
        cin >> value_1 >> value_2;
        int result = value_1 + value_2;
        cout << result << '\n';
    }
    return 0;
} 

В коде на C++ обычно можно не думать про буферизацию, ведь стандартные функции позаботятся об этом за вас. Важно, что при выводе ответа мы используем '\n' вместо std::endl, чтобы лишний раз не вынуждать программу сбрасывать буфер.

Помимо скорости, в C++ нужно строго следить за корректностью использованных функций ввода и внимательно читать документацию. Например, если вам требуется считать строку текста, нельзя использовать метод cin >> line, поскольку этот метод считывает текст не до конца строки, а лишь до пробельного символа. Но даже если вы знаете, что в тексте нет пробелов, этот метод не подойдёт, ведь он не останавливается на начале первой строки, а «проглатывает» любое количество символов перевода строки. Вместо него подойдёт более предсказуемый метод std::getline(cin, line).

Go

package main
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var n int
    fmt.Scan(&n)
    reader := bufio.NewReader(os.Stdin)
    scanner := bufio.NewScanner(reader)
    scanner.Split(bufio.ScanLines)

    writer := bufio.NewWriter(os.Stdout)
    for i := 1; i <= n; i++ {
        var value_1, value_2 int
        scanner.Scan()
        line := scanner.Text()
        values := strings.Split(line, " ")
        value_1, _ = strconv.Atoi(values[0])
        value_2, _ = strconv.Atoi(values[1])
        result := value_1 + value_2
        output_string := strconv.Itoa(result)
        writer.WriteString(output_string)
        writer.WriteString("\n")
    }
    writer.Flush()
} 

Обратите внимание, что мы используем буфер bufio.Writer для вывода данных на печать. При помощи метода WriteString записываем строки в этот буфер. Когда вывод подготовлен, следует вызвать метод Flush, который отправит всю накопленную информацию в стандартный поток вывода.

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

В буфер нельзя напрямую записать число, поэтому предварительно нужно преобразовать его в строку функцией strconv.Itoa. В случаях, когда требуется более сложное форматирование, используйте функцию fmt.Sprintf.

Ввод данных тоже может серьёзно повлиять на скорость работы программы. Самым простым способом считать данные был бы fmt.Fscanf, который позволяет сразу считать данные в переменную нужного типа. Но если считывание является узким местом выполнения программы, мы можем сильно уменьшить время её работы при помощи bufio.Scanner. Строки, полученные при сканировании, нужно самостоятельно разбить пробелами и превратить в числа.

Java

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.lang.StringBuilder;
import java.util.StringTokenizer;

class Solution {
    public static void main(String[] args) throws IOException {
        StringBuilder output_buffer = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num_lines = Integer.parseInt(reader.readLine());
        for (int i = 0; i < num_lines; ++i) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int value_1 = Integer.parseInt(tokenizer.nextToken());
            int value_2 = Integer.parseInt(tokenizer.nextToken());
            int result = value_1 + value_2;
            output_buffer.append(result).append("\n");
        }
        System.out.println(output_buffer.toString());
    }
} 

Чтобы считывание было эффективным, в коде на Java требуется специальный класс BufferedReader.

Чтобы не делать много операций вывода, а просто подготовить строку, в которой будет записан результат, и вывести её за раз, нужно получить объединение строк. Для этого пригодится класс StringBuilder. Объекты этого класса специально созданы, чтобы к ним постепенно добавлять данные. Просто складывать строки — output_string = output_string + "\n" + result.toString() — неэффективное решение, ведь в процессе создаются новые строки, а старые уничтожаются. Создание нового объекта — дорогая операция, ведь для него нужно выделить память и совершить множество вспомогательных действий, которых лучше избегать.

Обратите внимание, что текст читается построчно, а для считывания двух чисел нужно применить класс StringTokenizer. Он будет читать текст, пока не встретит разделитель. Этот класс поочерёдно вернёт сначала первое число, затем второе. Такой способ работает существенно быстрее, чем класс Scanner или метод String.split.

Python

import sys

def main():
    num_lines = int(input())
    output_numbers = []
    for i in range(num_lines):
        line = sys.stdin.readline().rstrip()
        value_1, value_2 = line.split()
        value_1 = int(value_1)
        value_2 = int(value_2)
        result = value_1 + value_2
        output_numbers.append(str(result))
    print('\n'.join(output_numbers))

if __name__ == '__main__':
    main() 

Здесь мы тоже воспользовались буфером для выходных данных. Но хранить мы будем не одну строку, а массив строк. Склеим эти строки в один большой текст мы в последний момент, поскольку в Python нет эффективного способа добавить одну строку к другой, подобного StringBuilder в Java.

Весь код программы заключён в функцию main. Это нужно, чтобы код программы работал не с глобальными, а с локальными переменными функции main. Обращение к локальным переменным оказывается эффективнее.

Для чтения данных можно воспользоваться функцией input, но если требуется считать много данных, то sys.stdin.readline() будет существенно эффективнее. Обратите внимание, что к полученной строке мы применили метод rstrip, чтобы отбросить символ перевода строки. Функция input это делает автоматически.

Чтобы преобразовать данные к целым числам, мы могли воспользоваться конструкцией

value_1, value_2 = [int(x) for x in line.split()] 

или

value_1, value_2 = map(int, line.split()) 

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

Если вы привыкли типизировать код на Python, то для отправки в тестирующую систему, возможно, потребуется создать отдельную версию программы с удалёнными аннотациями типов. Дело в том, что подключение библиотеки typing (import typing) может занимать достаточно много времени.

NodeJS

var readline = require('readline');
var io_interface = readline.createInterface({input: process.stdin});

let output_numbers = [],
    line_number = 0,
    num_lines;
io_interface.on('line', function (line) {
  if (line_number === 0) {
    num_lines = parseInt(line);    
  } else if (line_number <= num_lines) {
    let values = line.split(" ");
    let value_1 = parseInt(values[0]),
        value_2 = parseInt(values[1]);
    let result = value_1 + value_2;
    output_numbers.push(result);
  }
  line_number++;
})

io_interface.on('close', function () {
  if (line_number < 1 + num_lines) {
    // последняя строка была пустой и потому не считана
    // здесь мы могли бы обработать эту ситуацию
  }
  process.stdout.write(output_numbers.join('\n'));
}) 

У программ на NodeJS довольно необычный способ чтения данных: каждая строка, прочитанная из потока ввода, генерирует событие line. Можно зарегистрировать обработчик, который будет обрабатывать каждое такое событие.

Когда данные прочитаны полностью, будет вызван обработчик события close. В этот момент мы можем запустить все вычисления, что нельзя было сделать, пока данные не были считаны полностью. И в этом же блоке нужно вывести результат.

Чтобы отдельно обработать первую строку, мы завели счётчик, который указывает номер строки. Обратите внимание, что даже если строк на вход программы передано больше, чем требуется, мы игнорируем лишние. А если строк во входных данных, наоборот, оказалось меньше, можно проверить это в обработчике события close, сравнив значение счётчика считанных строк с ожидаемым количеством. Такая ситуация может возникнуть и при корректном вводе программы, если последняя строка пустая.

Make

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

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

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

Вне зависимости от языка, на котором вы пишете, в таких задачах в качестве компилятора указывается make. Чтобы проверяющая система поняла, на каком языке написан ваш код, нужно отправить код задачи в виде файла с нужным расширением. Прикрепить текст в форму — недостаточно.

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



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий