14.1 Time と Timer ストラクチャ
問 14.1
日時の表現と操作は DATE シグネチャを持つ
Date ストラクチャで提供されている．
DATE シグネチャはその型から容易にその機能を推定できる．
必要なら Date ストラクチャを使い，現在の日時と時刻を表す文字列
を返す関数
currentTime : unit -> string
を定義せよ．
解答例 以下に定義と実行の例を示す。
# fun currentTime () = Date.toString (Date.fromTimeLocal (Time.now())); val currentTime = fn : unit -> string # currentTime (); val it = "Sun Jul 19 10:17:42 2020" : string
問 14.2
関数 nlogn : int -> real と intcomp : int*int -> order を定義 し，checkTime 関数を完成させよ．
解答例 以下に例を示す。 以下では、intcompは、Intストラクチャに定義されている compare関数を使用している。
fun log2 x = Math.log10 x / (Math.log10 2.0)
fun nlogn n = ((Real.fromInt n) * (log2 (Real.fromInt n)))
fun checkTime n =
let
val array = genArray n
val tm = timeRun ArrayQuickSort.sort (array,Int.compare)
val nlognRatio = tm / (nlogn n)
in
(n, tm div 1000, nlognRatio)
end
問 14.3
関数 printResult : int * int * real -> unit は， の値，時間，時間ととの比の値を受け取り， size=10000, milli-secs=40, micro-secs/n log(n)=0.30103000 の形式でプリントする関数である． printResult 関数を定義し， checkTime 関数を完成させ， 前節で作成したソートプログラムの評価を行え．
解答例 文脈から、完成させるべき関数は、checkTimeではなく、testSort関数である。 ここでは、SML#の動的型付け機構を使って定義されている以下の型の汎用の 清書関数
# Dynamic.pp; val it = fn : [’a#reify. ’a -> unit]
を使った定義例を以下に示す。
fun printResult (n, tm, ratio) =
Dynamic.pp
{"size" = n, "milli-secs" = tm, "micro-secs/n long(n)" = ratio}
fun testSort n = printResult (checkTime n)
以下は、SML#の対話型環境下での実行結果である。
# app testSort [1000, 10000, 1000000, 10000000];
{"micro-secs/n long(n)" = 0.0, "milli-secs" = 0, size = 1000}
{"micro-secs/n long(n)" = 0.0602059991328, "milli-secs" = 8, size = 10000}
{"micro-secs/n long(n)" = 0.0834856521308, "milli-secs" = 1664, size = 1000000}
{
"micro-secs/n long(n)" = 0.0822069913873,
"milli-secs" = 19116,
size = 10000000
}
val it = () : unit
問 14.4
配列の大きさのリストを受け取り，各について の値，計算時間，の値との比を
- evalSort [10000,100000,1000000,10000000];
array size milli-sec. micro s./n log(n)
10000 30 0.22577250
100000 460 0.27694760
1000000 5740 0.28798536
10000000 66630 0.28653755
------------------------------------------------------------
avarage 0.26931075
のような形式で表示する関数 evalSort を以下の手順で作成せよ．
-
1.
20文字以下の大きさの文字列を受け取り，その前に空白文字を 付け加え，20文字の大きさの文字列を返す関数 padString : string -> string を定義せよ．
-
2.
padString を使って，2つの整数と1つの実数を受け取り，以下のよう な形式でプリントする関数 printLine を定義せよ． - printLine; val it = fn : int * int * real -> unit - printLine (10000,30,0.22577250);
10000 30 0.22577250val it = () : unit -
3.
以上を使って evalSort を定義せよ．
解答例 evalSortの定義例を以下に示す。 この例では、padStringを定義する代わりに、StringCvtストラクチャの padLeft関数を使用している。
fun evalSort L =
let
val L’ = map checkTime L
val av = (foldr (fn ((_,_,x),y) => y+x) 0.0 L’)/(Real.fromInt (List.length L’))
val title = (StringCvt.padLeft #" " 20 "array size")
^ (StringCvt.padLeft #" " 20 "milli-sec.")
^ (StringCvt.padLeft #" " 20 "micro s./nlogn")
^ "\n"
fun formatReal a = StringCvt.padLeft #" " 20 (Real.fmt (StringCvt.FIX (SOME 8)) a)
fun printLine (n,a,c) =
let
val ns = StringCvt.padLeft #" " 20 (Int.toString n)
val sa = StringCvt.padLeft #" " 20 (Int.toString a)
val sc = formatReal c
in
print (ns ^ sa ^ sc ^ "\n")
end
in
(print title;
map printLine L’;
print "------------------------------------------------------------\n";
print (" avarage" ^ (formatReal av));
print "\n")
end
以下は、SML#の対話型環境下での実行結果である。 現在の実行環境では、大きさ10000の配列では短時間に終了し、誤差が大きくなるとため、 100000、1000000, 10000000、67108863（最大配列サイズ）のテスト行っている。
# evalSort [100000, 1000000, 10000000, Array.maxLen div 4];
array size milli-sec. micro s./nlogn
100000 152 0.09151312
1000000 1784 0.08950625
10000000 20300 0.08729870
67108863 144932 0.08306366
------------------------------------------------------------
avarage 0.08784543
val it = () : unit
問 14.5
関数 checkTime を一般化し，汎用のテスト 関数
eval : {prog:’a->’b, input:’a, size:’a-> int, base:int -> real}
-> int * real * real
を定義せよ． ただし，引数レコードの各フィールドの意味は以下のとおりとする．
| フィールド | 値の意味 |
|---|---|
| prog | 評価すべきプログラム |
| input | プログラムへの入力 |
| size | 入力の大きさを返す関数 |
| base | 評価の基準となる関数 |
結果の型の意味は checkTime の場合と同様である．
解答例 checkTimeと同様であれば、結果の型はint * int * realである。 以下は定義例である。
fun eval {prog, input, size, base} =
let
val tm = timeRun prog input
val n = size input
val ratio = Real.fromInt tm / base n
in
(n, tm div 1000, ratio)
end
問 14.6
自然数のリストを受け取り，各要素に対して，大きさの乱数配列 を生成し，上記のような回の比較を行い，処理時間およびそのとの比を
- evalCompare [500000,1000000,5000000];
array size milli-sec. micro s./n
500000 40 0.08000000
1000000 70 0.07000000
5000000 370 0.07400000
------------------------------------------------------------
avarage 0.07466667
のような形式で表示する関数 evalCompare を，eval を使って定義せよ．
解答例 以下に定義例を示す。
fun evalCompare L =
let
fun comp array =
let
val n = Array.length array
val p = Array.sub(array, 0)
val m = n div 2
fun loop x = if x <= m then ()
else (Int.compare (Array.sub(array, n - x), p);
Int.compare (Array.sub(array, x - 1), p);
loop (x -1))
in
loop n
end
fun evalN n = eval {prog = comp, input = genArray n, size = Array.length, base = real}
val L’ = map evalN L
val av = (foldr (fn ((_,_,x),y) => y+x) 0.0 L’)/(Real.fromInt (List.length L’))
val title = (StringCvt.padLeft #" " 20 "array size")
^ (StringCvt.padLeft #" " 20 "milli-sec.")
^ (StringCvt.padLeft #" " 20 "micro s./n")
^ "\n"
fun formatReal a = StringCvt.padLeft #" " 20 (Real.fmt (StringCvt.FIX (SOME 8)) a)
fun printLine (n,a,c) =
let
val ns = StringCvt.padLeft #" " 20 (Int.toString n)
val sa = StringCvt.padLeft #" " 20 (Int.toString a)
val sc = formatReal c
in
print (ns ^ sa ^ sc ^ "\n")
end
in
(print title;
map printLine L’;
print "------------------------------------------------------------\n";
print (" avarage" ^ (formatReal av));
print "\n")
end
以下にSML#でのテスト例を示す。
# evalCompare [1000000, 10000000, Array.maxLen div 4];
array size milli-sec. micro s./n
1000000 8 0.00800000
10000000 80 0.00800000
67108863 564 0.00840426
------------------------------------------------------------
avarage 0.00813475
val it = () : unit
問 14.7
evalSort と evalCompare を組み合わせ，ソート関数の処理性能を
- normalEvalSort [500000,1000000,5000000,10000000];
array size time in cunit T/n log(n)
500000 2740 3.75926754
1000000 5860 3.81825925
5000000 33270 3.88323623
10000000 68970 3.85195525
------------------------------------------------------------
avarage 3.82817957
The estimated sort time function: T(n) = 3.8 n log(n).
のような形式で表示をする関数 normalEvalSort を定義せよ．
解答例 以下に定義例を示す。
fun evalCompare L =
let
fun comp array =
let
val n = Array.length array
val p = Array.sub(array, 0)
val m = n div 2
fun loop x = if x <= m then ()
else (Int.compare (Array.sub(array, n - x), p);
Int.compare (Array.sub(array, x - 1), p);
loop (x -1))
in
loop n
end
fun evalN n =
let val array = genArray n
in eval {prog = comp, input = array, size = Array.length, base = real} end
val L’ = map evalN L
val av = (foldr (fn ((_,_,x),y) => y+x) 0.0 L’)/(Real.fromInt (List.length L’))
in
av
end
fun evalSortN c L =
let
fun sort array = ArrayQuickSort.sort (array, Int.compare)
fun base n = c * nlogn n
fun evalN n = eval {prog = sort, input = genArray n, size = Array.length, base = base}
val L’ = map evalN L
val av = (foldr (fn ((_,_,x),y) => y+x) 0.0 L’) / (Real.fromInt (List.length L’))
val title = (StringCvt.padLeft #" " 20 "array size")
^ (StringCvt.padLeft #" " 20 "time in cunit")
^ (StringCvt.padLeft #" " 20 "C/nlogn")
^ "\n"
fun formatReal a = StringCvt.padLeft #" " 20 (Real.fmt (StringCvt.FIX (SOME 8)) a)
fun printLine (n,a,c) =
let
val ns = StringCvt.padLeft #" " 20 (Int.toString n)
val sa = StringCvt.padLeft #" " 20 (Int.toString (Real.floor (real a * 1000.0/ c)))
val sc = formatReal c
in
print (ns ^ sa ^ sc ^ "\n")
end
val C = Real.fmt (StringCvt.FIX (SOME 2)) av
in
(print title;
map printLine L’;
print "------------------------------------------------------------\n";
print (" avarage" ^ (formatReal av) ^ "\n");
print ("The estimated sort time function: T(n) = " ^ C ^ " n log(n)\n"))
end
fun normalEvalSort L = evalSortN (evalCompare L) L
以下にSML#でのテスト例を示す。
# normalEvalSort [1000000, 10000000, Array.maxLen div 4];
array size time in cunit C/nlogn
1000000 236268 7.43223684
10000000 2756460 7.62717282
67108863 20683151 7.75259017
------------------------------------------------------------
avarage 7.60399994
The estimated sort time function: T(n) = 7.60 n log(n)
val it = () : unit