(待完善)Go ACM模式处理输入输出

本文由 简悦 SimpRead 转码， 原文地址 tbghg.top

这里是 TBH 的博客，用于技术分享，记录日常。

背景

面试时 ACM 模式较多，力扣以核心代码模式为主，特地训练下 ACM 模式处理输入输出

推荐阅读

• ACM 模式较好的练习地点：https://kamacoder.com/
• Golang 常规处理输入输出：https://blog.csdn.net/weixin_44211968/article/details/124632136
• bufio 处理输入输出：https://www.acwing.com/blog/content/28740/

举例

在此用洛谷中的一道题说明一下：P1886 滑动窗口 /【模板】单调队列

使用常规输入输出：

折叠代码块 GO 复制代码

package main

import (
  "fmt"
  "strings"
)

func main() {
  var n, k int
  fmt.Scanln(&n, &k)
  list := make([]int, n)
  for i := 0; i < n; i++ {
    fmt.Scan(&list[i])
  }
  max, min := slidingWindow(list, k)
  
  fmt.Println(strings.Trim(fmt.Sprint(min), "[]"))
  fmt.Println(strings.Trim(fmt.Sprint(max), "[]"))
}

func slidingWindow(list []int, k int) (max, min []int) {
  var maxWindow, minWindow []int
  
  maxPush := func(i int) {
    for len(maxWindow) > 0 && list[maxWindow[len(maxWindow)-1]] < list[i] {
      maxWindow = maxWindow[:len(maxWindow)-1]
    }
    maxWindow = append(maxWindow, i)
  }
  
  minPush := func(i int) {
    for len(minWindow) > 0 && list[minWindow[len(minWindow)-1]] > list[i] {
      minWindow = minWindow[:len(minWindow)-1]
    }
    minWindow = append(minWindow, i)
  }
  for i := 0; i < k; i++ {
    maxPush(i)
    minPush(i)
  }
  max = append(max, list[maxWindow[0]])
  min = append(min, list[minWindow[0]])
  for i := k; i < len(list); i++ {
    maxPush(i)
    minPush(i)
    
    for maxWindow[0] < i-k+1 {
      maxWindow = maxWindow[1:]
    }
    for minWindow[0] < i-k+1 {
      minWindow = minWindow[1:]
    }
    max = append(max, list[maxWindow[0]])
    min = append(min, list[minWindow[0]])
  }
  return
}

结果就是有三个超时，其他通过，可自行尝试

分析下原因，每次fmt.Scan时都会进行一次系统调用，如果 N 较大，那时间开销相对就比较大，我们可以使用bufio库将数据直接读取到缓存中，整体只需要一次系统调用，时间开销要小很多

相应的，输出时如果我们选择 for 循环每次 print 一个数据，那时间开销也会很长，但将数据通过strings.Trim(fmt.Sprint(min), "[]")处理好之后再输出，总共两次fmt.Println系统开销要小很多。同时我们也可以把结果放到缓冲区中，再通过Flush将数据写出

我们先来看处理输入：

折叠代码块 GO 复制代码

import (
  "bufio"
  "fmt"
  "os"
  "strings"
)

func main() {
  var n, k int
  fmt.Scanln(&n, &k)
  list := make([]int, n)

  
  
  in := bufio.NewReader(os.Stdin)
  
  
  
  for i := 0; i < n; i++ {
    fmt.Fscan(in, &list[i])
  }

  max, min := slidingWindow(list, k)
  fmt.Println(strings.Trim(fmt.Sprint(min), "[]"))
  fmt.Println(strings.Trim(fmt.Sprint(max), "[]"))
  return
}

修改后，所有数据点可通过

我们再来看下输出，这时我们用了两次fmt.Println，也就是会进行两次系统调用，那我们如果将结果写入输出的缓存中，最后os.Flush是不是可以对时间进一步优化呢，原则上是这样的：

折叠代码块 GO 复制代码

func main() {
  var n, k int
  fmt.Scanln(&n, &k)
  list := make([]int, n)

  
  in := bufio.NewReader(os.Stdin)
  out := bufio.NewWriter(os.Stdout)

  for i := 0; i < n; i++ {
    fmt.Fscan(in, &list[i])
  }

  max, min := slidingWindow(list, k)
  
  
  
  fmt.Fprint(out, fmt.Sprint(strings.Trim(fmt.Sprint(min), "[]")+"\n"+strings.Trim(fmt.Sprint(max), "[]")))
  
  out.Flush()
  return
}

最后的运行结果是有一个点报 MLE 了（按照第二种写法，那个点是 100.16MB）

这个也比较好理解，对于数据量比较变态的情况，及时将数据输出，可以预防 MLE，所有结果合起来再输出，就有可能会超出规定内存

当然，输入也有可能会超出默认缓存大小，这个时候需要根据实际情况进行调整，例如 https://www.acwing.com/blog/content/28740/ 中提到的：

特殊场合 当一次输入超大时：3302. 表达式求值

将输入缓存设置为20000 * 1024

折叠代码块 GO 复制代码

in = bufio.NewScanner(os.Stdin)
bs = make([]byte, 20000 * 1024)

in.Buffer(bs, len(bs))