[Tutor] speeding code along [lists and dictionaries are fast]
Danny Yoo
dyoo@hkn.eecs.berkeley.edu
Sun Nov 17 23:30:02 2002
On Mon, 18 Nov 2002, Thomi Richards wrote:
> > speedup would be to cache the results of sqrt() so if you compute the
> > same values over and over it won't take as long. But in the end it is
> > the
>
> i did think about that, but decided that in the end it would probably
> take just as long to lookup 3 values in a list of values (by the end of
> the image, this list would be thousands long anyway), as it would to do
> the math.... ahh well...
Lists and dictionary lookup is nearly instantaneous: we use them to trade
time with space. That is, list lookup should take a constant amount of
time, regardless of how large our lists are.
(Well, as long as our lists aren't so large that the operating system
needs to juggle virtual memory. *grin*)
That's one big reason why lists are so good. This idea of constant lookup
is not intuitive to people, since we imagine ourselves marching through a
list to get at a result, and our intuition tells us that physical distance
matters. But computers are very very good at lookup: when given an index,
they don't march --- they take a flying leap!
If you use a caching approach to your problem; I think you'll be
pleasantly surprised with the results.