On Thu, Oct 30, 2008 at 4:05 PM, Kent Johnson <[EMAIL PROTECTED]> wrote: > On Thu, Oct 30, 2008 at 2:46 PM, Shawn Milochik <[EMAIL PROTECTED]> 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@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) _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor