From: John Cowan (jcowan@reutershealth.com)
Date: Thu Oct 16 2003 - 13:35:17 CST
Asmus Freytag scripsit:
> Normalization has mapping and reordering phases. The reordering is O(n
> log(n)) where n is the length of a combining sequence. Realistically that's
> a small number.
I tried sorting 100,000,000 runs of random bytes where each run has a
randomly chosen length from 1 to 5 with a naive quicksort and a naive
bubblesort. Although quicksort is O(N log N) and bubblesort is O(N^2),
the bubblesort was just a hair faster, 220 seconds on my machine vs. 225
seconds, and the code is a lot shorter and easier to get right. A few
experiments suggest that these results are linear in the number of runs,
which is not surprising. Not invoking the sort algorithm when N = 1,
the most trivial possible optimization hack, improves the advantages of
bubblesort substantially, making the running time 206 seconds vs. 252
seconds. A 20% improvement, easily achieved, is not to be sneezed at.
YMMV.
--
I don't know half of you half as well John Cowan
as I should like, and I like less than half jcowan@reutershealth.com
of you half as well as you deserve. http://www.ccil.org/~cowan
--Bilbo http://www.reutershealth.com
This archive was generated by hypermail 2.1.5 : Thu Jan 18 2007 - 15:54:24 CST