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

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

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
		}
	}
}

おわりに

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