9.9){ return number_format($d); }
elseif ($d>0.0){ return number_format($d,1); }
else { return " "; }
}
// PAGE ////////////////////////////////////////////////
MkMenuForm($Tests,$SelectedTest,$Langs,NULL);
$Row = $Tests[$SelectedTest];
$TestName = $Row[TEST_NAME];
$TestTag = $Row[TEST_TAG];
$TestLink = $Row[TEST_LINK];
list($Succeeded,$Failed,$Special,$Labels,$Ratios) = $Data;
unset($Data);
$first = 0;
$NString = 'N=?';
foreach($Succeeded as $d){
if ($d[DATA_TESTVALUE]>0){
$testValue = (double)$d[DATA_TESTVALUE];
$NString = 'N='.number_format($testValue);
break;
}
}
// BEWARE - Hard coded values - BEWARE
if ($TestName=='fasta'||$TestName=='k-nucleotide'||
$TestName=='reverse-complement'||$TestName=='regex-dna'){
if ($d[DATA_TESTVALUE] == 25000000) { $NString = '≈240MB '.$NString; }
elseif ($d[DATA_TESTVALUE] == 2500000) { $NString = '≈24MB '.$NString; }
elseif ($d[DATA_TESTVALUE] == 5000000) { $NString = '≈50MB '.$NString; }
elseif ($d[DATA_TESTVALUE] == 1000000) { $NString = '≈10MB '.$NString; }
elseif ($d[DATA_TESTVALUE] == 500000) { $NString = '≈5MB '.$NString; }
}
if ($TestName=='startup'){ $NString = ''; }
// Use the table column headers to emphasize the row sort order
$CPU_sort_td = '
sort | ';
$MEM_sort_td = '
sort | ';
$ELAPSED_sort_td = '
sort | ';
$GZBYTES_sort_td = '
sort | ';
if ($Sort=='fullcpu'){
$CPU_sort_td = '
| ';
$Chart_intro_1 = '
how many times slower';
$Chart_intro_2 = 'program was, compared to the fastest program';
} elseif ($Sort=='kb'){
$MEM_sort_td = '
| ';
$Chart_intro_1 = '
how many times more Memory';
$Chart_intro_2 = 'program used, compared to the program that used least Memory';
} elseif ($Sort=='elapsed'){
$ELAPSED_sort_td = '
| ';
$Chart_intro_1 = '
how many times slower';
$Chart_intro_2 = 'program was, compared to the fastest program';
} elseif ($Sort=='gz'){
$GZBYTES_sort_td = '
| ';
$Chart_intro_1 = '
how many times more Code';
$Chart_intro_2 = 'program used, compared to the program that used least Code';
}
if ($CanonicalPage){ echo '
'; }
?>
Each chart bar shows , one ↓ .
These are not the only programs that could be written. These are not the only compilers and interpreters. These are not the only programming languages.
Column × shows how many times more each program used compared to the benchmark program that used least.
diff program output N = 7 with this output file to check your program is correct before contributing.
We are trying to show the performance of various programming language implementations - so we ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.
For N = 7 programs should generate these permutations (40KB) - which, incidentally, seem to be in the same order as permutations generated by the Tompkins-Paige algorithm, see pages 150-151 Permutation Generation Methods Robert Sedgewick.
The fannkuch benchmark is defined by programs in Performing Lisp Analysis of the FANNKUCH Benchmark, Kenneth R. Anderson and Duane Rettig.
Each program should
- Take a permutation of {1,...,n}, for example: {4,2,1,5,3}.
- Take the first element, here 4, and reverse the order of the first 4 elements: {5,1,2,4,3}.
- Repeat this until the first element is a 1, so flipping won't change anything more: {3,4,2,1,5}, {2,4,3,1,5}, {4,2,3,1,5}, {1,3,2,4,5}.
- Count the number of flips, here 5.
- Keep a checksum
- checksum = checksum + (if permutation_index is even then flips_count else -flips_count)
- checksum = checksum + (toggle_sign_-1_1 * flips_count)
- Do this for all n! permutations, and record the maximum number of flips needed for any permutation.
The conjecture is that this maximum count is approximated by n*log(n) when n goes to infinity.
FANNKUCH is an abbreviation for the German word Pfannkuchen, or pancakes, in analogy to flipping pancakes.
Thanks to Oleg Mazurov for insisting on a checksum and providing this helpful description of the approach he took -