Goにおけるバッファを用いた入出力高速化

初めに

これはGoLang初心者が勉強メモ用に残しているものなので、多少不正確なところがある可能性がある。悪しからず

GoLangにおける入出力

GoLangを用いて競技プログラミングをする際に、最初に直面する壁はおそらく

入出力に関するものだろう。

ただ標準入力から受け取るだけならそれほど困らないだろうが、競技プログラミングにおける、与えられた課題に対して指定された実行制限時間・メモリ範囲内で正しいプログラムを記述するという競技の特性上、場合によってはその標準入力の速度が原因で実行時間制限に間に合わないということが多々ある。

では、プログラムの処理以前に入出力の時点で効率の悪い処理をおこなってしまうことを避けるにはどうすればよいか。

fmt.Scanとbufio.Scanner

GoLangを用いて標準入力を受け取る方法は主に以下の二つがある。

• fmt.Scan()

• bufio.Scanner()/Reader()/Writer()

いずれも標準入力を受け取ることができるという点では共通だが、その行われ方という点では大きく異なる。

• 前者はいちいちio.Readerにアクセスを行い、読み込む。

• 後者はバッファにあらかじめまとめて複数読み込んだ後、アクセスを行い読み込む。

こういった性質上、複数の入力を処理する際、前者と後者で結構な数のシステムコールの回数の差分が発生し処理時間にも影響が出てくる。

具体的には、読み込みの回数が回くらいになってくると前者の方法は使い物にならない。初めの方の簡単な問題を除けば、大体の問題ではこれくらいのオーダーの入出力の回数が要求されることが多い。よって必然的に後者の方法を採用せざるを得ない。

早速GoLangの練習も兼ねて高速化をスマートに行うための構造体クラスの作成を行うことにした。

作成した構造体クラス

実際に作成した構造体クラスは以下の通り。

import (
    "bufio"
    "fmt"
    "io"
    "strconv"
    "strings"
)

const (
    MaxBufSize = int(1e4)
)

type CustomIO struct {
    //This structure can increase the speed of a program by reducing the number of system calls, which are typically slow operations.
    reader bufio.Reader
    writer bufio.Writer
    cache  []string
}

func MakeCustomIO(in io.Reader, out io.Writer, bufsize int) (*CustomIO, error) {
    if bufsize > MaxBufSize {
        return nil, fmt.Errorf("bufsize is too large")
    }
    io := &CustomIO{
        reader: *bufio.NewReaderSize(in, bufsize),
        writer: *bufio.NewWriterSize(out, bufsize),
        cache:  []string{},
    }
    return io, nil
}

func (io *CustomIO) NextLine() string {
    for len(io.cache) == 0 {
        text, err := io.reader.ReadString('\n')
        if err != nil {
            panic(err)
        }
        arr := strings.Split(strings.TrimRight(text, "\n"), " ")
        for i := len(arr) - 1; i >= 0; i-- {
            io.cache = append(io.cache, arr[i])
        }
    }
    res := io.cache[len(io.cache)-1]
    io.cache = io.cache[:len(io.cache)-1]
    return res
}

func (io *CustomIO) NextInt() int {
    res, err := strconv.Atoi(io.NextLine())
    if err != nil {
        panic(err)
    }
    return res
}

func (io *CustomIO) NextFloat(sep byte) float64 {
    res, err := strconv.ParseFloat(io.NextLine(), 64)
    if err != nil {
        panic(err)
    }
    return res
}

func (io *CustomIO) Print(objects ...interface{}) {
    _, err := fmt.Fprintln(&io.writer, objects...)
    if err != nil {
        panic(err)
    }
}

func (io *CustomIO) Printf(format string, objects ...interface{}) {
    _, err := fmt.Fprintf(&io.writer, format, objects...)
    if err != nil {
        panic(err)
    }
}

func (io *CustomIO) Flush() {
    err := io.writer.Flush()
    if err != nil {
        panic(err)
    }
}

使い方は主に以下の通り。

// 標準入力から受け取り,標準出力に返すように設定.
io, _ := MakeCustomIO(file_in, file_out, MaxBufSize)
 
//全てを書き込み終えてから終了.    
defer io.Flush()

a, b, c := io.NextInt(), io.NextInt(), io.NextInt()

io.Printf("%d %d %d\n", a, b, c)

実際の使用例

atcoder.jp

感想

特に問題ないように思えた。

以前まではbufioについてあまり理解しないで使用していたので、反省。

GoLangで競技プログラミングは難しいですね。