囲碁で2つの整数の間の最小値を求める正しい方法は何ですか？

質問

プログラムでmathライブラリをインポートし、以下のような方法で3つの数値の最小値を求めようとしています。

v1[j+1] = math.Min(v1[j]+1, math.Min(v0[j+1]+1, v0[j]+cost))

というようにv1が宣言されているところ。

t := "stackoverflow"
v1 := make([]int, len(t)+1)

しかし、プログラムを実行すると、次のようなエラーが発生します。

./levenshtein_distance.go:36: cannot use int(v0[j + 1] + 1) (type int) as type float64 in argument to math.Min

と書く別のプログラムがあるので、おかしいと思ったのです。

fmt.Println(math.Min(2,3))

であり、そのプログラムの出力は 2 を文句を言わずに出力します。

というわけで、結局は値を float64 としてキャストすることにしました。 math.Min が動作するようにしました。

v1[j+1] = math.Min(float64(v1[j]+1), math.Min(float64(v0[j+1]+1), float64(v0[j]+cost)))

このやり方だと、以下のようなエラーが出ました。

./levenshtein_distance.go:36: cannot use math.Min(int(v1[j] + 1), math.Min(int(v0[j + 1] + 1), int(v0[j] + cost))) (type float64) as type int in assignment

というわけで、この問題を解消するために、結果をキャストして int

これは非常に非効率で読みにくいと思いました。

v1[j+1] = int(math.Min(float64(v1[j]+1), math.Min(float64(v0[j+1]+1), float64(v0[j]+cost))))

また、小さな minInt 関数も書きましたが、これは不要だと思います。なぜなら、他のプログラムで math.Min を使う他のプログラムは整数を取るときにうまく動作するので、これは私のプログラムの問題であって、ライブラリ自体の問題ではないと結論づけました。

何かひどく間違ったことをしているのでしょうか？

上記の問題、特に36行目を再現するためのプログラムを以下に示します。 パッケージ main

import (
    "math"
)

func main() {
    LevenshteinDistance("stackoverflow", "stackexchange")
}

func LevenshteinDistance(s string, t string) int {
    if s == t {
        return 0
    }
    if len(s) == 0 {
        return len(t)
    }
    if len(t) == 0 {
        return len(s)
    }

    v0 := make([]int, len(t)+1)
    v1 := make([]int, len(t)+1)

    for i := 0; i < len(v0); i++ {
        v0[i] = i
    }

    for i := 0; i < len(s); i++ {
        v1[0] = i + 1
        for j := 0; j < len(t); j++ {
            cost := 0
            if s[i] != t[j] {
                cost = 1
            }
            v1[j+1] = int(math.Min(float64(v1[j]+1), math.Min(float64(v0[j+1]+1), float64(v0[j]+cost))))
        }

        for j := 0; j < len(v0); j++ {
            v0[j] = v1[j]
        }
    }
    return v1[len(t)]
}

どのように解決するのですか？

いや、そういう書き方でいいと思うんですよ、例えば。 はstdlibのsort.goが はファイルの先頭付近でそれを行います。

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

math.Min(2, 3) が動作するようになったのは の数値定数は型付けされていないためです。 . しかし、float64 を一般的な数値型として扱うことには注意が必要です、なぜなら の上の整数は 2^53 は float64 に変換されると丸められます。 .

しかし は安定した Go では動作しませんが には、これを書いている時点では Go 1.18 ベータ を書くことができます。 ジェネリック min 機能 であり、ハンドコーディングされた単一型バージョンと同じように実行時に効率的です。

これまでにも 議論 を更新して既存の関数のジェネリックバージョンを追加するという議論がありましたが、もしそうなったとしても、それは後のバージョンになるまでないでしょう。