[Tutor] Simple way to compare Two lists

Stephen McInerney spmcinerney at hotmail.com
Fri Aug 17 05:53:58 CEST 2007


Jim  & Jaggo -

Dict lookup is (essentially) constant-time because the hashing function
computes which unique bucket a given entry will correspond to.
(Hashing functions are usually polynomials involving prime numbers.
Can assume that the computation of the hash value is constant-time)

So there is no linear table-walking in dict lookup.

Walking the shorter list will thus be faster in general, esp if M<<N.

It would be neat to code this example up and measure performance
using the standard timeit.Timer object
(does anyone have any code or package to generate GIF graphs with
logarithmic axes for N, based on timeit.Timer output? Maybe Matplotlib?)

If Jaggo could suggest us typical ranges for M,N in his application that
would help guide the discussion...  cases like M=10, N=10^6 will showcase 
this.

(I am real busy on another task I don't have time to do it right now)

PS What is the name of the author of the 'profiler' module?

Stephen

_________________________________________________________________
Puzzles, trivia teasers, word scrambles and more. Play for your chance to 
win! http://club.live.com/home.aspx?icid=CLUB_hotmailtextlink



More information about the Tutor mailing list