Top / scala 99problem 32~
S-99 Ninety Nine Scala Problems
http://aperiodic.net/phil/scala/s-99/
S-99 Ninety Nine Scala Problemsの1~31問まではこちら
ユークリッドのアルゴリズムを使っているそうだ。
1071 を 1029 で割った余りは 42 1029 を 42 で割った余りは 21 42 を 21 で割った余りは 0 よって、最大公約数は21である。
入力を m, n (m ≧ n) とする。 n = 0 なら、 m を出力してアルゴリズムを終了する。 n が m を割り切るなら、 n を出力してアルゴリズムを終了する。 m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 3. に戻る。
回答はこんな感じだ。
object S99Int { def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(n, m % n) }
久しぶりにみたから、目が慣れていない。
GCDって英語圏の最大公約数greatest common divisorの略だからね。
サイトには、
gcd(36,63)
ってだけ書いてあるけど、実際には
S99Int.gcd(36,63)
だからね。
でも、これって、どういうときつかうんだろ。
「あー今日は、最大公約数でも求めたいなぁ」っていうときかな?
そんなことってないよね。
互いに素かどうかを返す問題だ。
どうでもいいんだけど、互いに素っていう表現は3つあるって知ってた?
relatively prime/disjoint/coprime
primeは素って出てくれば、よさそうなんだけど。覚えにくい。プライムってサブプライムローンのプライムなのかな?
しらべてみたら、サブプライムローンのプライムであってるじゃん。
primeのpriは、「主要な」っていう意味。じゃあmeは?自分?主要な自分だっていっていると、互いに素になっちゃうね。っておぼえときゃいいのかな?
話を戻して、これは問32をつかって解くと簡単なんだ。でも、ここの回答のチェックポイントは
クラスのコンストラクターの書き方に注目したい。
object S99Int { def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(n, m % n) } class S99Int(val start: Int) { def isCoprimeTo(n: Int): Boolean = S99Int.gcd(start, n) == 1 }
ウェブでの回答はS99Int.gcdのところが単にgcdって書いてあるだけなんだけどね。
確かめる方法はこんな具合
scala> var a = new S99Int(35); a: S99Int = S99Int@1a422d9 scala> a.isCoprimeTo(64) res3: Boolean = true
一行で書くとこんなかんじかな
scala> new S99Int(35).isCoprimeTo(64) res4: Boolean = true
オイラーのファイ関数
totientって、英次郎でしらべたら、
《数学》その数以下{すう いか}でその数と互いに素な数の個数
で、それ以外の意味ってないんだね。これって、絶対に日常使わないから、英語圏の人でも、数学詳しくない人て、普通だとおもうから、きっとみんなしらないだろうね。
「toti」って全体のっていう意味でよく使われているらしいね。Javaやっていると、このような単純んな名前付けは、名前空間で重複するからだめだとか、ほかの人が読んでも意味を連想しにくいとかで、とかく誤解がなければすべてよし、みたいな感じで、ながったらしい名前をかくんだよね。
まあ、オイラーさんに文句はいえないわけだけど。
最大公約数を求める問題なんだけど、回答しているプログラムがうまく通らなかった。
primesが定義されていないからだ。
回答されているプログラムをみる限りprimesにはStream形の配列に素数リストを定義したものを代入すれば、動くようなつくりになっている。
だから、どうっていうことでもないんだけどね。
Streamは要素が必要になったときに作成されるList(みたいなモノ)です。
要素は必要になったときに初めて作成されるので、
模範解答例には2つの解き方が書いてあるが、あえて難しいほうの回答を読解してみる。
def factorCount(n: Int, p: Int): (Int,Int) = if (n % p != 0) (0, n) else factorCount(n / p, p) match { case (c, d) => (c + 1, d) }
else と match の組み合わせがどのように計算されるのか、イメージがわかない。
=> がScalaのクロージャだってことも、最初のころはわからないので、つぎのようには勘違いしない。
case クロージャ
てなってるって、どーゆうことよって思うわけさ。
match { case っていう組み合わせはパターンだ、でもこれって、
クロージャの構文と類似していて、意味合いも、ほぼそんな感じなんだよ。
scala のif はjavaのifと違って、かならず値を返すことになっている。
自分でまとめるよりも、はるかにわかりやすくまとめている人がいるのを発見したので、リンクしておきます。
かなりまとまっているところへリンク
http://sites.google.com/site/scalamemo/kihon-1/matchingu
ややまとまっているところへのリンク
http://d.hatena.ne.jp/taktamur/20091115/1258292009
だいたいまとめると、
val ret = x match{ case "a" => "Alpha"; case "b" => "Beta"; case _ => "unknown"; }
def generalSize(x:Any) = x match{ case s:String => s.length; case m:Map[_,_] => m.size; case _ => -1; }
問36の答えをつかって、もっと簡潔に問34の問題をとこうという趣旨だとおもうが、ここでは、ふたたび foldLeftの使い方の復習をしてみたいと思う。一度、この99問題の例題にとりあげたのだが、すっかりわすれてしまっている。
class S99Int(val start: Int) { def totient: Int = start.primeFactorMultiplicity.foldLeft(1) { (r, f) => f match { case (p, m) => r * (p - 1) * Math.pow(p, m - 1).toInt } } }
おさらいすると、foldLeftの引数は、初期値である。で、括弧の中身は、無名関数でありますな。 無名関数の最初の(r,f)は引数で、まずは左側の引数に初期値の1が入る。で、配列の要素数分ループしますが、その際に、初期値が入っていた変数に、評価したものが格納されるしくみになっています。
今回の例ではmatchの中に、無名関数があります。引数がp,mなのでrがpになって、fがmになるってことでいいのかな?
http://d.hatena.ne.jp/taktamur/20091114/1258210136
回答をみると、これは実行時間計測サンプルとして使えますな。
処理内容自体を引数として渡しているところが、Scalaっぽい書き方です。
def time[A](label: String)(block: => A): A = { val now = System.currentTimeMillis() val ret = block println(label + ": " + (System.currentTimeMillis() - now) + " ms.") ret }
引数の型はJavaの”クラス 変数名”という書き方ではなく"変数名: クラス"という活気型でブロックの時はクラス名がないからなのか "=> 適当な変数名 "と書くのかもしれません。
で、=>ってなんだっけ?
time("P34 (" + n + ")") { n.totientP34 }
ブロックは、変数としては渡しておらず、引数とは別に右隣に{ }で括った箇所が渡せるようになっています。
久しぶりにtakeWhileがでてきて使い方を復習してみる
まずは、処理対象のリストを用意しておきましてと、
scala> val list = List(1,2,3,4,5) list: List[Int] = List(1, 2, 3, 4, 5)
こんな風に書くと、条件を満たす要素を返す処理かと思いますよね?
scala> list.takeWhile( _ < 4) res18: List[Int] = List(1, 2, 3)
でも違うんです。条件を満たさないとそれ以降の要素を無視するメソッドなんですよ。
scala> list.takeWhile( _ > 3 ) res19: List[Int] = List()
たぶん次の結果を想定してしまいますが、
List(1, 2, 3)
これは、要素の最初が1だから 1>3 となって、条件を満たさないので、 それ以降の要素を無視するようになっています。
下記の模範回答のコードの一部にtimeだとか、forceとか使われている。
time("Preload primes") { primes takeWhile { _ <= Math.sqrt(n) } force }
timeって、よくわかんないなぁ。繰り返し実行しそうなイメージだけど、どうやってしらべんのかな?
APIにでもかいてあんのかな?とか思って、scala api でググってみた。
http://www.scala-lang.org/api/current/index.html
をみてみたら、検索テキストボックスがあったから、そこにtimeっていれてみたんだけど、TIMEOUTとか関係のないものしかでてこなかったなぁ。
forceについては、まったく何もでてきやしない。
Scala6階:型
http://www.h7.dion.ne.jp/~samwyn/Scala/type.htm
にて
Iterableの遅延相当型。 def force: Iterable[A]
Arrayを結果するforceのみを強制。 abstract def force: Array[A]
と書いてあった。
なんのことやらである。強制的に宣言するのであろうか?
もう一つあったので、書いておく
http://www.kmonos.net/wlog/69.html
にて下記コードが書いてあり
class List { int head lazy List tail; List( int h, lazy List t ) { head=h; tail=t; } static lazy List intsFrom(int n) { return new List(n, intsFrom(n+1)); } } int n = intsFrom(1).tail.tail.head; // 3
次のような解説が記載されていました。
lazyでない型が必要な文脈でlazyな型の値が現れていたら、 そこでforceする
(例えば ***.tail の *** には 非lazyなListが来るべきなので、そこにlazy Listが来てたらそれをforce)。
逆なら逆にdelayする。それだけ。 ちょっと面白いなあと思ったのは、lazy List を返すメソッドを定義すると、 それはreturnの式だけではなくて、 メソッド全体をdelayするという意味にとるらしいこと。
確かにそれは便利かも。 実装は明示的にサンクを操作するJavaのコードに変換するようです。 Javaを拡張しましたという話を見るたびに Polyglot の名前を見るので一度さわってみようと 思いつつ早幾年。 誰か「3分でわかるPolyglot」とか書くとよいよ!
えーと、自分の理解力では、1%ぐらいしか理解できんなぁ。
何が1%かというと、それは、forceとは遅延評価に関係した単語であるということぐらいだ。
そこで今度は "Scala force 遅延評価"でググってみた。
そうすると、概念的な記事がwikiに掲載されていました。
http://ja.wikipedia.org/wiki/%e9%81%85%e5%bb%b6%e8%a9%95%e4%be%a1
この概念と単語をしらないといけなかったのだね。つまり、この概念が日常的な概念だと勘違いしている人は、
そのまま、前置きの説明もなく、forceがどうのこうのと書いて説明した気になっているってことなんだね。
説明はみつけられなかったが、遅延評価部分を、「ここで評価します」というメソッドがforceってことにしておこうとおもいます。
解答にあるprimesはどこにも定義されていないようだ。 この解答を理解するには次のことを理解するひつようがある。
object S99Int { def listPrimesinRange(r: Range): List[Int] = primes dropWhile { _ < r.first } takeWhile { _ <= r.last } toList }
配列変数の後ろにスペースをおいて dropWhileと書くのがscala流のようだ。
配列へInt型の数値を格納する例
val primes = Array(1,2,3,5,7,11,13)
実行するには下記のように入力する
S99Int.listPrimesinRange(2 to 7)
結果
List[Int] = List(2, 3, 5, 7)
次のコードを実験してみた
primes dropWhile { _ < 3 }
結果
Array[Int] = Array(3, 5, 7, 11, 13)
Array(3, 5, 7, 11, 13) toList
結果
List[Int] = List(3, 5, 7, 11, 13)
scalaは配列を主語にしてスペース動詞という感じでプログラムが書けるようになっているようだ。