[Tutor] fast list traversal

[Shawn Milochik]

On Thu, Oct 30, 2008 at 4:05 PM, Kent Johnson <kent37 at tds.net> wrote:
> 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
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>



I just ran a very crude test.

Results: Lists load more quickly but iterate more slowly. Dictionaries
take longer to load but iteration takes about half the time.

Sample output:



Results for 9999999 iterations:
	List:
		Load: 4.75 seconds
		Process: 6.64 seconds

	Dictionary:
		Load: 7.54 seconds
		Process: 3.31 seconds

Comparison:
	List loads 0.63 times the speed of a dictionary.
	List processes loads 2.00 times the speed of a dictionary.







Results for 7654321 iterations:
	List:
		Load: 3.29 seconds
		Process: 4.72 seconds

	Dictionary:
		Load: 5.47 seconds
		Process: 2.41 seconds

Comparison:
	List loads 0.60 times the speed of a dictionary.
	List processes loads 1.96 times the speed of a dictionary.







Code:


#!/usr/bin/env python


import time

the_dict = {}
the_list = []

iter_num = 7654321


fill_list_time = time.time()

for x in range(iter_num):
    the_list.append(x)

fill_list_time = time.time() - fill_list_time

fill_dict_time = time.time()

for x in range(iter_num):
    the_list.append(x)
    the_dict[x] = 0

fill_dict_time = time.time() - fill_dict_time





proc_list_time = time.time()

for thing in the_list:

    thing = thing * 2

proc_list_time = time.time() - proc_list_time


proc_dict_time = time.time()

for thing in the_dict:

    thing = thing * 2

proc_dict_time = time.time() - proc_dict_time


print "Results for %d iterations:" % iter_num
print "\tList:"
print "\t\tLoad: %.2f seconds" % fill_list_time
print "\t\tProcess: %.2f seconds" % proc_list_time
print
print "\tDictionary:"
print "\t\tLoad: %.2f seconds" % fill_dict_time
print "\t\tProcess: %.2f seconds" % proc_dict_time
print
print "Comparison: "
print "\tList loads %.2f times the speed of a dictionary." %
(fill_list_time / fill_dict_time)
print "\tList processes loads %.2f times the speed of a dictionary." %
(proc_list_time / proc_dict_time)