Goで回文判定

競技プログラミングでよく現れる回文判定をGoで書きました。数値の場合は計算すると遅いので文字列に変換して比較しましょう。

文字列の場合

元の文字列と逆順に並べ替えた文字列を比較するだけですね。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func reverseStr(s string) string {
	r := []rune(s)
	n := len(r)
	for i := 0; i < n/2; i++ {
		r[i], r[n-1-i] = r[n-1-i], r[i]
	}
	return string(r)
}

func CheckStr(s string) bool {
	return reverseStr(s) == s
}

stringは読み取り専用のbyteのsliceなので、そのまま逆順にすると1バイト文字以外はおかしくなります。そのため、rune型に変換してから並べ替えます。

数値の場合

すぐに思いつく手法が2種類あります。結論から言うと手法2が速いです。

手法1 数値のまま回文判定
手法2 文字列に変換して回文判定

手法1 数値のまま回文判定

12345をイイ感じに計算して54321にするreverseInt関数を考えます。

12345を54321にするには、桁数を数えてから、次の表のように1桁ずつ計算していきます。

ループ	見る桁	計算結果
初期状態	12345	00000
1	12345	50000
2	12345	54000
3	12345	54300
4	12345	54320
5	12345	54321

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// `math.Pow`はfloat64で計算するので遅いです。
// intのみ考慮する`pow`関数を作成します。
func pow(a, b int) int {
	c := 1
	for i := 0; i < b; i++ {
		c *= a
	}
	return c
}

// 10, 100, 1000, ...で割って桁数を調べる。
func countDigit(n int) int {
	count := 1
	for {
		if n/pow(10, count) != 0 {
			count++
		} else {
			return count
		}
	}
}

// 前述の表のように並べ替えを行う。
func reverseInt(n int) int {
	digit := countDigit(n)
	x := 0
	for d := 0; d < digit; d++ {
		x += ((n / pow(10, d)) % 10) * (pow(10, digit-1-d))
	}
	return x
}

この関数の出力と元の数値を比較すれば、回文数かどうかがわかります。

1
2
3
func CheckInt1(n int) bool {
	return reverseInt(n) == n
}

手法2 文字列に変換して回文判定

strconv.Itoaを使うだけです。

1
2
3
4
func CheckInt2(n int) bool {
	s := strconv.Itoa(n)
	return reverseStr(s) == s
}

ベンチマーク

手法1は数値の比較なので速そうですが、変換のためにそこそこ計算しています。手法2は文字列に変換してから文字列比較を行います。なるほどわからん。計測します。

結果

桁数を変えながら計測したところ、4桁以上で手法2(文字列に変換して回文判定)が速いです。int64で一番長い19桁だと倍以上の差が出ました。

桁数	手法1	手法2
3	75 ns	80 ns
4	99 ns	82 ns
19	586 ns	222 ns

考察

一般的に長い桁数を扱うことが多いと思うので手法2でやりましょう。何も考えなくて良いのもアドです。

手法1は私のアルゴリズムがアレなのかもしれません。もっと良い計算方法があったら教えてください。