blob: 6a644c14b2762a2e4201aa91594e015eb7c5f32e (
plain)
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
/*
* This benchmark has been ported from "The Computer Language Benchmarks Game" suite and slightly
* modified to fit the benchmarking framework.
*
* The original file is `fannkuchredux/fannkuchredux.java-2.java` from the
* archive available at
* http://benchmarksgame.alioth.debian.org/download/benchmarksgame-sourcecode.zip.
* See LICENSE file in the same folder (BSD 3-clause).
*
* The Computer Language Benchmarks Game
* http://benchmarksgame.alioth.debian.org/
*
* contributed by Isaac Gouy
* converted to Java by Oleg Mazurov
*/
/*
* Description: Indexed-access to tiny integer-sequence.
* Main Focus: TODO
*
*/
package org.linaro.benchmarks.benchmarksgame;
import org.openjdk.jmh.annotations.*;
import java.util.concurrent.TimeUnit;
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
// CHECKSTYLE.OFF: .*
public class fannkuchredux
{
public int fannkuch(int n) {
int[] perm = new int[n];
int[] perm1 = new int[n];
int[] count = new int[n];
int maxFlipsCount = 0;
int permCount = 0;
int checksum = 0;
for(int i=0; i<n; i++) perm1[i] = i;
int r = n;
while (true) {
while (r != 1){ count[r-1] = r; r--; }
for(int i=0; i<n; i++) perm[i] = perm1[i];
int flipsCount = 0;
int k;
while ( !((k=perm[0]) == 0) ) {
int k2 = (k+1) >> 1;
for(int i=0; i<k2; i++) {
int temp = perm[i]; perm[i] = perm[k-i]; perm[k-i] = temp;
}
flipsCount++;
}
maxFlipsCount = Math.max(maxFlipsCount, flipsCount);
checksum += permCount%2 == 0 ? flipsCount : -flipsCount;
// Use incremental change to generate another permutation
while (true) {
if (r == n) {
return maxFlipsCount;
}
int perm0 = perm1[0];
int i = 0;
while (i < r) {
int j = i + 1;
perm1[i] = perm1[j];
i = j;
}
perm1[r] = perm0;
count[r] = count[r] - 1;
if (count[r] > 0) break;
r++;
}
permCount++;
}
}
// CHECKSTYLE.ON: .*
private static final int PREDEFINED_N_PANCAKES = 7;
@Benchmark
public void jmhTimeFannkuchRedux() {
fannkuch(PREDEFINED_N_PANCAKES);
}
}
|
