operation complexities of lists and dictionaries

[xarnaudx]

hi,
i've just a simple question:
what are the time complexities of inserting / removing / checking if an
element is present in 1) a list and 2) a dictionary?
does anybody know?
thanks

[Caleb Hattingh]

Hi

Use the "timeit" module, like so:

from timeit import Timer
t = Timer('[i for i in range(10000)]') # The string is code to execute (for timing)
print t.timeit(100) # execute it 100 times and print the result

0.222389936447

I would appreciate it if you could present your results in this thread.
I have also been wondering about timings for simple operations.

Thanks
Caleb

[Steven D'Aprano]

On Wed, 29 Mar 2006 09:38:05 -0800, xa******@gmail.com wrote:

hi,
i've just a simple question:
what are the time complexities of inserting / removing / checking if an
element is present in 1) a list and 2) a dictionary?
does anybody know?
thanks

No no no, that's not the way to ask the question, you're hardly likely to
get answers that way.

What you do is, you write in and say "I need a more efficient way of
adding data to a list, because adding data to a list is O(n**2) and that's
too slow. Also, how do I implement hash tables in Python, because I need
O(1) searching?"

That way you'll have dozens, maybe hundreds of replies from people
explaining that adding data to Python lists is O(log n) amortized, and
that dictionaries are hash tables.

*wink*

--
Steven.

[Ben Finney]

"xa******@gmail.com" <xa******@gmail.com> writes:

what are the time complexities of inserting / removing / checking if an
element is present in 1) a list and 2) a dictionary?
Partly dependent on the implementation, of which there are several for
Python (CPython, Jython, PyPy, and others). Which one are you most
interested in?
does anybody know?

The 'timeit' module can help you discover the answers for yourself, on
your current implementation.

--
\ "You could augment an earwig to the point where it understood |
`\ nuclear physics, but it would still be a very stupid thing to |
_o__) do!" -- The Doctor, _The Two Doctors_ |
Ben Finney

[Paul Rubin]

"xa******@gmail.com" <xa******@gmail.com> writes:

what are the time complexities of inserting / removing / checking if an
element is present in 1) a list and 2) a dictionary?
does anybody know?

I assume in the list case, the element you want to operate on is in
the middle of the list. In CPython, those are linear time operations.
If you just want to append to the end or remove from the end, those
are approximately constant time. For dicts, all those operations are
approximately constant time in CPython. Approximately means
occasionally something happens that makes it slower, but it's constant
time on average.

The Python docs don't specify this anywhere but it's so fundamental to
how people expect Python to work that it's not likely to be much worse
in any other implementation.