回文数かどうかを判定したい。

---

　書き終わって気が付いたのですが、"palindoromic"ではなくて"palindromic"ですね。文章はおろかソースコードまですべて間違ったつづりになっています……。機会があれば修正します。すみません(´・ω・`)

---

　とりわけProject Eulerを解いていると頻繁に要求されるのが回文数。「ある数字が回文数かどうか」を判定する関数をあまりにしょっちゅう使うのでライブラリ化したいのですが、その前にどのような判定方法が効率的なのか簡単に計測してみました。

　とりあえず思いついたのは3通り。ひとつめは文字列を反転させるのは容易なので、数字を1度文字列に変換してから比較する方法(palidoromic1?)。つづくpalindoromic2?はアルゴリズムを工夫することにより数字を数字のまま反転し、それを利用する方法。最後にpalidoromic3?は数字を桁ごとに区切ったリストに変換し。これを反転します。

(use srfi-1)
(use srfi-13)

; ; == 準備 ==
; 0以上の整数を反転させます
; (number-reverse 123) => 321
; (number-reverse 100) => 1
(define (number-reverse number)
    (let loop ((i number) (res 0))
        (if (<= i 0)
            res
            (loop (quotient i 10) (+ (* res 10) (modulo i 10))))))

; 0以上の整数をけたごとに区切ってリストに格納します
; (number->list 123) => '(1 2 3)
; (number->list 100) => '(1 0 0)
(define (number->list number)
    (let loop ((i number) (ls '()))
        (if (<= i 0)
            ls
            (loop (quotient i 10) (cons (modulo i 10) ls)))))
; == 準備ここまで ==

; palindoromic1/2/3はすべて0以上の整数が回文数なら#t、そうでない場合は#fを返す
; 数字を一度文字列に変換してから、回文数かどうかを判定します
(define (palindoromic1? number)
    (string= (number->string number)
             (string-reverse (number->string number))))

; 数字を数字のまま反転させて、回文数かどうかを判定します
(define (palindoromic2? number)
    (= number (number-reverse number)))

; 数字をリストに変換して、回文数かどうかを判定します
(define (palindoromic3? number)
    (let loop ((ls1 (number->list number)) (ls2 (reverse (number->list number))))
        (if (and (null? ls1) (null? ls2))
            #t
            (if (= (car ls1) (car ls2))
                (loop (cdr ls1) (cdr ls2))
                #f))))

　それほど難しいことではありませんね。なおここには示しませんが、一応簡単なテストは行ってpalindoromic系関数はすべて正常に動いていることを確認しています。たぶんこれで大丈夫なはず。

　それでは計測。例にもれずgaucheのtime関数を利用しています。

; == 計測開始 ==

(use srfi-27)

; upper個の乱数(1..upperの整数)を格納したリスト
(define randoms
    (let ((upper 100000))
        (let loop ((c 0) (ls '()))
            (if (> c upper)
                ls
                (loop (+ c 1) (cons (random-integer upper) ls))))))

(time (map palindoromic1? randoms))
(time (map palindoromic2? randoms))
(time (map palindoromic3? randoms))

; == 結果発表 ==

;(time (map palindoromic1? randoms))
; real   1.531
; user   1.390
; sys    0.703
;(time (map palindoromic2? randoms))
; real   0.062
; user   0.062
; sys    0.000
;(time (map palindoromic3? randoms))
; real   0.156
; user   0.219
; sys    0.000

　ということで優勝はpalindoromic2?、すなわちアルゴリズム的工夫により数字を数字のまま反転させる方法になりました。ぱちぱちぱち。結果が見えてたとは言わないお約束。なおこののち数度繰り返してみたものの、palindoromic2?がずば抜けて早く、次点がpalindoromic3?(リスト)、そしてpalindoromic1?(文字列)が圧倒的に遅いという結果は変わりませんでした。

　palindoromic1?の敗因はやはり型変換がよろしくないというところでしょう。その点palidoromic3?は型変換を行わないのですが、リストを生成するのでそこが非効率だったと思われます。アルゴリズムとメモリ効率の大切さを改めて認識する結果でした(´・ω・`)。