[Tutor] fast list traversal

[Shawn Milochik]

On Thu, Oct 30, 2008 at 6:06 PM, wesley chun <wescpy at gmail.com> wrote:
> based on the all the performance questions, i would say agree that
> dictionary access is faster than lists (hashes exist cuz they're fast)
> but they use up more memory, as shown in shawn's numbers. also, one of
> the reasons why slots was added to classes was because the attribute
> dictionary began to impact memory (when creating many instances), so
> converting that to __slots__ list of attributes instead made it more
> conservative of resources.
>
> thus, i would suggest using sets instead. if the data doesn't change,
> then frozensets. a for-loop thru sets would be very fast; and in
> Python 3.0, you can use *set comprehensions* too. :-)
>
> shawn, do you have time to run some numbers for sets and frozensets?
>
> anyway, just a suggestion...
> -wesley


They seem pretty similar. Here are two tests (code follows). Perhaps I
could have loaded them differently and it would have made more of a
difference. In this case I just made a list and populated the sets
from it.

Results for 9999999 iterations:
	Set:
		Load: 1.24 seconds
		Process: 4.43 seconds

	Frozenset:
		Load: 0.96 seconds
		Process: 4.09 seconds

Comparison:
	Set loads 1.30 times the speed of a frozenset.
	Set processes loads 1.08 times the speed of a frozenset.





Results for 9999999 iterations:
	Set:
		Load from list: 0.89 seconds
		Process: 3.72 seconds

	Frozenset:
		Load from list: 0.94 seconds
		Process: 4.67 seconds

Comparison:
	Set loads 0.94 times the speed of a frozenset.
	Set processes loads 0.80 times the speed of a frozenset.


Results for 7654321 iterations:
	Set:
		Load from list: 0.81 seconds
		Process: 2.52 seconds

	Frozenset:
		Load from list: 0.76 seconds
		Process: 2.52 seconds

Comparison:
	Set loads 1.07 times the speed of a frozenset.
	Set processes loads 1.00 times the speed of a frozenset.






#!/usr/bin/env python


import time

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_frozenset_time = time.time()
the_frozenset = frozenset(the_list)
fill_frozenset_time = time.time() - fill_frozenset_time


fill_set_time = time.time()
the_set = set(the_list)
fill_set_time = time.time() - fill_set_time



proc_set_time = time.time()

for thing in the_set:

    thing = thing * 2

proc_set_time = time.time() - proc_set_time


proc_frozenset_time = time.time()

for thing in the_frozenset:

    thing = thing * 2

proc_frozenset_time = time.time() - proc_frozenset_time


print "Results for %d iterations:" % iter_num
print "\tSet:"
print "\t\tLoad from list: %.2f seconds" % fill_set_time
print "\t\tProcess: %.2f seconds" % proc_set_time
print
print "\tFrozenset:"
print "\t\tLoad from list: %.2f seconds" % fill_frozenset_time
print "\t\tProcess: %.2f seconds" % proc_frozenset_time
print
print "Comparison: "
print "\tSet loads %.2f times the speed of a frozenset." %
(fill_set_time / fill_frozenset_time)
print "\tSet processes loads %.2f times the speed of a frozenset." %
(proc_set_time / proc_frozenset_time)