Most efficient solution?
Alexandre Fayolle
alf at leo.logilab.fr
Mon Jul 16 11:37:07 EDT 2001
On 16 Jul 2001 11:02:12 -0400, Alex <new_name at mit.edu> wrote:
>
>> You may get some speedup by making B a dictionary, and using has_key()
>> to see if the word is there. This should get you a O(log(n)) instead
>> of O(n) inside the loop. To gain further performance, use filter to
>> skim A.
>
>What's n, here? This looks linear in the length of A, and constant time
>in the number of unique elements in B, to me.
I was referring to the inner loop. n is the number of elements in B
(or of keys in C). 'item in B' is O(n), and 'C.has_key(item)' is O(log(n)).
You still have to multiply by len(A) for the whole program.
Alexandre Fayolle
--
LOGILAB, Paris (France).
http://www.logilab.com http://www.logilab.fr http://www.logilab.org
Narval, the first software agent available as free software (GPL).
More information about the Python-list
mailing list