Project Euler の Problem 4 をやってみたら (その2)アルゴリズム編


問題の詳細は[(その1)](http://qiita.com/ki073/items/bbb253d3a398557391e2)をごらんください。

1. xとyは入れ替えが可能なのでx<=yの範囲だけを調べる。
2. 回文になっている数値が見つかれば、それ以降より大きな値しか回文であるか調べない。
3. xとyは大きな値から調べていく。
というアルゴリズムにしています。

### Ruby

```ruby:problem4_1.rb
n=0
9999.step(1000,-1).each do |x|
	f=9999.step(x,-1).lazy.map{|y| x*y}.take_while{|xy| xy>n}.find{|xy| s=xy.to_s; s==s.reverse}
	n=f if f
end
puts n
```

遅延処理lazyの追加で 0m2.514s -> 0m0.134s とかなり速くなりました。
RubyのLazyはあまり速くないのですが、それなりの効果があるようです。

Python3は遅延処理がかなり取り入れられているので、Rubyよりは速そうな気が。

###Haskell

```haskel:problem4_1.hs
import Data.List

largest_palindrome :: Int -> Int -> Int
largest_palindrome x n
    | x<1000 = n
largest_palindrome x n = 
    case max_palindrome of
    Just a -> largest_palindrome (x-1) a
    Nothing ->  largest_palindrome (x-1) n
    where max_palindrome = find is_palindrome $ takeWhile (>n) [x*y| y <- [9999, 9998..x]] -- xとの掛け算で得られる回文の最大値
          is_palindrome :: Int -> Bool -- 回文判定
          is_palindrome num = let s = show num in s == reverse s

main = print $ largest_palindrome 9999 0
```

遅延処理が洗練されているコンパイラは速い。
0m0.002s　でした。

##追記(2017.6.17)
みなさんコメントありがとうざいました。コメントを元に整理しました。書き換えてをおりますので、コメントとは若干ずれているところもありますのがご了承ください。

最終的なアルゴリズムは以下の通りです。
1. xとyは入れ替えが可能なのでx<=yの範囲だけを調べる。
2. x,y共に大きい方から調べていく。
3. あるxで回文になっている数値が見つかれば、x*yをnとして記録してそれより小さなyは調べない
4. それ以降x*yがnより大きな範囲だけを調べる
5. x*(yの範囲の最小値)<=nであればそれ以降nより大きな回文数がないので、その時点で打切る。

```ruby:problem4_2.rb
problem4_2.rb
n=nil
9999.step(1000,-1).map{|x|
    break if n and x*9999<n
    f=9999.step(x,-1).lazy.map{|y| x*y}.take_while{|xy| !n or xy>n}.find{|xy| s=xy.to_s; s==s.reverse}
    n=f if f
}
puts n
```
処理時間は0m0.055sに大幅に速くなりました。

###処理時間測定
以下は処理時間を長くするために、7桁にしています。

内側のループに遅延処理(lazy)あり

```ruby:problem4_3.rb
n=nil
9999999.downto(1000000).each{|x|
    next if x % 10 ==0
    break if n and x*9999999<n
    f=9999999.downto(x).lazy.map{|y| x*y}.take_while{|xy| !n or xy>n}.find{|xy| s=xy.to_s; s==s.reverse}
    n=f if f
}
puts n
```

単純に内側のループのlazyを取り除いたもの

```ruby:problem4_4.rb
n=nil
9999999.downto(1000000).each{|x|
    next if x % 10 ==0
    break if n and x*9999999<n
    f=9999999.downto(x).map{|y| x*y}.take_while{|xy| !n or xy>n}.find{|xy| s=xy.to_s; s==s.reverse}
    n=f if f
}
puts n
```

内側のループからbreakで抜けるようにしたもの

```ruby:problem4_5.rb
n=nil
9999999.downto(1000000).each{|x|
    next if x % 10 ==0
    break if n and x*9999999<n
    9999999.downto(x).each{|y|
        xy=x*y
        break unless !n or xy>n
        s=xy.to_s
        if s==s.reverse
            n=xy
            break
        end
    }
}
puts n
```

整理すると

|プログラム名|特徴|xy=x*yの回数|処理時間|
|:-:|:-:|:-:|:-:|
|problem4_4.rb|lazyあり|4,260,745|0m3.018s|
|problem4_5.rb|lazyなし,x*yの計算回数が多い|8,454,335|0m3.142s|
|problem4_6.rb|breakで抜ける|4,260,745|0m1.583s|

ということになりました。
problem4_4.rbとproblem4_6.rbは計算量が同じ適度ですが、2倍程度の差が出てしまいました。(kts_hさんの指摘の通りです)

### Rubyのlazyはどの程度遅いのか?

計算負荷を同じになるようにして比較してみました。4桁x4桁の回文の個数を単純に数えています。

```ruby:program1.rb
palindromes=9999.downto(1000).flat_map{|x|
    9999.downto(x).lazy.map{|y| x*y}.select{|xy| s=xy.to_s; s==s.reverse}.force
}
puts palindromes.size
```

```ruby:program2.rb
palindromes=9999.downto(1000).flat_map{|x|
    9999.downto(x).map{|y| x*y}.select{|xy| s=xy.to_s; s==s.reverse}
}
puts palindromes.size
```

```ruby:program3.rb
palindromes=[]
9999.downto(1000).each{|x|
    9999.downto(x).each{|y|
        xy=x*y
        s=xy.to_s
        palindromes << xy if s==s.reverse
    }
}
puts palindromes.size
```


|プログラム名|特徴|処理時間|
|:-:|:-:|:-:|
|program1.rb|lazyあり|0m17.807s|
|program2.rb|lazyなし|0m12.707s|
|program3.rb||0m11.006s|
このプログラムだと、内側のループでx*yと回文の判断しかなく、計算負荷は軽いのでlazyの有無がかなり影響しています。
多少計算量が増えてもlazyを取った方が速くなる可能性もあるようです。

使用装置
Scientific Linux 7.3  Core i7 2600 3.4 GHz
Haskell ghc 8.0.2 オプション -O
Ruby 2.4.1