R: unique items in lists

Remco Gerlich scarblac at pino.selwerd.nl
Wed Mar 28 10:28:52 CEST 2001


Bob Cannard <bob_cannard at mentor.com> wrote in comp.lang.python:
> > The dictionary method does one dictionary action for each word, and then it
> > does a dict.keys() which takes time proportional to each unique word.
> 
> I don't know how dictionaries are implemented, but hopefully they're
> a lot faster than that - one would expect a hash or tree implementation,
> giving a logarithmic run time for each lookup. A linear implementation
> would be an obvious cause of poor run time performance for Python
> generally.

Dictionaries are hashes, I'm assuming a dictionary setattr is about constant
time. The "dict.keys()" at the end must be linear, since its result is
linear...

-- 
Remco Gerlich



More information about the Python-list mailing list