TopolearnChoosing the right container for millions of operations depends on its real complexity, not its interface.
deque is a doubly linked list of fixed-size blocks (64 slots each in CPython). Appends and pops at either end are O(1) and rarely allocate. Indexing walks block by block from the nearer end, so d[i] is O(n) in the middle, and insert/del in the middle are O(n). It has no slicing. Memory per item is close to a list's.
dict (and so Counter and defaultdict) is a hash table with a compact array of entries in insertion order plus a sparse index table. Lookups, inserts and deletes are O(1) on average. Deleting leaves dummy entries until the table is resized, which is why ordering survives deletes cheaply.
Counter is a pure-Python dict subclass, but counting an iterable uses a C helper (_count_elements), so Counter(iterable) is much faster than a Python loop. most_common(n) uses heapq.nlargest, O(N log n); without n it sorts everything.
defaultdict is a C dict subclass implementing __missing__; overhead beyond a dict lookup appears only for missing keys.
OrderedDict is implemented in C with an extra linked list over the dict, so move_to_end and popitem(last=False) are O(1), at the cost of noticeably more memory than a plain dict.
namedtuple field access goes through properties (_tuplegetter in C), slightly slower than plain tuple indexing but much faster than a dict lookup.
Example
import sys
import timeit
from collections import Counter, OrderedDict, deque
n = 100_000
lst, dq = list(range(n)), deque(range(n))
t_list = timeit.timeit(lambda: lst.insert(0, lst.pop()), number=2000)
t_deque = timeit.timeit(lambda: dq.appendleft(dq.pop()), number=2000)
print(t_deque < t_list) # True: O(1) vs O(n) at the left end
t_mid_list = timeit.timeit(lambda: lst[n // 2], number=20000)
t_mid_deque = timeit.timeit(lambda: dq[n // 2], number=20000)
print(t_mid_list < t_mid_deque) # True: deque indexing walks blocks
words = ["a", "b", "c"] * 50_000
def manual():
c = {}
for w in words:
c[w] = c.get(w, 0) + 1
return c
print(timeit.timeit(lambda: Counter(words), number=5) < timeit.timeit(manual, number=5)) # True
d, od = dict.fromkeys(range(1000)), OrderedDict.fromkeys(range(1000))
print(sys.getsizeof(od) > sys.getsizeof(d)) # TrueRemember
- deque is a linked list of blocks: O(1) at the ends, O(n) in the middle
- Counter counts via a C helper;
most_common(n)uses a heap - OrderedDict trades extra memory for O(1) reordering
Watch out for
- Using a deque for random access by index in a hot loop.