🐎

【小ネタ】Go言語でのchmin実装

2021/10/20に公開

この記事の内容は古いです!

Go1.18から導入されたGenericsによりもっとシンプルな解放が登場しました!

この記事は何

  • 競技プログラミングでよく使う、逐次最小値探索のためのテンプレート関数、通称chminのGo言語による実装です。
  • C++のテンプレート関数がこの時ばかりは羨ましくなりつつ、意地でもGo言語でやりきってみた
  • なお筆者は競技プログラミング初心者of初心者なので誤りがあったらすいません

waht is chmin?

  • 現在記憶している値と比較して、新しい値の方が小さければ記憶を更新する関数
  • 動的計画法(DP)問題で頻出
  • dp := make([]int, N)みたいな配列に対し、dp[i]の値候補が複数あるので、最小のものを選んでdp[i]に納め、それを0, 1, ... , N-1と進めていくようなイメージ

C++での実装例

  • はじめて知ったのですがテンプレート関数というものがあるのですね。大変素晴らしいと思います。
  • 下記の実装によってintだろうがfloat32だろうが引数として取ることができるそうです
template<class T> void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}

Goでの実装

  • 引数としてはなんでもOKにするためinterface{}を使う
  • 片方はポインタで渡す必要がある ← 個人的にこの処置に躓きました
    • 下記のコードに対して、最初はfunc Chmin(p *interface{}, v interface{})としたくなってしまったのですが、interface{}のポインタを寄越せゴルァと怒られます。
func Chmin(p interface{}, v interface{}) {
	switch v.(type) {
	case int:
		a, ok := p.(*int)
		if !ok {
			return
		}
		if vv := v.(int); *a > vv {
			*a = vv
		}
	case float32:
		a, ok := p.(*float32)
		if !ok {
			return
		}
		if vv := v.(float32); *a > vv {
			*a = vv
		}
	case float64:
		a, ok := p.(*float64)
		if !ok {
			return
		}
		if vv := v.(float64); *a > vv {
			*a = vv
		}
	}
}

おわりに

  • なんというコード量の差…。もっと良い解がありそうなものですが、まずはこれを使い倒してみます。
GitHubで編集を提案

Discussion