On Saturday, 6 February 2016 at 13:06:37 UTC, Andrei Alexandrescu
wrote:
Could you please add two simple calculations? Assuming uniform
random distribution of data, compute the average number of
swaps as a weighted average of orderings. Also, show the number
of lines (one test or one swap per line) as a proxy for
generated code size. That should provide good insights.
This now prints the numbers of comparison and swap lines and
computes the average numbers of swaps. In addition, it also runs
the same tests for permutations of 5 elements some of which might
be equal (an example of such permutation would be [1, 2, 0, 2,
3], on the other hand [1, 2, 0, 2, 4] should not be included
since it is identical). However, in this case the average number
of swaps is perhaps not so meaningful.
http://dpaste.dzfl.pl/2012caf872ec
Output:
testing 'partition5a'
Code: comparisons = 63, swaps = 107, total = 170
With all orderings of distinct elements:
0 swaps: 4 instances
1 swaps: 32 instances
2 swaps: 68 instances
3 swaps: 16 instances
Average number of swaps: 1.8
With all orderings of potentially nondistinct elements:
Error, not idempotent: [0, 0, 0, 0, 0] => [0, 0, 0, 0, 0]
testing 'partition5b'
Code: comparisons = 17, swaps = 21, total = 38
With all orderings of distinct elements:
0 swaps: 4 instances
1 swaps: 20 instances
2 swaps: 42 instances
3 swaps: 40 instances
4 swaps: 14 instances
Average number of swaps: 2.33333
With all orderings of potentially nondistinct elements:
0 swaps: 36 instances
1 swaps: 122 instances
2 swaps: 200 instances
3 swaps: 146 instances
4 swaps: 37 instances
Average number of swaps: 2.04806
testing 'partition5c'
Code: comparisons = 10, swaps = 12, total = 22
With all orderings of distinct elements:
0 swaps: 4 instances
1 swaps: 14 instances
2 swaps: 25 instances
3 swaps: 30 instances
4 swaps: 26 instances
5 swaps: 16 instances
6 swaps: 5 instances
Average number of swaps: 3.06667
With all orderings of potentially nondistinct elements:
0 swaps: 36 instances
1 swaps: 92 instances
2 swaps: 130 instances
3 swaps: 138 instances
4 swaps: 92 instances
5 swaps: 42 instances
6 swaps: 11 instances
Average number of swaps: 2.60628
testing 'partition5d'
Code: comparisons = 7, swaps = 8, total = 15
With all orderings of distinct elements:
0 swaps: 4 instances
1 swaps: 14 instances
2 swaps: 24 instances
3 swaps: 29 instances
4 swaps: 26 instances
5 swaps: 16 instances
6 swaps: 6 instances
7 swaps: 1 instances
Average number of swaps: 3.13333
With all orderings of potentially nondistinct elements:
0 swaps: 36 instances
1 swaps: 100 instances
2 swaps: 128 instances
3 swaps: 133 instances
4 swaps: 94 instances
5 swaps: 39 instances
6 swaps: 10 instances
7 swaps: 1 instances
Average number of swaps: 2.57486
testing 'partition5e'
Code: comparisons = 6, swaps = 8, total = 14
With all orderings of distinct elements:
0 swaps: 4 instances
1 swaps: 12 instances
2 swaps: 19 instances
3 swaps: 25 instances
4 swaps: 25 instances
5 swaps: 18 instances
6 swaps: 11 instances
7 swaps: 5 instances
8 swaps: 1 instances
Average number of swaps: 3.53333
With all orderings of potentially nondistinct elements:
0 swaps: 36 instances
1 swaps: 88 instances
2 swaps: 100 instances
3 swaps: 123 instances
4 swaps: 106 instances
5 swaps: 53 instances
6 swaps: 25 instances
7 swaps: 9 instances
8 swaps: 1 instances
Average number of swaps: 2.89649
