とりとめのないことを書いております。
by tempurature
カテゴリ
全体
プログラミング
scheme
verilog
未分類
以前の記事
2016年 04月
2016年 03月
2016年 02月
2016年 01月
2015年 12月
2015年 11月
2015年 10月
2015年 09月
2015年 08月
2015年 07月
2015年 06月
2015年 03月
お気に入りブログ
PHPで競技プログラミング
メモ帳
最新のトラックバック
ライフログ
検索
タグ
その他のジャンル
ブログパーツ
最新の記事
情報処理技術者試験 お疲れ様..
at 2016-04-17 18:55
基本情報技術者試験 平成27..
at 2016-04-14 04:48
基本情報技術者試験 平成27..
at 2016-04-13 23:03
苦い薬(ハーブ、サプリメント..
at 2016-04-09 14:03
「おバカ度チェックリスト」を..
at 2016-03-24 09:54
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
タグ:Racket ( 45 ) タグの人気記事
「好きな数字ランキング」をRacketで実装してみた
#lang racket
(require rackunit)

#|
NTTドコモが2010年に「一番好きな数字ランキング」という
ランキングを実施してました。ということで、
Racketでそれを実装してみようと思いました。

[一番好きな数字ランキング]
1位:7
2位:3
3位:2
4位:8
5位:5
6位:1
7位:6
8位:4
9位:9
10位:0
ソース:http://ranking.goo.ne.jp/ranking/category/999/faction_Opr7Tu7Tgqet_all/
|#

; ソースコード
(define (number->ranking n)
  (list-ref (list 10 6 3 2 8 5 7 1 4 9) n))

(define (more-favorite? p q)
  (< (number->ranking p) (number->ranking q)))

; テストコード
(check-equal? (number->ranking 7) 1)
(check-equal? (number->ranking 3) 2)
(check-equal? (number->ranking 2) 3)
(check-equal? (number->ranking 8) 4)
(check-equal? (number->ranking 5) 5)
(check-equal? (number->ranking 1) 6)
(check-equal? (number->ranking 6) 7)
(check-equal? (number->ranking 4) 8)
(check-equal? (number->ranking 9) 9)
(check-equal? (number->ranking 0) 10)
(check-true (more-favorite? 7 2))
(check-false (more-favorite? 9 4))
(check-false (more-favorite? 5 5))


[PR]
by tempurature | 2016-01-16 10:07 | scheme
Haskellの例題をRacketでも実行してみた
#lang racket

#| haskellのコード

pyths :: Int -> [(Int, Int, Int)]
pyths n = [ (x,y,z)
        | x<-[1..n], y<-[1..n], z <- [1..n], x^2+y^2==z^2]

|#

(define (pyths n)
  (for*/list ((x (in-range 1 (add1 n)))
              (y (in-range 1 (add1 n)))
              (z (in-range 1 (add1 n)))
              #:when (= (+ (sqr x) (sqr y)) (sqr z)))
    (list x y z)))

#|

実行時間計測

[Haskell]
*Main Data.Char> pyths 100
...
(2.92 secs, 1,811,409,328 bytes)

*Main Data.Char> pyths 500
...
(357.39 secs, 226,074,909,384 bytes)

[Racket] (単位はミリ秒)
> (time (pyths 100))
cpu time: 63 real time: 52 gc time: 0
...

> (time (pyths 500))
cpu time: 6578 real time: 6586 gc time: 0
...

インタプリタ上での時間計測では、
Racketの実行時間に比べてHaskellの実行時間は
異様に長かった。

というより、Haskellの画面表示は特異で、リストを結果として表示する場合は
リストの開き括弧だけがしばらく表示されていたりします。
HaskellというのはLispと似ているものかと思っていましたが、
どうやら内部の構造が相当違っていそうです。

|#


[PR]
by tempurature | 2016-01-01 00:43 | プログラミング
メリークリスマス! Dr. Racket!!
12/25。今日のDr. Racketの起動画面はミケランジェロの「アダムの創造」です。
キリスト生誕祭とは微妙にずれているような… なんでもないです。

c0364169_23510586.png

[PR]
by tempurature | 2015-12-25 23:51 | scheme
【racket】林先生が驚く初耳学! の結婚理論をシミュレーションで実証(n=10の場合)
前回の続きです。とりあえずソースコードから。

ソースコード

#lang racket
   
(define (for-each-permutation proc n)
  (define (req header rest)
    (if (null? rest)
        (proc (reverse header))
        (for-each
         (lambda (n)
           (req (cons (list-ref rest n) header)
                (append (take rest n) (drop rest (add1 n)))))
         (range (length rest)))))
  (req empty (range n)))

(define (let-go-and-catch perm t)
  (define tmp-top
    (if (zero? t) -1 (apply max (take (take perm t) t))))
  (define (get-point lst)
    (if (false? lst) 0 (add1 (first lst))))
  (get-point
   (memf (curryr > tmp-top) (drop perm t))))

(define (factorial n) (apply * (range 1 (+ n 1))))

(define (solve-expectation-value t n)
  (let ((sum 0))
    (for-each-permutation
     (lambda (perm) (set! sum (+ (let-go-and-catch perm t) sum))) n)
    (/ sum (factorial n))))

(define (solve-probability-of-the-best t n)
  (let ((sum 0))
    (for-each-permutation
     (lambda (perm)
       (when (= (let-go-and-catch perm t) n) (set! sum (add1 sum)))) n)
    (/ sum (factorial n))))

(define (solve-probability-not-married t n)
  (let ((sum 0))
    (for-each-permutation
     (lambda (perm)
       (when (= (let-go-and-catch perm t) 0) (set! sum (add1 sum)))) n)
    (/ sum (factorial n))))


自分が何番目の異性と結婚することができるかの期待値はsolve-expectation-value関数で算出します。0〜10の範囲のスコアで算出しています(10は一番の相手と結婚、0は未婚)。

t=0: 5.50
t=1: 7.20
t=2: 7.07
t=3: 6.48
t=4: 5.70
t=5: 4.84
t=6: 3.91
t=7: 2.96
t=8: 1.99
t=9: 1.00
t=10: 0.00

期待値だけで見た場合は、「最初の相手は見送って、2人目からは最初の人よりもいいひとなら結婚」するのがいいようです。

自分が出会う10人の人のうち、1番相性のいい人と結婚できる確率はsolve-probability-of-the-best関数で算出します。

t=0: 10.0%
t=1: 28.3%
t=2: 36.6%
t=3: 39.9%
t=4: 39.8%
t=5: 37.2%
t=6: 32.7%
t=7: 26.5%
t=8: 18.9%
t=9: 10.0%
t=10: 0.0%

1番相性のいい人と結婚したい場合、「お付き合いする人を3人見送って、4人目からはそれまでの人比べていい人なら結婚」するのがいいようです。

最後に最後まで未婚で終わってしまう確率を算出しました。

t=0: 0.0%
t=1: 10.0%
t=2: 20.0%
t=3: 30.0%
t=4: 40.0%
t=5: 50.0%
t=6: 60.0%
t=7: 70.0%
t=8: 80.0%
t=9: 90.0%
t=10: 100.0%

この結果は、上の2つに比べて単純です。例えば、1番狙いで3人見送ると未婚になる確率は30%です。1番の相手を探すのって意外にリスキーなのがわかります。


[PR]
by tempurature | 2015-12-23 14:14 | scheme
コード効率と可読性について
ソースコードは、コード効率と可読性が高い方がいいに決まってる。当然です。

なぜかといって、プログラミングの工数は一般的に高いので、たいていの人は自分の書いたコードを使いまわすからです。例えば、この前書いたウェブサイト用のコードをゲームアプリのコードにコピペしてたりする。

あと、プログラムを書く人というのは、捨てコードを書くつもりで書くことが少ない。捨てコードを書く人はむしろよくわかっている人です。

そして、職場やインターネットの仲間たちに賞賛されたいですよね(笑)。


でもコード効率と可読性はトレードオフの関係にあったりする。

プログラミングが大した好きでもないのにコードを書いている人はたくさんいます。そのような人たちはよく、コードがクラスや関数で構造化されると可読性が悪くなると主張します。実際そうなのでしょうか?

私はその意見については一理あると思います。構造化されていないコードというのは、乱雑なように見えて、実行時間や各変数の挙動については構造化されているコードよりも分かりやすかったりします。

下手に構造化されているコードと構造化されていないコードとでは、下手に構造化されているコードのほうが問題が大きいと思います。


普段からコードを書いている人たちはつい見逃してしまうのですけど、クラスだけでなく、関数やサブルーチンでさえも習得するのは難しかったりします。

例えばCの関数の場合は、関数の内部で他の関数の変数を参照できません。当たり前ですが、プログラムを普段書かない人にとっては、非常に厳しい制約に思えます。Cの関数やアセンブラのサブルーチン、クラス、クロージャ等々はそれぞれの言語におけるルールですが、そのルールでうまくやるための定石ないし慣例といったものも当然あります。

普段プログラムを書かない人は、関数の文法が頭に入っていないから混乱するのではなく、その言語でプレーするためのプレースタイルを学んでいないため混乱するのだと思います。しかも、そういった定石はたいていの教科書に書いてないですし、習得するのにそれなりに時間もかかります。


かといって、構造化されていないコードを書くべきなのでしょうか?ある意味でそれは正解となります。コード効率を高めるためには、構造化の方法を注意深く検討する必要があります。つまり、コード効率、実行効率、可読性を天秤にかけて最適化問題を解く必要があるのですが、そのためには初めに構造化されていないコードを書く必要があるのです。

どれを関数にするのか、どれをクラスにするのかを決定するのは、その道のプロでもそれほど簡単な問題ではないはずです。なので、自分は上級者だと見栄を張らずに構造化されていないコードを初めに書くのが正しいように思います。

特にゲームプログラミングではよくあることなのですが、同じような言い回しを何回も繰り返していたりします。そういうのは、その人のコーディングスキルがないのではなく、コードを最適化する前にコードを直さなければならないからなのでしょう。


[PR]
by tempurature | 2015-12-23 11:09 | プログラミング
【racket】林先生が驚く初耳学! の結婚理論をシミュレーションで実証(したかったのだが…)
12/20の「林先生が驚く初耳学!」で林修さんが披露していた結婚に関する数学的考察について、シミュレーションで検証してみようと思いました。

この考察では、20歳から35歳の間に出会う人間のうち、一番自分とふさわしい相手と結婚するにはどうするのが最適か?という問題について扱っています。

ここでは、結論だけを書かせていただきますが、「20歳から35歳の間に出会う人間をn人とすると、最初に出会う(1/e)n人(つまり0.37n人)とのお付き合いでは結婚しないでおき、それ以降は、今までに付き合った人よりもいい人であれば結婚するのがよい」のだそうです。

さて、シミュレーションでは、集合{0, ..., n-1}の置換(permutation)を生成し、t人見送った時の自分と一番ふさわしい相手と結婚する確率、または自分が結婚するのが何番目の相手であるかということの期待値を算出してみます。

まず、(make-permutation n)関数を記述しました。置換のリストを出力する関数です。

>(make-permutation 3)
((0 1 2) (0 2 1) (1 0 2) (1 2 0) (2 0 1) (2 1 0))

しかし、この関数はnを多くした時にメモリを大量に消費するので、代わりに次のような関数を用意しました。

#lang racket
(require point-free)

(define (power-list l1 l2)
  (if (null? l2)
      l1
      (foldr append empty
             (map (lambda (x) (map (lambda (y) (append x y)) l2)) l1))))
   
(define (for-each-permutation proc n)
  (define (req header rest)
    (if (null? rest)
        (proc (reverse header))
        (for-each
         (lambda (n)
           (req (cons (list-ref rest n) header)
                (append (take rest n) (drop rest (add1 n)))))
         (range (length rest)))))
  (req empty (range n)))


しかし、この関数を持ってしても思った以上の計算効率が得られないようです。次のベンチマークを実行してみました。

(define (benchmark n)
  (time
   (let ((a 0))
     (for-each-permutation (lambda (x) (set! a (add1 a))) n)
   a)))


ベンチマークの実行結果です。
> (benchmark 5)
cpu time: 0 real time: 0 gc time: 0
120
> (benchmark 6)
cpu time: 0 real time: 0 gc time: 0
720
> (benchmark 7)
cpu time: 32 real time: 36 gc time: 32
5040
> (benchmark 8)
cpu time: 47 real time: 55 gc time: 31
40320
> (benchmark 9)
cpu time: 329 real time: 323 gc time: 62
362880
> (benchmark 10)
cpu time: 3141 real time: 3132 gc time: 690
3628800
> (benchmark 11)
cpu time: 36218 real time: 36340 gc time: 9431
39916800
n=10で3.1秒、n=11で36.2秒かかっています。置換の個数はn!(nの階乗)で与えられるので、n=12, 13, 14, 15のときはそれぞれ6分、78分、18時間、11日かかるものと考えられます。20歳から35歳の間に15人の相手と付き合う人もなかなかなものだと思いますが、このような場合は少し方法を変えたほうが良さそうです


[PR]
by tempurature | 2015-12-22 00:27 | scheme
【racket】lambda, cut, curryに関する演習問題
lambdaが出てきた時に、瞬時にcut, curryに置き換えられるかのトレーニングです。

Q. 以下の無名関数のそれぞれについてcut, curryに置き換えられるか答えよ。

1. (lambda (x) (* x 2))
2. (lambda (x) (- x 2))
3. (lambda (x y) (cons (* x 2) y))
4. (lambda (x) (* x x))
5. (lambda (x) (x 2))
6. (lambda (x y z) (x y z))

[閑話休題]



A.

1. cut, curryどちらも可能
(cut * <> 2)
(curry * 2)

2. cutのみ可能
(cut - <> 2)
※curryrが使えます。(curryr - 2)

3. どちらも不可
※(cut (* <> 2) <>)はエラーになる

4. どちらも不可

5. cutのみ可能
(cut <> 2)

6. cutのみ可能
(cut <> <> <>)

---

この通り、curryはcutに比べて使いづらいのですが、私なりの利点としてはこう考えています。

(lambda (x) (* x 2))を、日本語に置き換えると、「引数xをとり、xと2をかけた数を返す関数」というふうになります。

(cut * <> 2)だと、「1つの引数をとり、その引数と2をかけた値を返す関数」という意味です。

(curry * 2)で、「2をかける関数」という意味になるのだと考えます。つまり、引数を隠蔽することでより自然言語に近い表現になっているのだと思います。こういうのをポイントフリーというらしいです。
(ただ、ギリシャ時代の数学書は引数を使わないので恐ろしく理解しづらいのだが…)


[PR]
by tempurature | 2015-12-20 04:16 | scheme
【racket】REALM OF RACKET 7章を読みました
REALM OF RACKETの7章は、Land of Lambda。韻を踏んでます、ヨウチェケラッ!

ラムダは偉大なり
ラムダは偉大なり
ラムダは偉大なり

そういえば高階関数のことをタカシナカンスウと呼びたくなるのは私だけでしょうか?

The Great Lambda
The Great Lambda
The Great Lambda

7章のなかで登場する関数たち。Racketeerは手続き(procedure)のことを関数(function)というらしいです。

map
filter
ormap
andmap
foldr
foldl
build-list
apply

build-list?!
build-listはRacket特有の組み込み関数らしいです。

(build-list n proc) -> list?

> (build-list 3 add1)
'(1 2 3)
> (build-list 5 sqr)
'(0 1 4 9 16)
> (build-list 5 sqrt)
'(0 1 1.4142135623730951 1.7320508075688772 2)
> (build-list 3 +)
'(0 1 2)
> (build-list 3 *)
'(0 1 2)

この関数は、range, iotaに似ていますが、初期値とステップ数を取ることができないので使いづらいです。

+, *を受け付けますが、(build-list 3 cons)とするとさすがに怒られます。


Lambda is great
Lambda is great
Lambda is great
Lambda is great
Lambda is great

そういえばRacketのソースコードの中には画像の他に、「λ」を貼り付けることができます。でもClojureのfnのほうが名前が短いのでいいように思います。

(fn [x] (* x 2))
(fn (x) (* x 2))とはかけない。残念

lambdaの短縮形として、cutを紹介しました。
(lambda (x) (* x 2))
(cut * <> 2)

Forumで教えてもらったのですが、Racketにはcurryという組み込み関数があって、さらに短く書くことができます。

(curry * 2)

curryはいわゆるカリー化のカリーです。F#でこれを習った時は、なんて無駄機能なのだろうと思ったのですが、lambda同様、ちょっとした用で使えるようです。


[PR]
by tempurature | 2015-12-18 23:07 | scheme
【racket】REALM OF RACKET 6章の課題/Difficult
5章は、4問全て解いていましたが、6章ではDifficultだけ解いて終わりにしようと思いました。ですがソースコードを自分ごのみにリファクタリングをかけるのもおっくうに思えて、本のソースコードをちょい修正して解きました。なので、ソースコードは公開できないです。

c0364169_23524142.png

上の画像をよく見ると(このプログラムと問題に習熟している人間であれば)、バグがあることに気が付きます。

具体的には、このゲームのゲームオーバーの条件は、2つのヘビが自分か相手同士か壁にぶつかることなので、間違っています。

完成したプログラムを試していると、いきなり例外が発生したり、ゲームオーバーになったりします。特に、上の場合は対戦モードなのでデバッグがしづらくて困ります。ゲームを作るのって想像以上に難しいのだと思います。痛感させられました。


[PR]
by tempurature | 2015-12-16 23:59 | scheme
【racket】REALM OF RACKET 6章の内容
6章では、ヘビが自分にぶつからないようにして、獲物を食べていくゲームを作ります。獲物を食べるとヘビの体が大きくなります。

ソースコードは200行くらいなので、なかなかのコード効率だと思います。

c0364169_22335766.png

[PR]
by tempurature | 2015-12-16 22:35 | scheme