Permutations
The purpose of this page is to analyse the performance of our algorithms, especially with regard to the differences between the array and the linked list version.
In all cases, the programs were compiled and executed on an Intel 166mhz pentium processor with 32MB RAM, running Linux kernel 2.2.5-15 with the EGCS compiler version 2.95.2 with the -O3 optimisation flag set.
Because outputting data to the screen is actually quite resource intensive, two sets of performance data are provided, one where each permutation is output as it is calculated, and one where no permutations are ever output.
Executable size
| Version | Size (KB) |
|---|---|
| Array version | 14.256 |
| Linked list | 14.831 |
The array version is slightly smaller in executable size, which is not surprising given how much more concise the source code is.
Performance (with output)
| Invocation | Permutations | Array (secs) | Linked list (secs) |
|---|---|---|---|
./perm 1 | 1 | - | - |
./perm 2 | 2 | - | - |
./perm 3 | 6 | - | - |
./perm 4 | 24 | - | - |
./perm 5 | 120 | - | - |
./perm 6 | 720 | 0.05 | 0.06 |
./perm 7 | 5,040 | 0.36 | 0.45 |
./perm 8 | 40,320 | 2.97 | 3.68 |
./perm 9 | 362,880 | 27.64 | 34.36 |
The linked list version is slower in each case, but the slowness of the output routines are masking the real difference in performance.
Performance (no output)
| Invocation | Permutations | Array (secs) | Linked list (secs) | A : L |
|---|---|---|---|---|
./perm 1 | 1 | - | - | - |
./perm 2 | 2 | - | - | - |
./perm 3 | 6 | - | - | - |
./perm 4 | 24 | - | - | - |
./perm 5 | 120 | - | - | - |
./perm 6 | 720 | - | - | - |
./perm 7 | 5,040 | 0.015 | 0.08 | 18.75% |
./perm 8 | 40,320 | 0.12 | 0.64 | 18.75% |
./perm 9 | 362,880 | 1.06 | 5.87 | 18.06% |
./perm 10 | 3,628,800 | 10.61 | 59.27 | 17.90% |
./perm 11 | 39,916,800 | 116.61 | 661.73 | 17.62% |
Here we can see that the array version is much faster, by over five times. This may be surprising, given that the main operations are inserting and removing data items, operations that linked lists are generally considered to be more efficient with (as the rest of the list does not have to be shifted backwards or forwards one by one).
We can explain this phenomena by noting that the lists we are using are actually quite small, no more than 11 elements in the tests above. It therefore seems that at these levels, the performance lost by having to shift array elements when inserting and deleting are more than made up for by the reduced number of processor steps in the rest of the array algorithm, including the fact that we don't have to continually ask the operating system for memory.
We may postulate, therefore, that at higher number of items, the linked list version will become relatively quicker. This is supported by the above data, which shows that despite the array version being five times faster, as we increase the number of items its performance advantage becomes gradually smaller.
This example shows that optimisation involves choosing algorithms
with careful regard to the type and amount of processing we are going
to be doing, and that optimisation of our algorithm is usually (though
not always) far more important than micro-optimisation of the "is
++count faster than count++?" variety.