全文検索
Tag クラウド
.NET RIA Services Alice Artisteer Boo CKeditor clojure DotNetNuke Drupal F# FCKeditor friendfeed Gauche Go Google App Engine IronScheme JavaScript jconsole Joomla JOSH JSON moblin mongodb OpenSUSE Protocol Buffer PubSubHubBub Python Quercus redis Resin Restlet RIA Scala Silverlight twitter VisualVM WikiBook Wordpress スーツとギーク プログラミング言語オタク 中学生 平常な場所での文学 文弱 柄谷行人 涼宮ハルヒの消失 長門有希アーカイブ
このサイトは?
本サイトでは、チームの技術調査の成果を(いささかの遊びごころを盛り込みつつ)順次掲載していきます。 現在、WordPress等のブログ/CMSと連携する、新世代の分散webサイト(Java/.NETを含む)の構築に関する調査及び、次世代のプログラミング教育環境に関する調査を展開中です。
東北楽天ゴールデンイーグルスファン在籍。
お問い合わせ先
supportあっとwordprogress.org (担当・赤坂)
ランダムリンク集
RandomLinks@bit.ly
以下、実験中 :
I'm twitterd...
- @scala ついにScala開眼祭りが。まぁ、宗教はあんまいらんでしょ。それはさておき愛すべき変態くまくまー氏のScala界参入はうれしい限り。 2010-05-11
- これはキテル!? 新フレームワークRangoの件 http://ff.im/-eCQgR 2010-01-22
- これはキテル!? 新フレームワークRangoの件 http://ff.im/-eCQgR 2010-01-22
- More updates...
Posting tweet...
Powered by Twitter Tools
TAG | Scala
チームWordProgressの新着記事一覧です :
(※各記事の内容を閲覧するためには、各記事のタイトルをクリックしてください。)年末くらいから、Google App Engineを使い始めようと思っている。Scalaで使いたいのだが、もれなく、Javaのライブラリを呼びだすことになるため、しばしば問題になるScalaとアノテーションの関係を復習しておきたい。keisuken氏が述べているとおり、import javax.annotation._して、クラス宣言の前に、@Resource { val name = “名前”,・・・・}と書いていくのが基本らしい。
実際のところは、Google App Engine向けに実装するときに・・・と思ったのだが、Scala2.8ではけっこう、アノテーションが使われるようになるんだね。アノテーションの好き嫌いはあるだろうが、「かゆいところに手が届く」的な用法なのは気に入った。
Scala 2.8では、@scala.annotaiton.tailrecアノテーションが追加 => 末尾再帰最適化を期待するメソッドにつけとくと、最適化されないパターンだったときにコンパイラがエラーを吐く
Scala 2.8では、@switch アノテーションが追加 => JVM バイトコードの tableswitch最適化がされないパターンだったときにコンパイラがエラーを吐く
が、Scala2.8、リリースが遅延しているし、リリース直後から実アプリ作りにつかっていいものか、今イチ不安だなぁ・・・(弱気)。。ついでに元ネタにリンクする気力なくすみません。。
@Resource {
val name = “abc”,
val `type` = classOf[Object],
val authenticationType = Resource.AuthenticationType.APPLICATION,
val shareable = true,
val mappedName = “helloworld”,
val description = “Hello, world type”
}
class HelloWorld {
def [...]
最近、夜中に書いた放言を、けっこうはてぶしていただいたScalaとグーグルgolangの関係だけれど、
Scala on Java VM ≒ (Haskell的言語) on golang
と考えておけば、これから5年くらいは大して外さないのではと思っている。・・・現状のHaskellがHaskell自身で実装されているなど、going my wayな点はさておく。
もちろん、純粋すぎるHaskellがgolangに実装される時には、GoskellとかHaskegolangとか、よくわからない名前の不純ななものになっているかもしれないが(JavaにHaskellを移そうとした人々は、Jaskellと名づけている)。
その点、golang上のrubyならば、gorubyで決まりだろう。ノーベル平和賞受賞者ゴルビーにも配慮十分な覚えやすい名前である。
ともあれ、(Haskell的言語) on golang、ひょっとしたら、5年後にはScalaの強敵になっているのかもしれない。関数脳を働かせる時にはhaskellの側で、手続型コードを書く時にはgolangでというわけ。もちろん、並列処理対応だってばっちりだ。
でも、プログラム言語の普及は常にゆっくりなもの。
ふつうのプログラマが、プログラム言語が手になじませるのには時間がかかる。ここ5年で普通に使われるようになる言語は、Scalaの方だ。
なんてったって、「Javaの限界を超えて実用化を目指す新開発言語「Scala」のメリットとは~後編(codezine誌)」に取り上げられているように、Scalaは、今日からでも、ベターJavaとしてプログラムを書いていけるのだから。
ベターJava。うまい言葉じゃないか。
正直に言うと、Scalaが、HaskellやLispやClojureやF#などと共に属している関数型言語界隈的には、Javaっぽく書いたら負けである。
だが、男には(もちろん、女にも)、とりあえず手っ取り早くすませてしまいたい時がいつでもやってくる。そんなときばかりは、負けとかぬるいとか、言っていられない。
たとえば、
関数型言語のListは、Arrayより遅いらしい、と上司が聞きつけてきたとしよう(上司は「遅い」という言葉に過敏であるとする)。悪いことに、初のScala案件を受託した上司は、Scalaコーディング規約なるものを作ろうとしている。
ScalaプログラミングでList禁止とかいう謎の御触れが出されたらことである。そう、あなたは、忙しいにも関わらず、大急ぎでベンチマーク対決をしなければならなくなった。
そんな時でもScalaなら安心だ。
Java屋であろうとなかろうと、Javaで現在時刻を知る関数がcurrentTimeMillisであることは、ググってみればすぐわかる。
もちろん、Scalaでも、
scala> System.currentTimeMillis
res1: Long = 1258619704810
これを使って、データを付加する時間、データにアクセスする時間計測すればよい。結果は、case classに入れることにしよう。
//ベンチマーク結果の格納クラス
case class Result(
val AppendTime:Double, //データを付加する時間の結果
val AccessTime:Double// とデータにアクセスする時間
) {
val total = AppendTime + AccessTime
}
・・・・ここであなたの手がとまる。ベンチマークって関数型言語的にどう書くんだ・・・・関数渡し・・・をするとして、もArrayとListの双方に対応するには・・・
Scalaなら、とりあえず、こんな風な考えが浮かんできてしまっても大丈夫だ :
いいや、forループでてきとうに書いて、
あとはコピペしててきとうに書こう。
えっと・・・・
//入力 ループ回数MAX
def simpleBench (MAX:Int)= {
println (“Loops : “+MAX)
//ベンチマークの結果(データを付加する時間とデータにアクセスする時間)
case class Result(val AppendTime:Double,val AccessTime:Double) {
val total = [...]
Scala入門記事というにはおこがましいかもしれないが、病み上がりに負けず今回は、輝かしい実績をお持ちの浅海氏の「Scalaプログラミングの勘所(1) @ >IT pro」に対し、勝手に追記。& どうやら、グーグルgolangについても語っておくのが今風らしいので、今回も後半でgolangに言及。
IT pro誌に連載中の本記事、その前までの回がかなりマニアックであったため、Scalaをはじめたばかりの方があまり読んでいないのではと思われる。しかし、Scalaのコレクション・クラスを知るには、非常に実践的で良い記事なので、少なくともこの回だけは読んでおいてほしい。
で、追記。
Scalaのコレクション・クラスは、データセットの繰り返し関係を扱うIteratorトレイトを内部的に持つと共に、データの取扱い方を抽象化したIterable・Collectionトレイトから派生している。浅海氏が取り上げているListやArrayも例外ではない。こうした裏方を知っておくことコレ大事ということで、特にJavaとの互換性を保つ上で不可欠なIteratorトレイトに少し言及。
※トレイトが何かは省略。はじめての方は、「scala trait」でググッて調べていただきたい。
いわゆるデザインパターンにおいて、繰り返しを扱うiteratorパターンはけっこう有名。その由来通りに、ScalaのIteratorトレイトも、繰り返し関係を取り扱うためのnextメソッド・hasNextメソッドを持っている。
Iteratorを生成し、nextしていってみよう。シングルトンオブジェクトという仕組みで、Scalaでは、以下のようにいきなりイテレータを生成できる。
scala> val i1 = Iterator.range(0,3) //0以上3未満の整数を生成
i1: Iterator[Int] = non-empty iterator
生成されたi1はnextメソッドを持っているはずである。
scala> i1.next
res6: Int = 0
scala> i1.next
res7: Int = 1
scala> i1.next
res8: Int = 2
scala> i1.next //3以上の整数は存在しないためエラーとなる
java.util.NoSuchElementException: next on empty iterator
さて、多少の好き嫌いはあろうものの、Scalaは、基本、万人受けする美少女言語。Scalaのiteratorトレイトは、古のiteratorパターンを軽々とこえていく。いわゆる高階メソッドがばりばり使えるのである。
高階メソッドとは、とりあえず、「ようそひとつひとつをまとめてドンのメソッド」とでもいっておこうか。詳しくは浅海氏の記事を読んでいただくとして、ちょっとだけ。
まずはmkstring。以下のようにタイプすると、
scala> Iterator.range(1,5).mkString(“Nagato”)
res7: String = 1Nagato2Nagato3Nagato4
数字の間に旧日本軍の戦艦長門が3隻はさみこまれた。これは、Iteratorの要素(1,2,3,4)のコンマの部分が長門におきかわったというわけ。
まぁ、mkStringはあまりおもしろくないので、次はかの大企業IBMとviエディタ日本語パッチ(vij)に高階関数mapを適用してみよう。
scala> Iterator.fromString(“IBMVIJ”).
map (x => x – 1).
foreach { x => print (x.toChar)}
warning: there were deprecation warnings;
HALUHI
おっと、どこかの組織が余計なwarningを出しているが、とりあえず、IBM => [...]
Scalaって、なんだか中途半端な関節技使い関数型言語じゃね、と思ってるおまいらに
Scalaの打撃系手続き型言語の実力を見せてやんよ(~> つり)。。
@ITにて、JavaScriptでストイックにアルゴリズムとデータ構造している連載を見つけた。すばらしい。ということで、KMP法というやつをScalaで書いて見る。
いや、Scalaブログ的には関数型っぽく書くとかっこいいとされているし、実際、関数脳は大事なのだが、better Javaとしてふつうに使えてるよ、という例までに。
//文字列探索のアルゴリズムに KMP (Knuth-Morris-Pratt) 法
// REPL環境での試し方 :、
//KMP.find(“キーワード”,”検索対象の文字列”で実行
class State(keyword: String) {
val EOS = keyword.length – 1
var loc = 0 //文字の位置
def done = (loc == EOS) // 最後の位置までたどりついたか
def next(c: Char) =
if (c [...]
Javaバーチャルマシン上のLisp系新言語Clojureの良さについて書く。
Lisp系といっても、なんだか読みやすいのである。そして、実案件でも使われていたり。興味を持った方は、まずは、「InfoQ Jruby Clojure」あたりでぐぐってみてほしい。
#追記・寝ぼけていたのかtypo多すぎなので修正orz
私の知る限り、日本語の記述でもっともClojureに好意的な記述をしてくださっているのは、何をかくそう、プログラミング言語Ruby作者Matz氏の「the 0.8 true language」である(ただし、潜在的には、だが)。以下、このMatz氏の長年日記を参考にさせてもらいながら書いていく。
———-(ここからMatzにっきの引用中心)————-
Matz氏は問う、「(これからのプログラミングの)80%の領域をカバーする言語」、名づけて「the 0.8 true language」はいかなるものか、と。そして、Matz氏はいくつかの条件を挙げている。
オブジェクトとメッセージ(or 動的結合)
高階関数(とクロージャ) ※ここのクロージャは当然、言語機能
内部DSL
並列実装技術
そして、シンプルな文法
Matz氏は、これらを満たす候補として、第一にLispとRubyをあげつつ、現時点のRubyをthe 0.8 true language候補としては留保している(並列実装技術の導入が遅れているため)。そして、Lispについては、内部DSL向けではない(Lispのマクロは別物の言語を作りやすすぎるから)点を課題として挙げている。
そして、Matz氏の日記は、以下の言をつぶやいて終わる(まぁ、続きはそのうちに、という感じで)。
今後Java方面では、ますますのXMLの活用とJVM上のJavaでない言語の台頭が予想される。 というか、もうかなり出てきてるよね。JRubyとかGroovyとかScalaとかClojureとか。
———–(Matzにっきの引用終わり)—————
さて、以上のJRuby~Clojureの4言語の中で、Clojureのみが上記5条件を満たす、と思っている。JRubyとGroovyは並列処理に弱い。そして、Scalaはぜんぜんシンプルではない。
他方、Clojureは、Scheme/CommonLisp等の標準Lispとの互換性を捨て、S式内部にDSLを持つLispである(clojureコミュニティではLess Lispyと呼んでいたりする。Lispっぽくなくも書ける・・)。内部DSLを意識し、並列処理を前面に出した唯一のLisp、それがClojureである。
・・・ということで、本サイトではこれからもClojureに注目していく。Clojureがマイナーであること・おそらくマイナーでありつづけることを知っているので、ややネタ的に。これでいいんだよな、長門Clojure。そう、Clojureはふつうの言語より0.2くらい欠けている(例えば、継承ベースのオブジェクト指向言語機能は、「一切ない」)のだが、それが、逆にシンプルさ・科目さという魅力を出しているのだ。
[追記]継承ベースのオブジェクト指向言語機能が「一切ない」言語といえば、GoogleのGo言語もそのひとつ。 Goにたぶん言語機能としてのクロージャ(closure)はないが、当然実装可能である。Goがclosureを持つ言語(例えば、RubyやClojure)を実装すれば、組み合わせとして上記の5条件をかなり良好に満たすであろうことをいいそえておく。Cの継承者を目指すGoにはそのうちいくつものスクリプト言語系が実装されるであろうことは、想像に難くない。
[本投稿の背景事情] 小ネタをいろいろおりまぜつつの本サイト、個人的にはScalaとClojureの比較をメインに据えていく予定であったのだが、(自らの発熱に)ついカッとなって、想定外にScala v.s. Goの比較をしたところ、急に本サイトにアクセスが集中してまっている。このままでは、既に全校生徒世界的に注目の集まっているScalaはさとおき、文芸部とコンピ研Lisperの間のみで話題となっているClojureが埋没しかねない。というか、誰も読まないだろうと思って書いたネタに相当のアクセスが流れて、ちょっとまずい状況。ということで、いてもたってもいられず、まじめにClojureの良さを、まずは少しだけ書いておいたと。
Scala入門 勝手流追記 その2。元記事が大上段なので、こちらも大上段に。
Scalaで実サービスをリリースしている著者らのJavaの限界を超えて実用化を目指す新開発言語「Scala」のメリットとは~前編(codezine誌)
今回は、codezine、1位と2位の記事がScalaとGoであること(11/12時点)にちなんで両者を比較しつつ、元記事に一点だけ突っ込む。
[追記@昼間]
以下、熱が下がった直後の明け方に書いたんで、いろいろ記載が粗いので、前提条件・抜け落ち等を補充。
◇プログラミング言語比較の前提はTiobeのランキングのような検索エンジンベースのランキング。
当然、書籍ベースのランキングや「魂」のランキングは十分に加味されていない・・・のはさておき、そもそも検索エンジンという仕組みへの信頼性が落ちている(少なくとも不況下の幻滅期にある)と思われるので、プログラミング言語の流行り廃りの議論に、こうしたランキングが良いかは、不明(といっても、Tiobeランキングのどの位置にGoがやってくるのか、皆興味あるだろうが)
◇Tiobeベースで話を進めているのに、メジャー言語にPHPが抜けていた。
これはScala v.s. Goということでミドルから下を主に考えていたから。少なくとも、Goベースのwebサーバは遠からず出てくるだろうし、その上でPHPが動くだろう事も明らかなので、PHPの文字を補っておいた。そもそもこのサイトもWordPress。いや速度面はさておき、良く出来ている。
◇そして、何より、議論のベースに静的片付け言語万歳。C系構文は永遠に不滅です、って言うのがあった(Goはいうまでもなく、ScalaもけっこうC系言語)。
これは、
「真のバカでも使えるものを設計しようとして人々がよくやるミスは、
真のバカのバカさ加減を過小評価することだ」
--Douglas Adams
(出典 Diomisid Spinellis著 『コード・リーディング』, p65)
という警句を、コンパイル時に真にバカなミスをしまくっている自分なりに重く受け入れているから。システム系言語はバカの壁に大いに配慮してほしい。ともあれ、Goみたいのがでてくると、下のレイヤの本を読もうという気になる。Goはひょっとしたら泡沫言語になるのかもしれないけれど、少なくとも、Cに近いレイヤに刺激を与える貢献は達成するのでは。
[再度追記
『コード・リーディング』を開いたついでに、監訳者であるMatz氏のにっきを見ると、Goについてのコメントが。やはり、Goには、尊敬するMatz氏も気になる変態言語(というか、大胆な言語)の側面あり。コメントでのやりとりにあるとおり、実装の継承(共有)まわり、プロトタイプ継承っぽいのでは・・・。「半人前の言語」あるいは「小学1年生(ただし神童)くらいの言語」だからこそ、Goと共にプログラミングを学ぶ価値はある。
<本文>
JRuby/Jythonなどスクリプト言語由来の言語と異なり、Javaと同様の静的コンパイル言語であるScalaは、Javaバーチャルマシンの主流言語の座をめぐり、本家Javaに挑む挑戦者に位置づけられる。
その試みが成就するのは、早くとも数年後であろうが、Javaの袋小路を打ち破る方向性をScalaは示したといえる。
Javaに対するScalaの利点は、以下の3つであろう。
不変性(val)の上手な導入による容易な並列処理プログラミング ※メモリリーク等を防ぐガベージコレクションの仕組みあり
簡潔な表記と型を含めたカスタマイズを可能とする言語内言語(DSL)構築能力 ※タイプセーフなスタイルを採用
スクリプトに近い簡潔な記述(関数型言語の型推論などに由来)
-----------
と書いたところで、これらの特性はただいま祭り中のグーグルの新プログラミング言語Goの特性とかぶることに気がつく。
C言語に対するGo言語の利点(私見)
・goroutine等による容易な並列処理プログラミング ※メモリリーク等を防ぐガベージコレクションの仕組みあり
・interface機能による言語拡張構能力(C++のtemplateに近いもの、か) ※タイプセーフなスタイルを採用
一方、ScalaとGoの明らかな相違点
・Scalaの言語仕様は巨大。Goの言語仕様は現時点では小さい => コンパイル時間についてはGoの圧勝(実行速度は最適化されたJavaVM上のScalaが速い場合もあろう)
※JVMかネイティブかはさておく。小飼氏ではないが、ネイティブScalaの可能性だってある。
Goの方の利点は2つだけであるが、これはGoがCに近しい低レベルな言語であることによる。RubyがCで実装されたように、Goの上でGoと親和的なスクリプト言語が出てくるのも遠くないことと思われる。
そうなると、2010年代の新主流言語をめぐる争いの中で、注目株のひとつが、
Scala v.s. (Go+(新)スクリプト言語)
というものになる可能性がある(あくまで仮説)。
もしかすると、この2言語の争いは、C,Java,C++(かろうじてC#)といったメジャー言語に割ってはいる最後の新言語をめぐる争いとなるかもしれない
※それ以降(2020年以降?)にくる「新言語」は、もはやアルファベットと記号で表記するプログラミング言語でないのかもしれない。
※個人的には、(新)スクリプト言語の座は、clojureであってほしいと思っているのだが、、実際には、PHPやRuby、あるいはそれらの新種がその位置を占めるのかもしれない。
----------
この仮説はさておき、Goの登場は、本格的な並列処理対応を打ち出した新型の手続き型言語の登場ということで、並列処理対応といえば、関数型言語Erlang,Scala,Clojure・・・という流れを変えるきっかけになるのかもしれない。
これは、かつての総合格闘技をグレーシー一族が関節技・寝技で席巻していた中で、グレーシーを打撃で打ち破った猛者が出たことで、打撃系が一気に見直されたようなもの・・か?(少なくとも、関数型言語には、関節技的なマニアックさがあるのは事実 ^^)
とここで、気がつくのは、数ある関数型言語の中で、唯一Scalaだけが、手続き型プログラミングも普通にかけるハイブリット言語であることを打ち出していることだ。
(実際、codezine記事のパテントビューロ社も手続き型言語の経験者のみが集まり、Scalaで実システムを作り上げている)
すなわち、Goの登場により、新世代の並列処理もやはり手続き型プログラミング・スタイルが主流となったとしても、Scalaは十分生き残っていくポテンシャルがあるのだ。
※言語仕様は巨大だが、現時点でも実行速度は相当速い
再び述べるが、やはり、「現存の言語では最も美少女な Scala」(小飼弾言を日々Scalaを使っている身から一部修正。現時点のScalaは大人の女性ではなく女子高校生レベルの成長途上にある)なのだ。
Scalaと、センセーショナルにデビューしたGo[golangのMLは1日で1000人近い参加者という押すな押すな状態]との関係、今後が楽しみである。
ということで、私は、昼はScala、夜はGoをいじる毎日でいこうと思う(Goについてはgoroutineはさておいて、斬新と思われるinterfaceを押さえたい)。
さて、元Scaka入門記事に一点だけつっこみ
6ページ目「Arrayは直接にAnyをデータ要素として持つことはできないようです(注4)」
少しミスリーディングな記述である(Genericや型パラメータの解説前なので仕方ないが)。Scalaの利点は静的な型づけにある。故に、入門記事であっても型の話は慎重に書かなければならない。
ので、勝手に補充
例えば、mapをもちいたArrayでは、ANY型を持つことができる(持ってしまう)
val anyarr =
Array.range(1,101).map { n => n match{
case _ if (n%15 == 0) => ” FizzBuzz ”
case _ [...]
こんな投稿が、Clojure-MLでちょっとした祭りを起こしている。
Does Clojure have a function like Haskell’s group?
In Haskell,
Input: group [1,2,2,1,1,1,2,2,2,1]
Output: [[1],[2,2],[1,1,1],[2,2,2],[1]]
Thanks
そのなの、partition-by関数一発だろと、
(use ‘clojure.contrib.seq-utils)
(partition-by identity [1 2 2 1 1 1 2 2 2 1])
=> ((1) (2 2) (1 1 1) (2 2 2) (1))
という突込みが入った後、
そんなgroupメソッドくらい、自分で作ろうぜと、皆で、いろいろとラムダラムダ(clojureにlambdaは出てこないが・・)。さすがLispers。。
Scalaなら・・・こうかな。
def group (L:List[Any]) = {
def g1 (L:List[Any],temp :List[List[Any]]) : List[List[Any]]= {
[...]
Scalaの欠点をあえてあげるとすれば、言語仕様が大きすぎるところ。
Scalaを使っている時、たいていは、便利・快適。なんだけれど、JSONのようにlight-weightなターゲットを扱う時には、「牛刀をもって鶏を割く(古)」・「馬から落ちて落馬した」的な、大げさ感・冗長感を感じることも。
この点、オブジェクト指向言語で「ない」ことを明言しているClojureは、JSONのようなものと相性が良さげ(これは、ClojureがListに限らずさまざまなデータ構造を扱うのを、Scalaに負けないくらい得意であることにもよる)。
ということで、JSON(BSON)ベースの文書指向データベースmongodbのclojure対応の試み、前々から興味深く思っていたんだけれど、githubにプロジェクトを立ててくれたみたい。
昨日立ったばかりのプロジェクトなんだけれど、例がけっこう充実している!
◇1件のデータのインサート 「私はrobbyという名前のロボットです」
1件のデータのインサート 「私はrobbyという名前のロボットです」
(insert! :robots
{:name “robby”}
◇一括インサート! 10,000件まとめて・・のはず
(mass-insert!
:points
(for [x (range 100) y (range 100)]
{:x x
:y y
:z (* x y)}))
=> nil
(fetch-count :points)
=> 100000
mongodbはScalaからさわったんだけれど、正直clojureからの方が感触よさげ。
clojure-clrの近況を見てClojure萌え再発ついでに。
後発のClojureの側からScalaを見るのが利にかなっていると思ったので、Scalaから見たClojure、改め、今後は 長門有希が観測する涼宮ハルヒClojureから見たScalaでいこうと思い立つ。ということで、ちょっと前にScalaで見たフィボナッチ数列をClojureで。・・・と思ったら、本家にきれいなメモ化の実装が既に本家に置いてありますね。
atomsでフィボナッチ数列@本家clojureサイト
clojureでは、mutableなデータを明示的に扱う。メモ化するデータを、(atom {})にいれていくのがポイント。STMを含め、clojureのmutableなデータの扱いはセンスが良い(clojureのSTMの概要については、InfoQ記事)。
ベンチマークまでつけてくれている。単純な再帰に比べメモ化版の実行速度は10,000倍以上
自分が半分寝ながら書いたScala版メモ化より、ぜんぜんきれい(というか、シンプルな言語系同士の比較ということで、dan氏のJavaScriptでメモ化の実装と見比べるのがいいかも[再び紹介、「フィボナッチ数列にO()を学ぶ」)。もちろん、Scalaだってやればできる子(というか、できすぎる子)なので、ちゃんとしたフィボナッチ実装はいくつも転がっているが。
※ついでに、ScalaでSTM/better Actor実装のプロジェクトも絶賛活動中 => 並列処理に興味ある人は、Scala界最強のハッカーの一人であろう、jboner氏のakka を心して観察せよ。
前エントリのクロージャ導入ネタついでの発展的例題として、フィボナッチ数列あたりがいいかなと考えて探していたのだが、またしてもdankogai氏に行き着いた。「フィボナッチ数列にO()を学ぶ」、これが実に分かりやすい。いや、この人はほんとに頭がいいのかも、と初めて(?)思った。
[その他、長門clojure版のフィボナッチ駆け足解説も見つかったので、これはこれで別エントリで]
なので、例によって、Scalaにて写経: ※JavaScriptのコードは元サイト側で、例題をちょこちょこ書き換えevalして即実行できるようになっているので、省略。・・この面、たしかにJavaScriptは教育向き。
◇再帰を用いたナイーブな実装 : 「計算量」O(2n)
実装(ちょっとだけScala風にさせてもらった) ※(たとえ、Scalaであっても)計算効率が悪いアルゴリズムなので遅い
def fibo (n :Int) : Int =
if (n < 2) n else {fibo(n-2) + fibo(n-1)}
val fiboList = {for (i <-1 to 10) yield fibo(i)}.toList
実行例
scala> fiboList foreach println _
1
1
2
3
5
8
13
21
34
55
◇クロージャを活用した実装 : 「計算量」O(n)
うん、良い例題。しかし、JavaScriptも結構簡潔だなぁ。やはり、動的言語の方が教育向きか。
def fib(n:Int) = {
def f(a:Int, b:Int, c:Int) :Int=
if (c <= 2) a else f(a+b, a, c-1)
f(1, 1, [...]
