1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
// Merge sort
MS(ret) >< [] => ret~[];
MS(ret) >< x:xs => MS_tail(ret, x)~xs;
MS_tail(ret, n) >< [] => ret~(*R)[n];
MS_tail(ret, int n) >< x:xs =>
// MS(a)~left, MS(b)~right, Append(ret,a)~b,
// Split(0, left,right) ~ (n:x:xs);
MS(a)~left, MS(b)~right, Append(ret,a)~b,
(*L)Split(left,right) ~ (*R)(n:x:xs);
/*
Splitn(int flag, a, b) >< [] => a~[], b~[];
Splitn(int flag, a, b) >< (int y):ys
| flag==0 => b~(*R)(y:cnt), (*L)Splitn(1, a, cnt)~ys
| _ => a~(*R)(y:cnt), (*L)Splitn(0, cnt, b)~ys;
Split(a,b) >< x:xs => Splitn(0,a,b)~x:xs;
*/
Split(a,b) >< [] => a~[], b~[];
Split(a,b) >< x:xs => a~(x:cntl), (*L)Split(b,cntl)~xs;
// この実験から、Merge は悪くないことがわかる。
// Part でも -t 5 6 7 順に速くなる。
// つまり、Split が悪いと言える。
/*
MS_tail(ret, n) >< [] => ret~(*R)[n];
MS_tail(ret, n) >< x:xs =>
MS(a)~left, MS(b)~right, Merge(ret,b)~a,
(*L)Split(left,right) ~ (*R)(n:x:xs);
*/
Merge(ret, snd) >< [] => ret~snd;
Merge(ret, snd) >< x:xs => (*L)MergeCC(ret, x, xs)~snd;
MergeCC(ret, int y, ys) >< [] => ret~(*R)(y:ys);
MergeCC(ret, int y, ys) >< (int x):xs
| x <= y => ret~(x:cnt), (*L)MergeCC(cnt, y, ys) ~ xs
| _ => ret~(y:cnt), (*L)MergeCC(cnt, x, xs) ~ ys;
// ret~(*R)(x:cnt) less improvement
// *** I should make an option that outputs bytecodes to a file. ***
// *** Then, I have to look the reason why
// *** ret~(*R)(x:cnt), MergeCC(cnt, y, ys) ~ xs becomes less improvement.
// left~cntr, (*L)Split(cntr,cntl)~xs, right~(x:cntl);
// This also make it less efficient.
const LIST_ELEM=1200000;
MkRandList(ret) >< (int n)
| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1)
where rd=rand(LIST_ELEM)
| _ => ret~[];
MkRandList(cnt)~(LIST_ELEM),
MS(ret)~cnt;
ret;
|
