JavaScript: クロージャーでメモ化してくれる関数を作ってみたという記事を以前書きました。
前記事のまとめ : 漸化式でかけるような数列は、汎用のメモ化関数でメモ化できる。
例えば：
//フィボナッチ数列
const fibo = n =>
(n === 0)? 0
: (n === 1)? 1
: fibo(n-1) + fibo(n-2)
//階乗
const facto = n =>
(n === 0)? 1
: (n === 1)? 1
: n * facto(n-1)
は、汎用のメモ化関数 memoizer を使って：
//フィボナッチ数列
const fibo = memoizer( [0,1] )( a => n => a(n-1) + a(n-2) )
//階乗
const facto = memoizer( [1,1] )( a => n => n * a(n-1) )
とすると、計算した値をメモ化することで高速で計算できる、ということでした。
速くなるし、 初期値と漸化式っぽい関数を書けばいいだけだし、いいことずくめ。
でも...ぶっちゃけそんなに使わなくね?
わあ、めっちゃ便利!
と当時は思ったのですが、 んじゃあそれから今まで、業務や個人的にでも使ったか?といわれると、全然使ってません。
考えるに理由はふたつ。
- メモ化が必要なケースになかなか出会わない
- 単純な漸化式で表わされるような数式ってなかなか思いつかない
1はまあしょうがないとして、2のほうはもうちょっと何とかならないかなあ、と思ったわけです。
数学とか得意な人は使いまくれるのでしょうが、漸化式といっても知ってるのはここにあるフィボナッチと階乗くらいで、あと何にも思いつかない...
漸化式で表わせないときは、便利な汎用のmemoizer を使うのをあきらめて個別にメモ化関数を書いていたんだけど、気がついたら同じようなことをしてるし、
あれ? これって思いこみ?
漸化式でなくてもよくね?
というのが、この記事の主旨です。今のところ予想です。
でも考えてみれば、漸化式っぽい数列の関数を定義するのに数列 a とインデックス n を引数として渡しているので、 それで、a(n-1)にもアクセスできるし、ということは a(0)やa(1)にだってアクセスできるわけで、漸化式に囚われる必要もないわけです。
例えば 素数列。
面倒そうで漸化式で表わせなさそうなのということで選びました。
漸化式では表わせないようですが、今まで求めた数列から次の値が計算できる、と考えれば望みはありそうです。
できあがったやつはそれなりに実用になったほうがいいので：
- 素数かどうかの調べ方 ： 試し割り
- あらかじめ2と3の倍数を除いた素数候補から
- その数の平方根以下の素数で割って試す
ということでやってみます。
こんな風にしたい：
// 素数列の初期数列。とりあえず最初のみっつだけ。
const primeInits = [2, 3, 5]
// 漸化式っぽいもの。
// 素数列 a の n 番目の素数は、
// n-1 番目の素数 から作られる素数候補 を順に試して、
// 試し割りで最初に割り切れなかったやつ、という意味。
const primeRule = a => n => {
for (const potentialPrime of potentialPrimeG( a(n - 1) ) ) {
if ( passedTrialDivision( a )( potentialPrime ) ) return potentialPrime
}
}
// 素数のメモ化関数を作る
// primeAt(n)で 素数列の n 番目の素数を返します。
const primeAt = memoizer( primeInits )( primeRule )
こんな風になればいいなと。今のところ希望です。
以下で、未定義の、まだふわっとしているところをちゃんと詰めていきます。
素数候補を返すジェネレータ
引数の 素数 aPrime より大きくて、2の倍数でも3の倍数でもないものが素数候補です。
const potentialPrimeG = aPrime => function*(){
let m = Math.ceil( aPrime / 6 ) * 6
if ( aPrime === m - 5 ) yield m - 1
while (true) {
yield m + 1
yield m + 5
m = m + 6
}
}()
試し割りで割り切れない(=素数)かどうかを返す関数
引数に素数列 a と 素数候補 potentialPrime をとって、potentialPrimeの平方根以下の a の要素で試し割りして、割り切れちゃったら偽、割り切れなかったら真を返します。
const passedTrialDivision = a => potentialPrime => {
const end = Math.sqrt( potentialPrime )
for (let i = 0; a(i) <= end; i++){
if (potentialPrime % a(i) === 0) return false
}
return true
}
さあこれで実装は終ったはずです。ちゃんと動くかな?
使ってみる
とりあえず、30個の素数列を求めてみました。
[...Array(30).keys()].map(primeAt)
/*
[
2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113
]
*/
ちゃんと動いているようです。やった!
ということでこの例から言えること...
今回のまとめ
漸化式で表わせない、表わしにくいものでも、前に求めた数列の値から次の値が求められるのなら、汎用のメモ化関数でのメモ化はできそうです。
今回使ったコードです。まとめて。
// 汎用のメモ化関数
const memoizer = inits => rule =>{
const memo = [...inits]
const a = n => {
if(n >= memo.length) {
for(let i = memo.length; i <= n; i++) {
memo[i] = rule( a )( i )
}
}
return memo[n]
}
return a
}
// memoizer を特化して、素数列のメモ化関数を作る
const primeInits = [2, 3, 5]
const primeRule = a => n => {
for (const potentialPrime of potentialPrimeG( a(n - 1) ) ) {
if ( passedTrialDivision( a )( potentialPrime ) ) return potentialPrime
}
}
const primeAt = memoizer( primeInits )( primeRule )
// 素数列のメモ化関数のための補助的な関数
const potentialPrimeG = aPrime => function*(){
let m = Math.ceil( aPrime / 6 ) * 6
if ( aPrime === m - 5 ) yield m - 1
while (true) {
yield m + 1
yield m + 5
m = m + 6
}
}()
const passedTrialDivision = a => potentialPrime => {
const end = Math.sqrt( potentialPrime )
for (let i = 0; a(i) <= end; i++){
if (potentialPrime % a(i) === 0) return false
}
return true
}
// 使ってみる
[...Array(30).keys()].map(primeAt)