[Tutor] fast list traversal

[Kent Johnson]

On Thu, Oct 30, 2008 at 2:46 PM, Shawn Milochik <Shawn at milochik.com> wrote:

> You might try using dictionaries instead. I've had phenomenal speed
> gains by switching lists to dictionaries before, although that may
> have had more to do with the fact that I needed to access certain
> values, rather than iterating through them in sequential order like
> you're doing.

Looking up individual values (i.e. testing for membership) is much
faster for dicts and sets than for lists. Problems of the form

for item in long_list_1:
  if item in long_list_2:
    do something with item

will be much faster if long_list_2 is changed to a set. This is
because the complexity goes from O(len(long_list_1) *
len(long_list_2)) to O(len(long_list_1)).

Iterating is probably faster on lists, certainly it is not
"phenomenally" faster to iterate a dict than a list.

Kent