Golang学習メモ Week6

先週の振り返り

ほんまにかくことがなかった。競技プログラミングを学習の根底に置いている都合上、文法だとか関数だとかが本当に出てこない。

今週の学習内容

Golang

1. Go 標準入力（大規模データ）

bufio.NewScanner()を基本使っているが、これは大体64KBを超えるとバッファオーバーフローが発生し読み込めなくなる。
そのため大規模データの読み込みを行う場合は、以下のいずれかで対策しなくてならない。
分割でI/Oを増やすか、メモリを大きく確保するかのどちらかになるかな？
必要なバッファサイズが大きすぎる場合はScannerを使うよりReaderのが強いらしいのでどの方法でもできるようにしておきたい。

対策1 単語単位の読み取り

main.go

sc2 := bufio.NewScanner(os.Stdin)
// 読込を円滑にするために単語単位で読み込めるように
sc2.Split(bufio.ScanWords)

// 単語の読み取り完了までスキャン繰り返し
for sc2.Scan() {
    txt := sc2.Text() // 1単語スキャン
    ...
}

対策2 バッファサイズ増加

main.go

// デフォルトの64KBバッファから1MBバッファに更新
const maxScanTokenSize = 1024 * 1024
sc3.Buffer(make([]byte, maxScanTokenSize), maxScanTokenSize)
// 1行スキャン
stringArray := strings.Split(sc3.Text(), separator)
...

対策3 Readerの利用

main.go

// Reader定義
var reader = bufio.NewReader(os.Stdin)
// 1行スキャン
line, _ := reader.ReadString('\n')
// 改行記号を取り除く
line = strings.TrimSpace(line)
...

2. Go 数値変換(int64型)

過去にstrconv.Atoi(str)を使って文字列変換していたが、これではint(int32)型になってしまい、桁数の多い整数値の変換ができない。
そこで別の関数strconv.partInt()を使う

main.go

// (数値変換文字, n進数, int型の規模)を引数で指定 
a, _ := strconv.ParseInt(str, 10, 64)

アルゴリズム

1. 線形探索、遂次探索

配列に格納されたデータに対して、先頭から末尾まで順番に目的のデータを探す手法。
シンプルが故にデータの量が多くなればなるほど計算量も多くなる欠点を持つ。

main.go

for i, v := range list {
    if v == k {
        // 見つかれば何かアクション
    }
}

今週のまとめ

今週は競技プログラミングで使うアルゴリズムの学習兼、実際に競技プログラミングで詰まった箇所の改善ポイントをまとめた。
正月休みを満喫したが記載内容が０じゃないので私はとてもえらいということにしておく。