> Ralf, could I
> ask you to run my code below through your experiments (I don't have
> easy access to anything but hugs at the moment)?
Here we are ...
50000 | < | <= | > | >= | == | 1 2* |
1..100* | 2 1* | 100..1* | 1 2 2 1* | random
merge | 1.29 | 3.65 | 1.27 | 2.76 | 1.30 | 1.78 |
2.85 | 1.84 | 2.85 | 1.69 | 7.59
bottom-up | 0.96 | 2.24 | 0.87 | 2.04 | 0.96 | 1.77 |
2.86 | 1.78 | 2.86 | 1.57 | 7.89
heap | 8.87 | oo | 8.88 | oo | 6.17 | 7.44 |
8.76 | 7.31 | 8.62 | 7.13 | 9.82
pairing | 0.53 | 1.54 | 0.70 | 1.88 | 0.52 | 1.19 |
1.72 | 1.22 | 1.92 | 1.13 | 3.58
Jon's | 0.48 | 1.14 | 0.52 | 1.19 | 1.12 | 1.43 |
1.72 | 1.44 | 1.64 | 1.39 | 3.79
braun | 8.74 | 22.02 | 6.94 | 21.91 | 2.78 | 5.18 |
6.37 | 5.06 | 6.25 | 5.13 | 9.37
smooth | 0.13 | 0.28 | 0.13 | 2.98 | 0.11 | 1.60 |
1.39 | 1.57 | 1.29 | 1.55 | 7.67
splay | 0.39 | 0.81 | 0.37 | 1.87 | 0.40 | 0.85 |
2.23 | 0.84 | 1.75 | 0.76 | 5.35
oo = heap or stack overflow
1. | smooth | smooth | smooth | Jon's | smooth | splay |
smooth | splay | smooth | splay | pairing
2. | splay | splay | splay | splay | splay | pairing |
pairing | pairing | Jon's | pairing | Jon's
3. | Jon's | Jon's | Jon's | pairing | pairing | Jon's |
Jon's | Jon's | splay | Jon's | splay
4. | pairing | pairing | pairing | bottom-up | bottom-up | smooth |
splay | smooth | pairing | smooth | merge
5. | bottom-up | bottom-up | bottom-up | merge | Jon's | bottom-up |
merge | bottom-up | merge | bottom-up | smooth
6. | merge | merge | merge | smooth | merge | merge |
bottom-up | merge | bottom-up | merge | bottom-up
7. | braun | braun | braun | braun | braun | braun |
braun | braun | braun | braun | braun
8. | heap | (heap) | heap | (heap) | heap | heap |
heap | heap | heap | heap | heap
Times were taken on a *loaded* Sun Ultra-1 Sparcstation (run time
options -K32M -H32M, *minimum* out of five runs). I incorporated
Lennart's suggestion to `print the sum of the sorted list' as
well.
Splay trees perform quite well; second place? I am a bit sceptical
about their ability to adopt to presorted data. You said: (In fact, it
has been conjectured that splaySort is optimal with respect to any
reasonable notion of "presortedness".[2]) The non-strictly decreasing
sequence (>=) seems to be a hard nut to crack. Look at the following
table ...
100000 | < | <= | > | >= | == | 1 2* |
1..100* | 2 1* | 100..1* | 1 2 2 1* | random
merge | 3.50 | 8.80 | 2.77 | 8.95 | 3.00 | 6.53 |
13.10 | 6.52 | 12.56 | 6.49 | oo
bottom-up | 2.18 | 8.41 | 2.11 | 7.83 | 2.27 | 6.56 |
13.03 | 6.57 | 12.61 | 6.60 | oo
heap | oo | oo | oo | oo | 21.91 | oo |
oo | oo | oo | oo | oo
pairing | 1.45 | 3.48 | 2.30 | 7.50 | 1.56 | 2.54 |
4.07 | 2.46 | 4.54 | 2.51 | 11.15
Jon's | 1.19 | 3.00 | 1.14 | 3.14 | 2.21 | 3.00 |
3.58 | 2.96 | 3.60 | 2.87 | 8.56
braun | 26.33 | oo | 22.21 | oo | 7.80 | 14.71 |
21.17 | 14.74 | 21.08 | 14.73 | 23.67
smooth | 0.30 | 0.62 | 0.27 | 7.70 | 0.28 | 4.30 |
3.37 | 4.33 | 3.25 | 4.29 | oo
splay | 0.74 | 3.59 | 0.74 | 11.65 | 0.77 | 2.43 |
9.01 | 3.19 | 6.17 | 2.21 | 17.06
1. | smooth | smooth | smooth | Jon's | smooth | splay |
smooth | pairing | smooth | splay | Jon's
2. | splay | Jon's | splay | pairing | splay | pairing |
Jon's | Jon's | Jon's | pairing | pairing
3. | Jon's | pairing | Jon's | smooth | pairing | Jon's |
pairing | splay | pairing | Jon's | splay
4. | pairing | splay | bottom-up | bottom-up | Jon's | smooth |
splay | smooth | splay | smooth | braun
5. | bottom-up | bottom-up | pairing | merge | bottom-up | merge |
bottom-up | merge | merge | merge | (merge)
6. | merge | merge | merge | splay | merge | bottom-up |
merge | bottom-up | bottom-up | bottom-up |(bottom-up)
7. | braun | (heap) | braun | (heap) | braun | braun |
braun | braun | braun | braun | (heap)
8. | (heap) | (braun) | (heap) | (braun) | heap | (heap) |
(heap) | (heap) | (heap) | (heap) | (smooth)
Sorting with splay trees takes 11.65 for (>=) but only 0.74 for (>).
Ralf
