The biggest speedups almost always come from three things, in this order: measuring to find the real bottleneck, picking a better algorithm or data structure, and avoiding repeated work (caching, fewer I\/O calls). Micro-tweaks like swapping a multiply for a shift rarely matter. The ten techniques below are ordered roughly by how much they usually buy you. Examples are in Python, and every output shown was produced by running the code.<\/p>\n
Guessing where code is slow is wrong surprisingly often. Profile first, change one thing, then profile again.<\/p>\n
cProfile<\/code> shows time per function, and timeit<\/code> times small snippets.<\/li>\n- JavaScript in the browser:<\/strong> the Performance tab in Chrome DevTools.<\/li>\n
- Anything:<\/strong> a simple timer around the suspicious section, run several times on realistic data.<\/li>\n<\/ul>\n
import cProfile\n\ncProfile.run(\"main()\", sort=\"cumulative\") # replace main() with your entry point\n<\/code><\/pre>\nDonald Knuth’s often-quoted line is “premature optimization is the root of all evil”. The full sentence is about small efficiencies in non-critical parts of a program: you should not spend effort on them, but you should not pass up the critical few percent either. Profiling is how you find that few percent.<\/p>\n
2. Choose a better algorithm<\/h2>\n
This is where order-of-magnitude gains live. If the input doubles and your runtime quadruples, you probably have a nested loop that a different approach can remove. Compare two ways to check for duplicates:<\/p>\n
def dup_quadratic(nums):\n for i in range(len(nums)):\n for j in range(i + 1, len(nums)):\n if nums[i] == nums[j]:\n return True\n return False\n\ndef dup_set(nums):\n seen = set()\n for x in nums:\n if x in seen:\n return True\n seen.add(x)\n return False\n\nprint(dup_quadratic([1, 2, 3, 2]), dup_set([1, 2, 3, 2])) # True True\ndata = list(range(3000))\nprint(dup_quadratic(data), dup_set(data)) # False False\n<\/code><\/pre>\nBoth give the same answers. The first is O(n^2) and does about 4.5 million comparisons on the 3,000 items above; the second is O(n) on average. In a quick timing run the quadratic version was more than 20 times slower on that input, and the gap keeps growing with size. The rule of thumb: sorting a large input needs an O(n log n) algorithm, not bubble sort, and any “for each item, scan the whole list” pattern is a hint to use a hash map or sort first. If you need a refresher on the notation, see time complexity explained<\/a>.<\/p>\n3. Pick the right data structure<\/h2>\n
The same idea applies to the container you choose:<\/p>\n
\n- Membership tests (
x in collection<\/code>): a list<\/code> scans every element (O(n)); a set<\/code> or dict<\/code> is O(1) on average. In a timing test with 100,000 numbers, checking for the last element in the set was over 50 times faster than in the list.<\/li>\n- Take items from the front: use
collections.deque<\/code>; list.pop(0)<\/code> is O(n).<\/li>\n- Always need the smallest item: a heap (
heapq<\/code>) instead of re-sorting.<\/li>\n- Lookups by key: a dictionary instead of searching a list of pairs.<\/li>\n<\/ul>\n
The Hash Map lesson<\/a> practices exactly this trade.<\/p>\n4. Cache repeated work<\/h2>\n
If a function is pure (the same input always gives the same output) and called repeatedly with the same arguments, store the result. In Python, functools.lru_cache<\/code> does it in one line:<\/p>\nfrom functools import lru_cache\n\ncalls = 0\ndef fib(n):\n global calls\n calls += 1\n return n if n < 2 else fib(n - 1) + fib(n - 2)\n\nfib(25)\nprint(\"plain calls:\", calls) # plain calls: 242785\n\n@lru_cache(maxsize=None)\ndef fib_cached(n):\n return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)\n\nfib_cached(25)\nprint(fib_cached.cache_info()) # CacheInfo(hits=23, misses=26, maxsize=None, currsize=26)\n<\/code><\/pre>\n