[racket] [BULK] Re: Looking for feedback on code style

On 13/09/10 23:19, Prabhakar Ragde wrote:
> One of the things that irritates me about a conventional algorithms
> course is that the underlying model is so fuzzy. When we talk about an
> input of size n, we are really assuming a RAM model with word size c log
> n for some constant c big enough to implement our algorithm without too
> much pain, even though no real machine has an arbitrarily expandable
> word size.


Too true. I explain to my students this confusion. Even if the word
length were expandable, if you look at the way the address is decoded to
access the ram - ram access takes O (log n) time, where n is the RAM
size supported by the word length. And if you have some kind of memory
hierarchy (cache and RAM, or cache, RAM and disk) then things are
definitely not really going to be O(1) when you might naively expect
then to be, when you do some serious scaling.

Often when you look at smart solutions that appear to get rid of a log n
factor, (example: radix sort) it is a cheat and when you really scale up
the problem that log n factor creeps back in again.

But, on the other hand, O(log n) is, for most practical purposes, very
close to O(1), so why worry?


 And we're not very clear, in these days of powerful languages
> with powerful libraries, about what exactly can be assumed to take O(1)
> time. --PR


Also too true. Woe befall anyone who tries to write array algorithms in
Python, then time them to see if they get the same performance answers
as the ones "in the book". You get some very funny timings, because
Python arrays are not so simple. Or they weren't, the last time I tried
this.


-- 
Chris Stephenson
cs at cs.bilgi.edu.tr