Re: Canonical equivalence in rendering: mandatory or recommended?

From: John Cowan (
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.


I don't know half of you half as well           John Cowan
as I should like, and I like less than half
of you half as well as you deserve.   

This archive was generated by hypermail 2.1.5 : Thu Jan 18 2007 - 15:54:24 CST