1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Example implemented from "The computer Language Benchmarks Game" - Fannkuch-Redux
16 # http://benchmarksgame.alioth.debian.org/
18 # Complete description of the fannkuch-redux :
19 # https://benchmarksgame.alioth.debian.org/u64q/fannkuchredux-description.html#fannkuchredux
20 module fannkuchredux
is example
, no_warning
("missing-doc")
27 var p
: Array[Int] is noautoinit
28 var pp
: Array[Int] is noautoinit
29 var count
: Array[Int] is noautoinit
32 for i
in [0..p
.length
[ do printn p
[i
] + 1
36 fun first_permutation
(idx
: Int) do
37 for i
in [0..p
.length
[ do p
[i
] = i
39 for i
in [0..count
.length
[.reverse_iterator
do
44 p
.copy_to
(0, i
+1, pp
, 0)
46 for j
in [0..i
] do p
[j
] = if j
+ d
<= i
then pp
[j
+d
] else pp
[j
+d-i-1
]
50 fun next_permutation
do
64 for j
in [1..i
[ do p
[j
] = p
[j
+1]
72 fun count_flips
: Int do
76 p
.copy_to
(0, pp
.length
, pp
, 0)
77 while pp
[first
] != 0 do
96 fun run_task
(task
: Int) do
97 var idx_min
= task
* chunk_sz
98 var idx_max
= fact
[n
].min
(idx_min
+ chunk_sz
)
100 first_permutation
(idx_min
)
105 for i
in [idx_min
..idx_max
[ do
107 var flips
= count_flips
108 maxflips
= maxflips
.max
(flips
)
109 chk_sum
+= if i
% 2 == 0 then flips
else -flips
111 if i
+ 1 != idx_max
then next_permutation
114 max_flips
[task
] = maxflips
115 chk_sums
[task
] = chk_sum
119 p
= new Array[Int].with_capacity
(n
)
120 for i
in [0..n
[ do p
.add
(0)
121 pp
= new Array[Int].with_capacity
(n
)
122 for i
in [0..n
[ do pp
.add
(0)
123 count
= new Array[Int].with_capacity
(n
)
124 for i
in [0..n
[ do count
.add
(0)
128 task
= task_id
.get_and_increment
129 if task
< n_tasks
then run_task
(task
) else break
136 var chunk_sz
: Int is noautoinit
137 var n_tasks
: Int is noautoinit
138 var n
: Int is noautoinit
139 var fact
: Array[Int] is noautoinit
140 var max_flips
: Array[Int] is noautoinit
141 var chk_sums
: Array[Int] is noautoinit
142 var task_id
= new AtomicInt(0)
146 fun print_result
(n
, res
, chk
: Int) do
147 print chk
.to_s
+ "\nPfannfuchen(" + n
.to_s
+ ") = " + res
.to_s
151 n
= if args
.is_empty
then 7 else args
[0].to_i
153 fact
= new Array[Int].with_capacity
(n
+1)
155 for i
in [1..n
] do fact
.add
(fact
[i-1
] * i
)
157 chunk_sz
= (fact
[n
] + n_chunks
- 1) / n_chunks
158 n_tasks
= (fact
[n
] + chunk_sz
- 1) / chunk_sz
159 max_flips
= new Array[Int].with_capacity
(n_tasks
)
160 for i
in [0..n_tasks
[ do max_flips
.add
(0)
161 chk_sums
= new Array[Int].with_capacity
(n_tasks
)
162 for i
in [0..n_tasks
[ do chk_sums
.add
(0)
164 var actors
= new Array[FannkuchRedux].with_capacity
(nb_actors
)
165 for i
in [0..nb_actors
[ do
166 var a
= new FannkuchRedux
171 for i
in [0..nb_actors
[ do
172 actors
[i
].async
.terminate
173 actors
[i
].async
.wait_termination
177 for i
in max_flips
do res
= res
.max
(i
)
184 print_result
(n
, res
, chk
)