What is the cost of len() function for Python built-ins? Is it same for all built-ins? (list/tuple/string/dictionary)
+16
A:
It's O(1) (very fast) on every type you've mentioned, plus set and others such as array.array.
Alex Martelli
2009-07-12 04:40:31
+19
A:
Calling len() on those data types is O(1) in CPython, the most common implementation of the Python language. Here's a link to a table that provides the algorithmic complexity of many different functions in CPython:
James Thompson
2009-07-12 04:59:44
+1 for the link. Useful.
musicfreak
2009-07-12 06:22:10
+2
A:
List:
adam@cajita:~/devel> python -mtimeit -s "l = range(10); len(l)"
10000000 loops, best of 3: 0.0369 usec per loop
adam@cajita:~/devel> python -mtimeit -s "l = range(1000000); len(l)"
10000000 loops, best of 3: 0.0372 usec per loop
Tuple:
adam@cajita:~/devel> python -mtimeit -s "t = (1,)*10; len(t)"
10000000 loops, best of 3: 0.037 usec per loop
adam@cajita:~/devel> python -mtimeit -s "t = (1,)*1000000; len(t)"
10000000 loops, best of 3: 0.0371 usec per loop
String:
adam@cajita:~/devel> python -mtimeit -s "s = '1'*10; len(s)"
10000000 loops, best of 3: 0.037 usec per loop
adam@cajita:~/devel> python -mtimeit -s "s = '1'*1000000; len(s)"
10000000 loops, best of 3: 0.037 usec per loop
Dictionary:
adam@cajita:~/devel> python -mtimeit -s "d = dict((i,j) for i, j in enumerate(range(10))); len(d)"
10000000 loops, best of 3: 0.037 usec per loop
adam@cajita:~/devel> python -mtimeit -s "d = dict((i,j) for i, j in enumerate(range(1000000))); len(d)"
10000000 loops, best of 3: 0.0369 usec per loop
Array:
adam@cajita:~/devel> python -mtimeit -s "import array; a = array.array('i',range(10)); len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
adam@cajita:~/devel> python -mtimeit -s "import array; a = array.array('i',range(1000000)); len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
Set:
adam@cajita:~/devel> python -mtimeit -s "s = set(range(10)); len(s)"
10000000 loops, best of 3: 0.0371 usec per loop
adam@cajita:~/devel> python -mtimeit -s "s = set(range(1000000)); len(s)"
10000000 loops, best of 3: 0.0371 usec per loop
Deque:
adam@cajita:~/devel> python -mtimeit -s "from collections import deque; d = deque(range(10)); len(d)"
10000000 loops, best of 3: 0.037 usec per loop
adam@cajita:~/devel> python -mtimeit -s "from collections import deque; d = deque(range(1000000)); len(d)"
10000000 loops, best of 3: 0.037 usec per loop
Adam Bernier
2009-07-12 05:34:28
This is not so good of a benchmark even though it shows what we already know. This is because range(10) and range(1000000) is not supposed to be O(1).
Unknown
2009-07-12 05:45:44
@Unknown: you're absolutely right. Thank you for pointing that out.
Adam Bernier
2009-07-12 06:57:25
Is it ironic to get good information from someone named Unknown? Or am I confusing ironic with Alanis Morissette ironic?
James Thompson
2009-07-13 05:08:27
That song was an unfortunate stain on an otherwise solid career. I'd say you've captured the second definition quite well: Ironic (adj) 2: characterized by an often poignant difference or incongruity between what is expected and what actually is; "madness, an ironic fate for such a clear thinker".
Adam Bernier
2009-07-14 03:10:51
+4
A:
All those objects keep track of their own length. The time to extract the length is small and mostly consists of [rough description, written in Python terms, not C terms]: look up "len" in a dictionary and despatch it to the built_in len function which will look up the object's __len__ method and call that ... all it has to do is return self.length
John Machin
2009-07-12 06:17:13