Custom AST Transformation で メモ化を試してみました

Groovy AST変換によるコンパイル時メタプログラミングについて、調査を継続しています。今日は、簡単なコードを書いてみました。コンパイル中に AST 変換を行い、任意のメソッドをメモ化できます。とりあえず使用例を。 @Memoized def fib(n) { if (n <= 1) …

Groovy 始めました。

Groovy では、AST をカジュアルに変換できると聞きました。サイコーじゃないですか。ということで、いきなり AST 周りを調べています。で、一つ疑問が。int + int の計算であり、かつ、左辺値のコンテキストも int を要求しているのに、なんで一回 Object に…

比較はモノイド

比較モナドについて考察されている一連のエントリに感銘を受けて、私も比較について考えてみました。 比較モナド - terazzoの日記 続・比較モナド - terazzoの日記 続・続・比較モナド〜復讐編〜 - terazzoの日記 まず、考察対象として「比較結果」と「比較…

実用的な同時並行ソートを実装する話

scala の parallel collection は、普通の collection を使うように使っているだけで、並列計算の恩恵を受けられる場合も多いのですが、そうではない場合も多いです。その典型例が、ソートです。実は、並列のソートは、まだ実装されていません。じゃあ、自分…

scala を左傾化させる話

Scala exercises for beginners を foldLeft で解いてみた。 // Exercise 2 def sum(x: List[Int]): Int = x.foldLeft(0){_ + _} // Exercise 3 def length[A](x: List[A]): Int = x.foldLeft(0){(sum, _) => sum + 1} // Exercise 4 def map[A, B](x: List[…

akka の例題を parallel collection で実装

akka の例題では、arctan(1) をテーラー級数展開して円周率を求めるという例題を取り上げている。具体的には、下記の数式を10000項ずつ Actor に割り振って、並列計算している。このような級数を scala で並列計算する方法としては、akka を使う以外にも、sc…

Scala の内面を Haskell 化する話

Scala を使って Haskell 風の記述をしている例を時々見かけるけれど、徹頭徹尾 Haskell になっている例はあまり見掛けない。アプリケーションロジックだけ見れば同じなんだけれど、実際の内部動作は全然違っていたりする。そして、パフォーマンスが致命的に…

関数の自動メモ化

groovy 1.8 では、memoize によってクロージャのメモ化が出来るようになったけれど、scala だってできるもん、という負け惜しみエントリ。 普通の自動メモ化 サクっと作ったものを(1〜5引数対応)をGistに上げたので簡単に紹介。実装のポイントは単純で、下記…

ハミング数の算法 3種 - infinite list, imperative queue, cyclical iteration

素因数分解が の形式になる数をハミング数という*1。この手の問題は、やはり Haskell で書くとスッキリする。Hamming numbers - Rosetta Code から Haskell のコードを引用する。 hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*)…

フィボナッチ数の算法のベンチマーク

まずは、結果を下図に示します。なおベンチマークに使用したコードは上記の説明コードとは違い、チューニング済みです。逐次平方変換のコードは、dev68 さんの groovy 実装 をそのまま scala に移植しました。また、このエントリをきっかけとして、このエン…

A linear algebra view of Fibonacci sequence

はじめに フィボナッチ数列の高速な算法である 逐次平方変換 Binet公式 について、線形代数的な視点から説明を与えて、ベンチマークしてみました。なおどちらの方法についても、詳しい説明は世の中に出回っているはずですが、私にとってそれらの説明は天才の…

RubyのEnumerableを遅延評価にしてみる

最近、無意識のうちに遅延評価を前提としたコードを書くようになってきました。趣味の scala コードばかりを書いている弊害でしょうか。そんな遅延脳が失態をやらかしました。正格評価前提の言語(Ruby)で、遅延評価を期待したコードを書いてしまい、プログラ…

基礎から始める覆面算

Scala の for 式で覆面算を解いているエントリを見つけた人が Haskell と Groovy で解きながらリスト内包表記について考えていた。このようなエントリを見かけると、いつも面白いなーと感心するけど、どうも私は実戦で使いこなせていない。おそらくは、パフ…

Re:今流行のお題を出してみた(一方通行を許可した迷路を作成)

こちらの問題を解いてみました。グラフ連結に関する理論を全く使っていないという意味で、力技です。一方通行のドアが壁に存在する期待値が40%くらいまでなら、なんとかなりました。 35%を切ってくると、このままでは厳しいかもしれません。再帰の仕方とかは…

時間帯重複チェックの計算量と前提条件

お題:時間帯重複チェック(応用編) - No Programming, No Life に関して、解法は2種類に大別できるようです。 解法の分類 離散時刻方式 「時間帯(何時何分から何時何分まで)に含まれる時刻(何時何分)の最小単位が1分」であることに注目した方式です。…

時間帯重複チェック:仕様変更で絶賛炎上中編

先日、時間帯重複チェック の問題を Scala で解いてみたのですが、その応用編が出題されました。なんと、「お客様から仕様変更を言い渡されました」ですと。(><)うえーんうえーん、さきに言ってよー。スパゲチーくらえー!!!今回は特に見所はありませ…

答案:時間帯重複チェック (Scala による Option モナド活用編)

お題:時間帯重複チェック - No Programming, No Life を Scala で解いてみました。「失敗するかもしれない処理」を記述する際に、Java では例外を使うと思いますが、Scalaでは、Option を使うという選択肢があります。そこで、今回の答案は、例外ではなくて…

追記:まともなアルゴリズムによる解法

ちょっと悩んだけれど、まともな解法も考えつくことができた。基本的には篩方式のアルゴリズム。 object Prob216 { def solve { val N = 50000000 //10000 val nToT: Int => Long = n => 2L * n * n - 1 val tSeq = Array.tabulate(N + 1)(nToT) for { n <- …

scala 2.9 collection.parallel を実戦投入です!!

プログラミング問題サイトProject Eulerの第216問に、こんな問題が出た。1 自然数 n について、2*n2-1 が素数となるものの個数を求めよ普通に素数判定すると計算時間がかかる(一時間くらい?)ので工夫したアルゴリズムで解け、というのが出題意図と思う。…

scala 合算実験に興味を示しました

scala で collection の要素の合計を求める方法について、比較検討されている。 Scala 合算実験(Hishidama's Scala sum Memo) Numeric[T]を自分で実装して sum を使うあたりとか、おーそういう手もあったか、みたいな。でも、再帰の比較が頂けない。Vector/W…

blog とか始めてみた

これから、低能さ加減を晒していきますよん!例えば、文章構成のまずさとか、コミュ障な感じとか。