Videos / DSA

Episode 3 of 22 · DSA, end to end

Arrays and 2D arrays: contiguous memory, and why it is fast

Chapters

1. One block, no gaps0:00
2. The index is arithmetic0:17
3. Constant time, and its price0:32
4. Insert, and everything shifts0:50
5. Finding, not reading1:05
6. The whole cost model1:22
7. The whole shelf1:38
8. Sixteen for the price of one1:54
9. The size of the gap2:11
10. The miss path2:27
11. The list that misses every step2:43
12. When the dumb loop wins3:01
13. A table laid for eight3:19
14. Size and capacity3:37
15. The append that is not cheap3:56
16. Why doubling4:12
17. Amortised, precisely4:31
18. Reserve up front4:50
19. The grid is a lie5:06
20. Row major5:23
21. Two loop orders5:40
22. Count the cache lines5:59
23. The fix is one swap6:16
24. When it is not one block6:35
25. Two walkers, one swap6:52
26. Rotate, the obvious way7:08
27. Three reverses7:26
28. Why it works, and modulo7:44
29. One read index, one write8:02
30. What partition really is8:21
31. The note says shelf four8:37
32. The append that moves it8:55
33. The blunt rule9:11
34. Removing while you iterate9:33
35. Fail fast, or fail silently9:51
36. Iterate one, build another10:09
37. One block, in order10:25

Arrays and 2D arrays: contiguous memory, and why it is fast. Picture a street of identical houses, numbered from zero, with no gaps between them. That is an array. One block of memory, every element exactly the same size, laid end to end. Al

Mark as watchedSaved in this browser only.