scala 99problem 32～の編集

[ トップ ] [ 編集 | 差分 | バックアップ | 添付 | リロード ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

[[SCALAの記事一覧]]

&topicpath;

*目次 [#h7fd4b7e]
#contents

*練習問題 S-99 Ninety Nine Scala Problems † [#q9fbf881]
S-99 Ninety Nine Scala Problems

http://aperiodic.net/phil/scala/s-99/

*問１～３１ [#y3bbd7cc]
S-99 Ninety Nine Scala Problemsの1～31問まではこちら

[[scala]]

*問32 [#d250c212]

ユークリッドのアルゴリズムを使っているそうだ。

*ユークリッドのアルゴリズムってなんだっけ [#q3a54de7]
**(例題) 1071 と 1029 の最大公約数を求める。 [#m5f0fe7d]

1071 を 1029 で割った余りは 42 
 1029 を 42 で割った余りは 21 
 42 を 21 で割った余りは 0 
 よって、最大公約数は21である。

**アルゴリズム [#b477dae8]
 入力を 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の略だからね。

**実行方法 [#zc6e1896]
サイトには、

gcd(36,63)

ってだけ書いてあるけど、実際には

S99Int.gcd(36,63)

だからね。

でも、これって、どういうときつかうんだろ。

「あー今日は、最大公約数でも求めたいなぁ」っていうときかな？

そんなことってないよね。

*問33 [#mceb6639]
互いに素かどうかを返す問題だ。

どうでもいいんだけど、互いに素っていう表現は３つあるって知ってた？

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

*問34 [#r9d67974]
オイラーのファイ関数

totientって、英次郎でしらべたら、

《数学》その数以下｛すう いか｝でその数と互いに素な数の個数

で、それ以外の意味ってないんだね。これって、絶対に日常使わないから、英語圏の人でも、数学詳しくない人て、普通だとおもうから、きっとみんなしらないだろうね。

「toti」って全体のっていう意味でよく使われているらしいね。Javaやっていると、このような単純んな名前付けは、名前空間で重複するからだめだとか、ほかの人が読んでも意味を連想しにくいとかで、とかく誤解がなければすべてよし、みたいな感じで、ながったらしい名前をかくんだよね。

まあ、オイラーさんに文句はいえないわけだけど。

*問35 [#j7f541bc]
最大公約数を求める問題なんだけど、回答しているプログラムがうまく通らなかった。

primesが定義されていないからだ。

回答されているプログラムをみる限りprimesにはStream形の配列に素数リストを定義したものを代入すれば、動くようなつくりになっている。

だから、どうっていうことでもないんだけどね。

**Stream [#q9928a1b]
Streamは要素が必要になったときに作成されるList(みたいなモノ)です。

要素は必要になったときに初めて作成されるので、 
-要素の作成に時間がかかる場合に初期作成コストを抑えることができます。 
-また、要素を全部辿らない場合に無駄な作成コストを削減できます。 
-JavaのInputStreamとかとは何の関係もありません。

*問36 [#y12cb8d8]
模範解答例には２つの解き方が書いてあるが、あえて難しいほうの回答を読解してみる。

- 引数 n 元の数
- 引数 p ためしに割ってみる素数

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と違って、かならず値を返すことになっている。

**matchを調べてみる [#p74826ab]

自分でまとめるよりも、はるかにわかりやすくまとめている人がいるのを発見したので、リンクしておきます。

かなりまとまっているところへリンク

http://sites.google.com/site/scalamemo/kihon-1/matchingu

ややまとまっているところへのリンク

http://d.hatena.ne.jp/taktamur/20091115/1258292009

だいたいまとめると、

***switchみたいな使い方 [#v92113d8]
 val ret = x match{
        case "a" => "Alpha";
        case "b" => "Beta";
        case _ => "unknown";
  }

***マッチさせながら変数に代入 [#s66e137f]
 def generalSize(x:Any) = x match{
      case s:String => s.length;
      case m:Map[_,_] => m.size;
      case _ => -1;
    }

*scalaの_アンダーバー [#of6c8bab]
-あるときは高階関数の引数
-あるときは仮引数
-あるときはmatchの、何でもマッチ表記
_*　だと可変長の配列のマッチ表記

*問37 [#ibbacf23]
問３６の答えをつかって、もっと簡潔に問34の問題をとこうという趣旨だとおもうが、ここでは、ふたたび
foldLeftの使い方の復習をしてみたいと思う。一度、この９９問題の例題にとりあげたのだが、すっかりわすれてしまっている。

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)は引数で、まずは左側の引数に初期値の１が入る。で、配列の要素数分ループしますが、その際に、初期値が入っていた変数に、評価したものが格納されるしくみになっています。

今回の例ではmatchの中に、無名関数があります。引数がp,mなのでrがpになって、fがmになるってことでいいのかな？

**foldleftの説明 [#s718888f]
http://d.hatena.ne.jp/taktamur/20091114/1258210136

*問38 [#u2345b5a]
回答をみると、これは実行時間計測サンプルとして使えますな。

処理内容自体を引数として渡しているところが、Scalaっぽい書き方です。

**ブロック受け側 [#o4e822c7]
  def time[A](label: String)(block: => A): A = {
    val now = System.currentTimeMillis()
    val ret = block
    println(label + ": " + (System.currentTimeMillis() - now) + " ms.")
    ret
  }

引数の型はJavaの”クラス　変数名”という書き方ではなく"変数名: クラス"という活気型でブロックの時はクラス名がないからなのか "=> 適当な変数名 "と書くのかもしれません。

で、=>ってなんだっけ？

**ブロックを使った呼び出し側 [#ad62b395]
 time("P34 (" + n + ")") {
      n.totientP34
 }

ブロックは、変数としては渡しておらず、引数とは別に右隣に｛　｝で括った箇所が渡せるようになっています。

**takeWhile [#ufc03432]
久しぶりにtakeWhileがでてきて使い方を復習してみる

***takeWhile使い方の例 [#o5641f57]
まずは、処理対象のリストを用意しておきましてと、
 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>3　となって、条件を満たさないので、
それ以降の要素を無視するようになっています。

**force [#y664ec78]
下記の模範回答のコードの一部に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については、まったく何もでてきやしない。

***forceについて触れてある記事 [#b088e3f9]

Scala6階：型

http://www.h7.dion.ne.jp/~samwyn/Scala/type.htm

にて
 Iterableの遅延相当型。
 def force: Iterable[A]

Arrayを結果するforceのみを強制。
 abstract def force: Array[A]

と書いてあった。

なんのことやらである。強制的に宣言するのであろうか？

もう一つあったので、書いておく

***"LazyJ: Seamless Lazy Evaluation in Java"。 LazyJ について。 Java に Haskell のような遅延評価を入れる話。 [#c9daecdc]

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 の名前を見るので一度さわってみようと 思いつつ早幾年。
 
 誰か「３分でわかるPolyglot」とか書くとよいよ！

えーと、自分の理解力では、１％ぐらいしか理解できんなぁ。

何が１％かというと、それは、forceとは遅延評価に関係した単語であるということぐらいだ。

そこで今度は "Scala force 遅延評価"でググってみた。

そうすると、概念的な記事がwikiに掲載されていました。

***forceについて書かれている遅延評価のwiki [#df04a174]
http://ja.wikipedia.org/wiki/%e9%81%85%e5%bb%b6%e8%a9%95%e4%be%a1

-実際の計算が行われていない中間状態の時それをプロミス (promise)
 
-計算の実体をさしてサンク (thunk) といい、

-プロミスを強制(force)することで値が計算される。

この概念と単語をしらないといけなかったのだね。つまり、この概念が日常的な概念だと勘違いしている人は、

そのまま、前置きの説明もなく、forceがどうのこうのと書いて説明した気になっているってことなんだね。

***結論 [#jfb97fb0]
説明はみつけられなかったが、遅延評価部分を、「ここで評価します」というメソッドがforceってことにしておこうとおもいます。

*問３９ [#tcc264bc]
解答にあるprimesはどこにも定義されていないようだ。
この解答を理解するには次のことを理解するひつようがある。
-配列の変数を宣言して、インスタンスに数値の要素を持つ配列を格納させること
-配列の切り出し方法と最終的にリストにする方法

**解答は次のようになっている。 [#k286a1ac]
 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)

**実験してみた [#a2367f96]
次のコードを実験してみた
 primes dropWhile { _ < 3 }

結果
  Array[Int] = Array(3, 5, 7, 11, 13)

**実験してみた [#cf481440]
 Array(3, 5, 7, 11, 13) toList

結果
 List[Int] = List(3, 5, 7, 11, 13)

**考察 [#o44c2fd2]
 scalaは配列を主語にしてスペース動詞という感じでプログラムが書けるようになっているようだ。

spamではない場合はチェックをいれてください。タイムスタンプを変更しない