blob: 5b367882faa3256206acea01e09e6804707031ef (
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
/*
* This benchmark has been ported from "The Computer Language Benchmarks Game"
* suite and slightly modified to fit the benchmarking framework.
*
* The original file:
* https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/fannkuchredux-java-2.html
*
* The Computer Language Benchmarks Game
* https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
*
* contributed by Isaac Gouy
* converted to Java by Oleg Mazurov
*
* LICENSE: 3-Clause BSD
* https://benchmarksgame-team.pages.debian.net/benchmarksgame/license.html
*/
/*
* Description: Indexed-access to tiny integer-sequence.
* Main Focus: TODO
*
*/
package benchmarks.benchmarksgame;
// CHECKSTYLE.OFF: TypeName
public class fannkuchredux {
// CHECKSTYLE.ON: TypeName
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++;
}
}
private static final int PREDEFINED_N_PANCAKES = 7;
public void timeFannkuchRedux(int iters) {
for (int i = 0; i < iters; i++) {
fannkuch(PREDEFINED_N_PANCAKES);
}
}
public boolean verifyFannkuchRedux() {
int expected = 16;
int found = fannkuch(PREDEFINED_N_PANCAKES);
if (expected != found) {
System.out.println("ERROR: Expected " + expected + " but found " + found);
return false;
}
return true;
}
public static void main(String[] args) {
int rc = 0;
fannkuchredux obj = new fannkuchredux();
final long before = System.currentTimeMillis();
obj.timeFannkuchRedux(1100);
final long after = System.currentTimeMillis();
if (!obj.verifyFannkuchRedux()) {
rc++;
}
System.out.println("benchmarks/benchmarksgame/fannkuchredux: " + (after - before));
System.exit(rc);
}
}
|
