在程序设计竞赛中使用Go语言

最近在用Go写区块链。出于帮助熟悉Go语言和编程竞赛复健两个目的，想尝试用Go来刷点水题。寻找I\O的正确姿势就花了很长时间，最后找到这么一篇博客，赶紧搬运来。

Go语言在程序设计竞赛中用的不多，主要是因为Go没有类似STL那样的通用容器库。用Go做竞赛题，有时也不得不写一些冗余的代码，但是Go有没有实际用途呢？我们知道，Go在速度和内存使用方面非常快，而且Go特有的CSP模型使得我们可以更容易地构建并发管道（简单来说就是Go在并发性上有优势）。那么在程序设计竞赛中使用Go究竟有什么好处呢？先来看看几大程序设计赛事对Go的支持情况，以下数据统计自2018.3.2：

• HackerRank提供了Go 1.9.1，时限4s，内存限制1024MB（给C++14 2s/512MB），而且给你双核CPU。

• Codeforces使用单核的Go1.5.2，时限和内存限制和其他语言没有不同。

• LeetCode支持Go1.7.1，在时限、内存限制上也没有特殊待遇，单核，不能再多了。

• TopCoder仅支持C++，Java和C#，没有Go。

• Google Code Jam只要你的运行时间不超过4min。并行性完全取决于你的系统或运行程序的集群??（对不起没打过GCJ，不知道这里在说啥）。

• CodeChef卡在了Go1.4，还是没有特别照顾，还是单核。

• Timus卡在了更老的版本Go1.3，很难过。哪儿哪儿都很难过。

• ICPC不样用Go，拜拜

现在你知道了，大多数oj都不提供多核judge，所以Go的并发优势也就派不上什么用场。也就HackerRank会给你两倍内存两倍时间还有两个内核，理论上讲你可以在HackerRank使用4倍于C++的可伸缩转换（例如MapReduce），你不太可能会做出这种事，就是告诉你一声。

输入输出

标准库的fmt包没有使用缓冲区（那就慢），所以考虑到代码的运行效率，我们应当避免直接使用fmt包。而使用bufio包再封装出两个好用的输入输出函数，就一点毛病没有了：

        package main

import (
  "bufio"
  "fmt"
)

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{}) { fmt.Fscanf(reader, f, a...) }

func main() {
  // STDOUT MUST BE FLUSHED MANUALLY!!!
  defer writer.Flush()

  var a, b int
  scanf("%d %d\n", &a, &b)
  printf("%d\n", a+b)
}

    

把这个加到你的模版里，你就拥有了具备缓冲流的强力输入输出函数。（有人要用Go语言写模版吗，会用得上吗）

Strings, bytes, strconv, regexp

注意Go中的字符串是不可写的（写操作要比C++慢得多），所以在进行所有修改操作时尽量使用[]byte。标准库实现了一系列包（strings，bytes，regexp等）和一系列常用函数（map，contains，prefix，suffix，repeat，split，trim，index，等等）。还有一个strconv包，用来处理各种关于数字的解析和格式化。

除此之外，Go还自带后缀数组，支持正则表达式。

这是我用Go写的Codeforces 208A - Dupstep的AC代码（省略了部分模版代码）：

        import (
  "regexp"
  "strings"
)

func main() {
  defer writer.Flush()

  var s string
  scanf("%s\n", &s)
  s = regexp.MustCompile("(WUB)+").ReplaceAllLiteralString(s, " ")
  s = strings.Trim(s, " ")
  printf("%s\n", s)
}

    

这份代码跑了60ms，别人的C++14平均跑了30-60ms，用的内存还比我少。

排序和二分查找

sort包提供了特定类型的排序函数。排序函数有Sort()和Stable()，二分查找函数有Search()。还有一些好用的函数，像Ints()，Float64s和SearchInts()，仅适用于几个常见类型（int，float64和string）。对于其他类型，就必须使用通用Sort()并接受一个sort.Interface的副本。这很麻烦，但是在主流oj上线带有新版排序API的Go1.8前，我们只能受着。

下面是你要给一个int+float64的pair排序时要做的事情：

        type pair struct {
  x int
  y float64
}

type pairs []pair                  /**/
func (a pairs) Len() int           { return len(a) }
func (a pairs) Less(i, j int) bool { return a[i].x < a[j].x || a[i].y < a[j].y }
func (a pairs) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
  defer writer.Flush()

  items := pairs{{4, 74.0}, {9, 34.56}, {9, 31.31}}
  sort.Sort(sort.Reverse(items))

  for _, item := range items {
    printf("(%d, %.2f)\n", item.x, item.y)
  }

  // (9, 34.56)
  // (9, 31.31)
  // (4, 74.00)
}

    

一想起Go没有泛型和多态，我就难过……??????但哭也没用，只能忍着。

数学，大数，随机

math包提供了一大堆很nice的数学函数和常量，包括一些疯狂的东西比如Expml(x float64) float64能计算e^x-1，在接近0的部分，它比Exp(x) - 1更精确。math包里一共有62个函数、11个数学常量，这里就不多说了。需要的话，就自己看去吧。

math/big包包含了任意精度的类型和函数。我听说它非常快，但我在比赛中还没用遇到过真正使用它的机会。建议你好好看看这块，万一用得上呢。

math/rand包实现了伪随机数生成器，并提供了一系列用于种子和生成的函数。注意根据输入数据，给RNG选择用时间值或哈希值作为随机种子。

总结

如你所见，程序设计竞赛基本上还是C++和Java的地盘，毕竟C++和Java在现在的题目上表现异常地好，还提供强大的通用模板库。Go是不可能做到这一点的。现在我只会在比较大的字符串处理问题上使用Go，因为在这方面C++功能不太够用，Python又太慢了，再有就是涉及到高精度运算的时候，我也会用Go。

程序设计竞赛圈接下来会如何发展，让我们拭目以待。希望我们可以看到更多可以通过并发和并行高效解决的问题，那将是Go的专属领域。

评论区

Patrica Millie

Great stuff ???? ?? I use InterviewBit Link to practice coding interview problems. InterviewBit offers GO 1.8.

ragini ragini

Your good knowledge and kindness in playing with all the pieces were very useful. I don’t know what I would have done if I had not encountered such a step like this.
http://www.besanttechnologies.in/dot-net-training-in-bangalore.html

Theofanis Despoudis

You can optimize the code a bit further:

• defer occurs a fixed performance penalty so you could explicitly flush the writers.
• Regex package is convenient but slow. Consider parsing the strings manually.
• Take a look at this article: https://blog.golang.org/profiling-go-programs as pprof can help you profile the code.

原文：https://www.cnblogs.com/zhuaiballl/p/15010899.html