Re: C code .vs. Assembly code for Microcontrollers/DSPs ?

sberg@camtronics.com (Scott A. Berg) writes:
>So these are 32 or even 64 bit integers or even floating point
>numbers, randomly and uniformly spread across the entire range. How
>many buckets is this? Or perhaps you're using different names for
>sorts than I'm used to seeing.


The idea of bucket sort is


(1) In one pass using 3N/2 comparisons, find Min and Max.
(2) Allocate N buckets (or some other number reasonably close to N)
(3) In one pass move each element X[i] to bucket number
floor( (X[i]-Min)/(Max-Min) * N )
(4) Sort each bucket using some other algorithm; the worst case bucket
        size is N, so if you use an O(NlgN) algorithm on the buckets, the
        worst overall cost is O(NlgN)
(5) Concatenate the buckets.


If the input is random and uniformly distributed, that's a very _good_
case for bucket sort, and you get O(N) time. If the numbers are
spread across the _entire_ range, you have to be a bit clever in step
(3) to avoid overflow, but it's still not enormously complicated.


>Alas, so have I. Perhaps we should spend less time attempting to
>create the ultimate compiler and more time teaching practitioners how
>to use what they've got! Besides, if you see these sort of problems
>with the applications, why do you think the compilers are any better?


I don't. Compilers are notorious for running into extremely hard
problems. I've heard of one compiler spending a week on one 200-line
function. I have more reasons than one for compiling my code with
every compiler I have available. (I compile Fortran with f77 and f2c;
I compile C with cc, gcc, and lcc; and so on.)


--
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.