Goで回文判定

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

ソースコード: github.com/ebiiim/palindrome

文字列の場合

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

 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
}

数値の場合

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

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

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

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

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

ループ見る桁計算結果
初期状態1234500000
11234550000
21234554000
31234554300
41234554320
51234554321
 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
375 ns80 ns
499 ns82 ns
19586 ns222 ns

考察

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

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