[Tutor] fast list traversal
kent37 at tds.net
Thu Oct 30 21:05:13 CET 2008
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.
More information about the Tutor