2.2 Data Structures
← 2.1 Programming Principles | Home | Next: 2.3 Clean Code →
Basic Structures
Understand basic types (int, float, boolean, char/string), composite types (arrays, matrices, objects/dictionaries/hash tables), and more advanced structures (linked lists, trees, graphs), along with their use cases and complexity characteristics.
Caching and Memoization
Caching stores frequently accessed data in a higher-performance intermediate layer to avoid repeated computation or repeated reads from slow storage (databases, network). Common tiers: CPU L1/L2/L3 caches → in-memory caches (e.g., Redis) → disk.
Memoization is a specific optimization technique in functional programming: cache the results of function calls and return the cached result for the same inputs. This requires the function to be a pure function (no side effects, same inputs always yield the same output). A classic example is the Fibonacci sequence—without memoization the time complexity is O(2^n); with memoization it drops to O(n).
Stack vs. Heap
| Dimension | Stack | Heap |
|---|---|---|
| Allocation | Automatically allocated at the top of the stack when a function is called; automatically freed when the function returns | Allocated and freed dynamically at runtime, with no enforced pattern |
| Structure | LIFO (last in, first out), contiguous memory | Arbitrary order, non-contiguous, requires bookkeeping |
| Speed | Very fast: allocation simply adjusts a pointer, typically a single CPU instruction | Slow: requires finding a suitable free block, thread synchronization, updating allocation tables |
| Cache | Very high CPU cache hit rate (frequent reuse) | Lower (scattered memory access) |
| Threading | Each thread gets its own independent stack | Typically a single per-application global resource, requires thread safety |
| Size | Fixed at thread creation | Can grow, limited by system memory |
| Common issues | Stack overflow (infinite recursion, excessively deep call chains, overly large local variables) | Memory leaks (allocated but not freed), fragmentation (enough total free memory but no contiguous block large enough) |
| Use case | Local variables, function parameters, return addresses | Objects allocated with new/malloc, data that needs to survive across function calls |
Git vs. GitHub Analogy
Git is a revision control system, a tool to manage your source code history. GitHub is a hosting service for Git repositories. They are not the same thing: Git is the tool, GitHub is the service for projects that use Git. As Arthur Khazbulatov put it, "The difference between git and GitHub is the same as the difference between porn and PornHub." You do not need GitHub to use Git.
Sources
- Stack Overflow — What and where are the stack and heap?: https://stackoverflow.com/a/80113/1213497
- Stack Overflow — Difference between Git and GitHub: https://stackoverflow.com/a/13321586
← 2.1 Programming Principles | Home | Next: 2.3 Clean Code →