学習を兼ねて書きました。
- 準備
計測には、下記記事のBenchmarkクラスをそのまま使います。
Swiftで重い処理の処理時間を測定する - Qiita
extension Array {
func reject(excludeElement: (T) -> Bool) -> [T] {
return filter { !excludeElement($0) }
}
}
- 実装
prime1
func prime1(n: Int) -> [Int] {
var ns = Array(2...n)
let upper = Int(sqrt(Double(n))) // maxの平方根
return reduce((2...upper), ns) { (r: [Int], n: Int) -> [Int] in
return r.reject {
($0 % n == 0) && $0 > n
}
}
}
prime1計測
Benchmark.measure("prime1") {
prime1(200) // 0.971(s)
}
Swiftでも副作用を排除する関数型のアプローチで書ける！
只、prime1の実装だとUshio@githubさんがご指摘をしてくださった通り、問題点があります。
- 4（2の時点で落とされていたはずのもの）が計算されている
- 剰余が発生している
そこで、素直に副作用を許容して書いたのが下記です。
prime2
func prime2(n: Int) -> [Int] {
var ns = Array(2...n)
let upper = Int(sqrt(Double(n)))
for i in 2...upper {
let index = i - 2
if ns[index] != 0 {
for var j = index + i; j < ns.count; j += i {
ns[j] = 0
}
}
}
return ns.filter { x in x != 0 }
}
prime2計測
Benchmark.measure("prime2") {
prime2(200) // 0.190(s)
}
ベンチマークを取ってみると、prime1に比べてprime2の方が5倍近く早くなってますね!
まとめ
アルゴリズムの特性や性質を理解して、
素直に手続き型のアプローチで書いた方が可読性も高いし、速度も出るのなら
そちらを使うべしだし、適材適所だなと感じました。