--- /dev/null
+# This file is part of NIT (http://www.nitlanguage.org).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Example implemented from "The computer Language Benchmarks Game" - Fannkuch-Redux
+# http://benchmarksgame.alioth.debian.org/
+#
+# Complete description of the fannkuch-redux :
+# https://benchmarksgame.alioth.debian.org/u64q/fannkuchredux-description.html#fannkuchredux
+module fannkuchredux is no_warning("missing-doc")
+
+import actors
+
+class FannkuchRedux
+ actor
+
+ var p: Array[Int] is noautoinit
+ var pp: Array[Int] is noautoinit
+ var count: Array[Int] is noautoinit
+
+ fun print_p do
+ for i in [0..p.length[ do printn p[i] + 1
+ print ""
+ end
+
+ fun first_permutation(idx: Int) do
+ for i in [0..p.length[ do p[i] = i
+
+ var i = count.length - 1
+ while i > 0 do
+ var d = idx / fact[i]
+ count[i] = d
+ idx = idx % fact[i]
+
+ p.copy_to(0, i+1, pp, 0)
+
+ for j in [0..i] do
+ if j + d <= i then
+ p[j] = pp[j+d]
+ else
+ p[j] = pp[j+d-i-1]
+ end
+ end
+ i -= 1
+ end
+ end
+
+ fun next_permutation do
+ var first = p[1]
+ p[1] = p[0]
+ p[0] = first
+
+ var i = 1
+ count[i] += 1
+ while count[i] > i do
+ count[i] = 0
+ i += 1
+
+ p[0] = p[1]
+ var next = p[0]
+
+ for j in [1..i[ do p[j] = p[j+1]
+ p[i] = first
+ first = next
+
+ count[i] += 1
+ end
+ end
+
+ fun count_flips: Int do
+ var flips = 1
+ var first = p[0]
+ if p[first] != 0 then
+ p.copy_to(0, pp.length, pp, 0)
+ loop
+
+ flips += 1
+ var lo = 1
+ var hi = first - 1
+ while lo < hi do
+ var t = pp[lo]
+ pp[lo] = pp[hi]
+ pp[hi] = t
+ lo += 1
+ hi -= 1
+ end
+ var t = pp[first]
+ pp[first] = first
+ first = t
+
+ if pp[first] == 0 then break
+ end
+ end
+ return flips
+ end
+
+ fun run_task(task: Int) do
+ var idx_min = task * chunk_sz
+ var idx_max = fact[n].min(idx_min + chunk_sz)
+
+ first_permutation(idx_min)
+
+ var maxflips = 1
+ var chk_sum = 0
+
+ var i = idx_min
+ loop
+ if p[0] != 0 then
+ var flips = count_flips
+ maxflips = maxflips.max(flips)
+ if i % 2 == 0 then
+ chk_sum += flips
+ else
+ chk_sum += -flips
+ end
+ end
+
+ i += 1
+ if i == idx_max then break
+ next_permutation
+ end
+
+ max_flips[task] = maxflips
+ chk_sums[task] = chk_sum
+ end
+
+ fun run do
+ p = new Array[Int].with_capacity(n)
+ for i in [0..n[ do p.add(0)
+ pp = new Array[Int].with_capacity(n)
+ for i in [0..n[ do pp.add(0)
+ count = new Array[Int].with_capacity(n)
+ for i in [0..n[ do count.add(0)
+
+ var task = 0
+ loop
+ task = task_id.get_and_increment
+ if task < n_tasks then
+ run_task(task)
+ else
+ break
+ end
+ end
+ end
+end
+
+redef class Sys
+ var n_chunks = 150
+ var chunk_sz: Int is noautoinit
+ var n_tasks: Int is noautoinit
+ var n: Int is noautoinit
+ var fact: Array[Int] is noautoinit
+ var max_flips: Array[Int] is noautoinit
+ var chk_sums: Array[Int] is noautoinit
+ var task_id = new AtomicInt(0)
+ var nb_actors = 8
+end
+
+fun print_result(n, res, chk: Int) do
+ print chk.to_s + "\nPfannfuchen(" + n.to_s + ") = " + res.to_s
+
+end
+
+if args.is_empty then
+ n = 7
+else
+ n = args[0].to_i
+end
+
+fact = new Array[Int].with_capacity(n+1)
+fact[0] = 1
+for i in [1..n] do fact.add(fact[i-1] * i)
+
+chunk_sz = (fact[n] + n_chunks - 1) / n_chunks
+n_tasks = (fact[n] + chunk_sz - 1) / chunk_sz
+max_flips = new Array[Int].with_capacity(n_tasks)
+for i in [0..n_tasks[ do max_flips.add(0)
+chk_sums = new Array[Int].with_capacity(n_tasks)
+for i in [0..n_tasks[ do chk_sums.add(0)
+
+var actors = new Array[FannkuchRedux].with_capacity(8)
+for i in [0..nb_actors[ do
+ var a = new FannkuchRedux
+ actors.add(a)
+ a.async.run
+end
+
+for i in [0..nb_actors[ do
+ actors[i].async.terminate
+ actors[i].async.wait_termination
+end
+
+var res = 0
+for i in max_flips do res = res.max(i)
+
+var chk = 0
+for i in chk_sums do
+ chk += i
+end
+
+print_result(n, res, chk)
nitlanguage / nit.git / commitdiff