|[47 earlier articles]|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? firstname.lastname@example.org (James Kanze US/ESC 60/3/141 #40763) (1996-03-25)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? email@example.com (1996-03-25)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? firstname.lastname@example.org (1996-03-25)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? email@example.com (1996-03-27)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? firstname.lastname@example.org (1996-03-31)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? email@example.com (R. Edward Nather) (1996-04-02)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? firstname.lastname@example.org (1996-04-02)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? email@example.com (1996-04-06)|
|Re: C code .vs. Assembly code for Microcontrollers/DSPs ? firstname.lastname@example.org (1996-04-10)|
|From:||email@example.com (Richard A. O'Keefe)|
|Date:||2 Apr 1996 23:47:28 -0500|
|Organization:||Comp Sci, RMIT, Melbourne, Australia|
|References:||96-03-006 96-03-139 96-03-218|
firstname.lastname@example.org (Scott A. Berg) writes:
>Well in general I agree, but no one seems to have covered the all too
>common dead end. Suppose you want to sort a list of a few hundred
>seemingly random integers (no special properties to exploit like being
>generated in almost sorted order) and you are already using quicksort
>(or some other O(n log n) algorithm) and it's still too slow. There
>ARE no faster algorithms and diddling with the code to squeeze a few
>constants can make the difference.
Wrong. Being integers is a special property, and there ARE faster
algorithms, including radix sort (for *fixed* integer sizes it is O(N)
and the cross-over point for when it's better than quicksort is
typically about 100) and bucket sort (which is O(N) average time and
O(NlgN) worst case, and quite easy to program).
If I were in that kind of dead end, I'd turn around and say "hmm,
where did these integers come from? Can I change the code that
>Besides, I've rarely run into the need for such a distinct function as
>a list sort or a string search or some other "classroom example"
>algorithm, and deriving minimal big-oh algorithms is rarely a pastime
I have seen "industrial" code using an O(N**3) algorithm when an
O(N.lgN) algorithm is known. I have seen "industrial" code failing to
take advantage of 'modern' data structures like splay trees or skip
lists when they could have been used. Even more surprising, I have
seen "industrial" code that failed to exploit basic ideas like
software caching and batching.
>1) There will always be a need for assembly language bit-jocks, but
>both the demand and the supply pool will get smaller.
As I don't expect the 8051 family to go away any time soon, I have to agree.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.
Return to the
Search the comp.compilers archives again.