Publié · en amélioration
Guide Structures de données de base · 2/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
This chapter traces each structure on a tiny example, so you can see exactly which memory moves on every operation.
A dynamic array keeps a size (items in use) and a capacity (slots allocated). When size == capacity and you append, it allocates a block twice as large, copies the old items over and then writes the new one. Here is a trace of nine appends starting from capacity 1:
| Append | Size after | Capacity after | Items copied |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 2 | 2 | 2 | 1 |
| 3 | 3 | 4 | 2 |
| 4 | 4 | 4 | 0 |
| 5 | 5 | 8 | 4 |
| 6 to 8 | 8 | 8 | 0 |
| 9 | 9 | 16 | 8 |
Nine appends caused 1 + 2 + 4 + 8 = 15 copies, fewer than two per append. That is why appending is O(1) amortized even though a single append can cost O(n). The simulation below counts copies for any number of appends:
def count_copies(n, growth=2):
size, capacity, copies = 0, 1, 0
for _ in range(n):
if size == capacity:
copies += size # move every item to the new block
capacity *= growth
size += 1
return copies
for n in (9, 1_000, 1_000_000):
print(n, count_copies(n), round(count_copies(n) / n, 2))
# the copies-per-append ratio stays below 2Inserting at the front is different: every existing item shifts one slot to the right, so list.insert(0, x) costs O(n) every time, not just occasionally.
A singly linked list A -> B -> D stores three nodes, each with a next reference. To insert C after B:
C.C.next = B.next (so C points to D).B.next = C.Only two references change, regardless of the list length. The order of steps 2 and 3 matters: doing step 3 first loses the only reference to D. Finding B in the first place still requires walking from the head, which is O(n).
A stack is the natural tool for anything nested. To check that is balanced, push every opening bracket and, on every closing bracket, pop and compare:
([]{})| Char | Action | Stack after |
|---|---|---|
( | push | ( |
[ | push | ( [ |
] | pop [, matches | ( |
{ | push | ( { |
} | pop {, matches | ( |
) | pop (, matches | empty |
The input is balanced because every pop matched and the stack ended empty.
PAIRS = {")": "(", "]": "[", "}": "{"}
def balanced(text):
stack = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in PAIRS:
if not stack or stack.pop() != PAIRS[ch]:
return False
return not stack
print(balanced("([]{})"), balanced("(]"), balanced("((")) # True False FalseA queue on top of a fixed array uses two indices: head (next item to remove) and tail (next free slot). Both move forward and wrap around with % capacity, so nothing is ever shifted. With capacity 4:
| Operation | Slots | head | tail | Size |
|---|---|---|---|---|
| start | _ _ _ _ | 0 | 0 | 0 |
| enqueue a, b, c | a b c _ | 0 | 3 | 3 |
| dequeue (a) | _ b c _ | 1 | 3 | 2 |
| enqueue d | _ b c d | 1 | 0 | 3 |
| enqueue e | e b c d | 1 | 1 | 4 |
After e the tail wrapped to slot 0. When the buffer is full, a growable version copies the items into a larger array in queue order and resets head to 0.
A hash table has an array of buckets. To store a key, compute hash(key) % bucket_count and put the pair in that bucket. With separate chaining, each bucket is a small list, and keys that collide simply share it. Using 8 buckets and integer keys whose hash is the key itself:
| Key | key mod 8 | Bucket after insert |
|---|---|---|
| 3 | 3 | bucket 3: [3] |
| 11 | 3 | bucket 3: [3, 11] |
| 6 | 6 | bucket 6: [6] |
| 19 | 3 | bucket 3: [3, 11, 19] |
Keys 3, 11 and 19 collide. Looking up 19 hashes to bucket 3 and then scans three entries. The load factor is 4 / 8 = 0.5. When it passes a threshold such as 0.75, the table doubles its bucket count and reinserts every pair, because each pair's bucket index depends on the bucket count.
def place(keys, bucket_count):
buckets = [[] for _ in range(bucket_count)]
for key in keys:
buckets[hash(key) % bucket_count].append(key)
return {i: b for i, b in enumerate(buckets) if b}
keys = [3, 11, 6, 19]
print(place(keys, 8)) # {3: [3, 11, 19], 6: [6]}
print(place(keys, 16)) # {3: [3, 19], 6: [6], 11: [11]}Doubling to 16 buckets split the long chain. A good hash function plus a bounded load factor keeps chains short, which is where the average O(1) comes from.
A dynamic array pays for occasional copying with cheap appends, a linked list changes a couple of references per splice, a stack and a ring-buffer queue only touch their ends, and a hash table computes a bucket and scans a short chain. Tracing these on paper once makes their complexity numbers obvious instead of memorised.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.