トップ
新規
単語検索
ヘルプ
活動記録/第5回
をテンプレートにして作成
開始行:
- 日時 :2006/6/12 (Mon)
- 場所 :名大 理学部1号館(多元数理科学研究科) 307室
- 時刻 :18:00〜19:30
- 参加者:9名
- 話題 :
- おつかれさまです。勉強会中でやった[[継続渡しによる別解:...
- すみません、Exeriseの更新をしようと思ったのですが、編集...
- すみません、直しました。 -- [[けいご]] &new{2006-06-20 ...
----
#contents
* 5章 Exercise 続き [#e8ab579a]
**Exercise 6. けいご [#k186bd76]
- 元のquick
let rec quick = function
[] -> []
| [x] -> [x]
| x :: xs -> (* x is the pivot *)
let rec partition left right = function
[] -> (quick left) @ (x :: quick right)
| y :: ys -> if x < y then partition left (y :: ...
else partition (y :: left) right ys
in partition [] [] xs;;
- 答え
let rec quicker l sorted = match l with
[] -> sorted
| [x] -> x :: sorted
| x :: xs -> (* x is the pivot *)
let rec partition left right = function
[] -> quicker left (x :: quicker right sorted)
| y :: ys -> if x < y then partition left (y :: ...
else partition (y :: left) right ys
in partition [] [] xs;;
- 試してみる
# quicker [2; 3; 9; 1; 5; 4] [];;
- : int list = [1; 2; 3; 4; 5; 9]
- quicker left (x :: quicker right sorted)がポイント
- Haskellのshowsもこんな感じ 一般にconsリストの連結は時間...
-- (Haskellで書くと) "hoge" ++ "foobar" よりも (?s -> 'h'...
-- (関係ないけど) しかし、stringはchar listではない…試し...
# (fun x -> 'h'::'o'::'g'::'e'::x) "foobar";;
This expression("foobar") has type string but is here us...
**Exercise 7. みずの [#a2b0a0db]
(* fromからtoまでの数列を生成 *)
let rec range from_value to_value =
if from_value > to_value then []
else from_value::(range (from_value + 1) to_value);;
(* 整数版sqrt *)
let sqrt_int x = int_of_float (sqrt (float_of_int x));;
let f r x xs= let y = sqrt_int(r - x*x) in
if x > y && (x*x + y*y = r) then
(x,y)::xs
else
xs;;
let squares r = List.fold_right (f r) (range 0 (sqrt_int...
**Exercise8.飯田、吉岡 [#x53ada9d]
let rec rev l1 l2 = match l1 with [] -> l2
| x::rest -> rev rest (x::l2);;
let map2 f = let rec map'f res
= function [] -> rev res [] | x::rest -> map'...
in map' f [];;
***Exercise8の別解 by けいご [#k36863d8]
'''継続渡しスタイル (Continuation Passing Style)'''と呼ぶ...
- OCaml:
let map2 f xs =
let rec map' f ys k =
match ys with
[] -> k []
| y'::ys' -> map' f ys' (fun zs -> k (f y'::zs))
in map' f xs (fun x->x);;
ここで
| y'::ys' -> map' f ys' (fun zs -> f y' :: k zs)
とやってしまった。結果リストが逆順になる…thx to みずの
- Haskell脳なかわいそうな人のために:
map' f (x:xs) k = map' f xs (?ys->k (f x:ys))
map' f [] k = k []
***効率は? [#d340c6ec]
どうやって計る?体感的には同じ位に思えた。
とりあえず,ベンチマークしてみました.(樋口)
~教科書中にあった指定した長さの乱数のリストを得る関数
let nextrand seed =
let a = 16807.0 and m = 2147483647.0 in
let t = a *. seed
in t -. m *. floor(t /. m)
let rec randlist n seed tail =
if n = 0 then (seed,tail)
else randlist (n-1) (nextrand seed) (seed::tail)
これを使い,長さ10000000のリストを用意し,
すべての要素を+1するような実験を行いました.
let _ = map2 (fun x -> x +. 1.0) (snd (randlist 10000000...
ex8a, ex8bは共にocamlc.opt -o ex8a ex8a.ml
といったように特にオプションなしでコンパイルしました.
-ex8a 飯田・吉岡 解
Command being timed: "./ex8a"
User time (seconds): 18.46
System time (seconds): 0.68
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:19...
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 0
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 163
Minor (reclaiming a frame) page faults: 114564
Voluntary context switches: 0
Involuntary context switches: 0
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
-ex8b けいご 解
Command being timed: "./ex8b"
User time (seconds): 19.82
System time (seconds): 3.68
Percent of CPU this job got: 11%
Elapsed (wall clock) time (h:mm:ss or m:ss): 3:31...
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 0
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 30614
Minor (reclaiming a frame) page faults: 628565
Voluntary context switches: 0
Involuntary context switches: 0
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
~User timeを見ると似たようなものですけど,
System timeやpage faultをみてみると
ex8bは,激しくメモリを消費中?
* 6章 Exercise [#j2d045ed]
**Exercise 2(樋口) [#vfa96a64]
nat上で
int_of_nat,
mul,
monus を定義せよ
参考 nat の定義
type nat = Zero | OneMoreThan of nat ;;
let rec int_of_nat = function
Zero -> 0 |
OneMoreThan n -> 1 + int_of_nat n;;
let rec add m n =
match m with
Zero -> n |
OneMoreThan m' -> OneMoreThan (add m' n);;
が定義されているとして
let rec mul m n =
match m with
Zero -> Zero |
OneMoreThan Zero -> n |
OneMoreThan m' -> add n (mul m' n);;
let rec monus m n =
match m with
Zero -> Zero |
OneMoreThan m' -> match n with
Zero -> OneMoreThan m' |
OneMoreThan n' -> monus m' n';;
**Exercise 3(末次) [#pb712e62]
let rec minus m n =
match (m, n) with
(m, Zero) -> Some m
| (Zero, _) -> None
| (OneMoreThan k, OneMoreThan l) -> minus k l;;
**Exercise 5(下村) [#s9e70b19]
(* inord *)
let rec inord t l =
match t with
Lf -> l
| Br(x,left,right) -> (inord left (x :: inord right ...
(* postord *)
let rec postord t l =
match t with
Lf -> l
| Br(x,left,right) -> (postord left (postord right (...
一応、ここで使った二分木の定義。
type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;
**Exercise 6(小笠原) [#o9117959]
ごめんなさい、結構難しい...ToT
すぐにできないので、宿題とさせてください。
終了行:
- 日時 :2006/6/12 (Mon)
- 場所 :名大 理学部1号館(多元数理科学研究科) 307室
- 時刻 :18:00〜19:30
- 参加者:9名
- 話題 :
- おつかれさまです。勉強会中でやった[[継続渡しによる別解:...
- すみません、Exeriseの更新をしようと思ったのですが、編集...
- すみません、直しました。 -- [[けいご]] &new{2006-06-20 ...
----
#contents
* 5章 Exercise 続き [#e8ab579a]
**Exercise 6. けいご [#k186bd76]
- 元のquick
let rec quick = function
[] -> []
| [x] -> [x]
| x :: xs -> (* x is the pivot *)
let rec partition left right = function
[] -> (quick left) @ (x :: quick right)
| y :: ys -> if x < y then partition left (y :: ...
else partition (y :: left) right ys
in partition [] [] xs;;
- 答え
let rec quicker l sorted = match l with
[] -> sorted
| [x] -> x :: sorted
| x :: xs -> (* x is the pivot *)
let rec partition left right = function
[] -> quicker left (x :: quicker right sorted)
| y :: ys -> if x < y then partition left (y :: ...
else partition (y :: left) right ys
in partition [] [] xs;;
- 試してみる
# quicker [2; 3; 9; 1; 5; 4] [];;
- : int list = [1; 2; 3; 4; 5; 9]
- quicker left (x :: quicker right sorted)がポイント
- Haskellのshowsもこんな感じ 一般にconsリストの連結は時間...
-- (Haskellで書くと) "hoge" ++ "foobar" よりも (?s -> 'h'...
-- (関係ないけど) しかし、stringはchar listではない…試し...
# (fun x -> 'h'::'o'::'g'::'e'::x) "foobar";;
This expression("foobar") has type string but is here us...
**Exercise 7. みずの [#a2b0a0db]
(* fromからtoまでの数列を生成 *)
let rec range from_value to_value =
if from_value > to_value then []
else from_value::(range (from_value + 1) to_value);;
(* 整数版sqrt *)
let sqrt_int x = int_of_float (sqrt (float_of_int x));;
let f r x xs= let y = sqrt_int(r - x*x) in
if x > y && (x*x + y*y = r) then
(x,y)::xs
else
xs;;
let squares r = List.fold_right (f r) (range 0 (sqrt_int...
**Exercise8.飯田、吉岡 [#x53ada9d]
let rec rev l1 l2 = match l1 with [] -> l2
| x::rest -> rev rest (x::l2);;
let map2 f = let rec map'f res
= function [] -> rev res [] | x::rest -> map'...
in map' f [];;
***Exercise8の別解 by けいご [#k36863d8]
'''継続渡しスタイル (Continuation Passing Style)'''と呼ぶ...
- OCaml:
let map2 f xs =
let rec map' f ys k =
match ys with
[] -> k []
| y'::ys' -> map' f ys' (fun zs -> k (f y'::zs))
in map' f xs (fun x->x);;
ここで
| y'::ys' -> map' f ys' (fun zs -> f y' :: k zs)
とやってしまった。結果リストが逆順になる…thx to みずの
- Haskell脳なかわいそうな人のために:
map' f (x:xs) k = map' f xs (?ys->k (f x:ys))
map' f [] k = k []
***効率は? [#d340c6ec]
どうやって計る?体感的には同じ位に思えた。
とりあえず,ベンチマークしてみました.(樋口)
~教科書中にあった指定した長さの乱数のリストを得る関数
let nextrand seed =
let a = 16807.0 and m = 2147483647.0 in
let t = a *. seed
in t -. m *. floor(t /. m)
let rec randlist n seed tail =
if n = 0 then (seed,tail)
else randlist (n-1) (nextrand seed) (seed::tail)
これを使い,長さ10000000のリストを用意し,
すべての要素を+1するような実験を行いました.
let _ = map2 (fun x -> x +. 1.0) (snd (randlist 10000000...
ex8a, ex8bは共にocamlc.opt -o ex8a ex8a.ml
といったように特にオプションなしでコンパイルしました.
-ex8a 飯田・吉岡 解
Command being timed: "./ex8a"
User time (seconds): 18.46
System time (seconds): 0.68
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:19...
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 0
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 163
Minor (reclaiming a frame) page faults: 114564
Voluntary context switches: 0
Involuntary context switches: 0
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
-ex8b けいご 解
Command being timed: "./ex8b"
User time (seconds): 19.82
System time (seconds): 3.68
Percent of CPU this job got: 11%
Elapsed (wall clock) time (h:mm:ss or m:ss): 3:31...
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 0
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 30614
Minor (reclaiming a frame) page faults: 628565
Voluntary context switches: 0
Involuntary context switches: 0
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
~User timeを見ると似たようなものですけど,
System timeやpage faultをみてみると
ex8bは,激しくメモリを消費中?
* 6章 Exercise [#j2d045ed]
**Exercise 2(樋口) [#vfa96a64]
nat上で
int_of_nat,
mul,
monus を定義せよ
参考 nat の定義
type nat = Zero | OneMoreThan of nat ;;
let rec int_of_nat = function
Zero -> 0 |
OneMoreThan n -> 1 + int_of_nat n;;
let rec add m n =
match m with
Zero -> n |
OneMoreThan m' -> OneMoreThan (add m' n);;
が定義されているとして
let rec mul m n =
match m with
Zero -> Zero |
OneMoreThan Zero -> n |
OneMoreThan m' -> add n (mul m' n);;
let rec monus m n =
match m with
Zero -> Zero |
OneMoreThan m' -> match n with
Zero -> OneMoreThan m' |
OneMoreThan n' -> monus m' n';;
**Exercise 3(末次) [#pb712e62]
let rec minus m n =
match (m, n) with
(m, Zero) -> Some m
| (Zero, _) -> None
| (OneMoreThan k, OneMoreThan l) -> minus k l;;
**Exercise 5(下村) [#s9e70b19]
(* inord *)
let rec inord t l =
match t with
Lf -> l
| Br(x,left,right) -> (inord left (x :: inord right ...
(* postord *)
let rec postord t l =
match t with
Lf -> l
| Br(x,left,right) -> (postord left (postord right (...
一応、ここで使った二分木の定義。
type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;
**Exercise 6(小笠原) [#o9117959]
ごめんなさい、結構難しい...ToT
すぐにできないので、宿題とさせてください。
ページ名: