comparing two lists and returning "position"

Charles Sanders C.delete_this.Sanders at BoM.GOv.AU
Mon Jun 25 11:41:00 CEST 2007


hiro wrote:
> bare in mind that I have a little over 10 million objects in my list
> (l2) and l1 contains around 4 thousand
> objects.. (i have enough ram in my computer so memory is not a
> problem)

Glad to see you solved the problem with the trailing space.

Just one minor point, I did say

 > or probably less efficiently ...

As far as i know, my suggestion's running time is
proportional to len(l1)*len(l2), which gets quite
big for your case where l1 and l2 are large lists.

If I understand how python dictionaries work, Paul Rubin's
suggestion

 > from itertools import izip, count
 > pos = map(dict(izip(l2, count())).__getitem__, l1)

or the (I think) approximately equivalent

from itertools import izip, count
d = dict(izip(l2,count()))
pos = [ d[i] for i in l1 ]

or the more memory intensive

d = dict(zip(l2,range(len(l2))))
pos = [ d[i] for i in l1 ]

should all take take running time proportional to
(len(l1)+len(l2))*log(len(l2))

For len(l1)=4,000 and len(l2)=10,000,000
Paul's suggestion is likely to take
about 1/100th of the time to run, ie
be about 100 times as fast. I was trying
to point out a somewhat clearer and simpler
(but slower) alternative.

Charles



More information about the Python-list mailing list