{ "cells": [ { "cell_type": "markdown", "id": "d848a7b2", "metadata": {}, "source": [ "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/MeiraDavidson/compute_module1/blob/main/notebooks/lab_06_counted_and_clocked.ipynb)\n\n", "# Lab 6: Counted and Clocked\n", "\n", "*From* **A First Taste of Algorithms — and the Machines That Learn** *(The Curious Family Library). A computational lab: run the cells in order. A few labs end with a deliberately broken “Break it” cell — that one is meant to fail, and seeing how is the point.*" ] }, { "cell_type": "markdown", "id": "4277b1be", "metadata": {}, "source": [ "*Accompanies Chapter 6. Until now this book has counted and refused to clock. Today both instruments run side by side: the count predicts the shapes, the clock reveals the constants, and a plot — your first — shows the two sorts diverging exactly as the chapter promised. Two instruments arrive, each with its debt: the clock because constants are real, the plot because six chapters of tables have earned a picture.*\n", "\n", "## 1. The plodder, counted\n", "\n", "Insertion sort, exactly as hands do it — each arrival walks left past everything bigger:" ] }, { "cell_type": "code", "execution_count": null, "id": "3f47c045", "metadata": {}, "outputs": [], "source": [ "def insertion_sort_count(a):\n", " comparisons = 0\n", " for i in range(1, len(a)):\n", " arriving = a[i]\n", " j = i - 1\n", " while j >= 0 and a[j] > arriving:\n", " comparisons = comparisons + 1\n", " a[j + 1] = a[j] # shift the bigger card right\n", " j = j - 1\n", " if j >= 0:\n", " comparisons = comparisons + 1 # the comparison that said \"stop\"\n", " a[j + 1] = arriving\n", " return comparisons\n", "\n", "hand = [7, 3, 9, 1, 8]\n", "print(insertion_sort_count(hand), hand)" ] }, { "cell_type": "markdown", "id": "8dd63ca6", "metadata": {}, "source": [ "One behavior to notice and remember: this sorter works **in place** — it rearranges the very list you hand it, the way your hands rearrange the actual cards (print `hand` after the call: it changed). Merge sort, by contrast, built a *new* sorted list and left its input alone. The difference seems cosmetic today; in §3 it becomes load-bearing. Check the count against your paper run from Fluency 1.1. Then the gait audit, worst case (reverse-sorted), in the house style:" ] }, { "cell_type": "code", "execution_count": null, "id": "a6467c1e", "metadata": {}, "outputs": [], "source": [ "for n in [8, 32, 128, 512, 2048]:\n", " print(n, insertion_sort_count(list(range(n, 0, -1))))" ] }, { "cell_type": "markdown", "id": "6e9dafef", "metadata": {}, "source": [ "Verify each row equals n(n − 1)/2 exactly, and read the gait: n quadruples each row — the count multiplies by *sixteen*. The n² signature, measured.\n", "\n", "## 2. The race, counted\n", "\n", "Retype merge sort and its step counter from Lab 3 (`merge`, `merge_sort_count`) — retyping is review — then race the two on the same worst-case inputs:" ] }, { "cell_type": "code", "execution_count": null, "id": "12703ccb", "metadata": {}, "outputs": [], "source": [ "for n in [8, 32, 128, 512, 2048]:\n", " ins = insertion_sort_count(list(range(n, 0, -1))) # fresh worst case each —\n", " mrg = merge_sort_count(list(range(n, 0, -1)))[1] # remember: insertion mutates\n", " print(n, \" insertion:\", ins, \" merge:\", mrg, \" ratio:\", round(ins / mrg, 1))" ] }, { "cell_type": "markdown", "id": "927db739", "metadata": {}, "source": [ "Read the ratio column: about 1 at the top, about 90 at the bottom, roughly doubling with each doubling of n. In the counted currency the halver wins at *every* size on this table — even n = 8 — and the gap only opens. Hold that fact; the clock is about to complicate it.\n", "\n", "## 3. The clock arrives — with a protocol\n", "\n", "Python's stopwatch is `time.perf_counter()`: call it, do work, call it again, subtract. But a computer is a busy place — your timing shares the machine with everything else running — so single measurements lie. The professional protocol: **repeat many times, take the median** (the middle value when sorted — outliers from a busy moment fall off the ends)." ] }, { "cell_type": "code", "execution_count": null, "id": "0257a703", "metadata": {}, "outputs": [], "source": [ "import time\n", "\n", "def clock(sorter, items, repeats):\n", " times = []\n", " for _ in range(repeats):\n", " copy = list(items)\n", " start = time.perf_counter()\n", " sorter(copy)\n", " times.append(time.perf_counter() - start)\n", " times.sort() # the built-in sort; §6 turns the clock on it\n", " return times[len(times) // 2] # the median" ] }, { "cell_type": "markdown", "id": "1658b5b2", "metadata": {}, "source": [ "(Note the line `copy = list(items)`: each repeat sorts a **fresh copy**. For an in-place sorter this is not tidiness, it is the experiment's integrity — predict what the second repeat would be measuring without it, then hold the thought for Break-it 2.)\n", "\n", "## 4. The clocked race, and the neighborhood\n", "\n", "Now both sorts on the clock. Plain versions without counters (retype `merge_sort` from Lab 3; write `insertion_sort` by deleting the counter from §1), shuffled inputs this time — the clock's question is \"typical day,\" and `random.shuffle` deals one:" ] }, { "cell_type": "code", "execution_count": null, "id": "22e70e99", "metadata": {}, "outputs": [], "source": [ "import random\n", "random.seed(7) # same shuffles every run: experiments should repeat\n", "\n", "for n in [4, 8, 16, 32, 64, 128, 256]:\n", " items = list(range(n))\n", " random.shuffle(items)\n", " t_ins = clock(insertion_sort, items, 51)\n", " t_mrg = clock(merge_sort, items, 51)\n", " winner = \"insertion\" if t_ins < t_mrg else \"merge\"\n", " print(n, \" insertion:\", round(t_ins * 1e6, 1), \"µs merge:\",\n", " round(t_mrg * 1e6, 1), \"µs →\", winner)" ] }, { "cell_type": "markdown", "id": "8e1b19d4", "metadata": {}, "source": [ "Predict before running: §2 said merge wins every count — does it win every clock? Then read the table. On most machines a *neighborhood* appears at small n where insertion wins the clock while losing the count: the plodder is a simple creature with almost no overhead, and at a dozen items, overhead is most of the bill. Find your machine's crossover point (the n where the winner flips) and write it down — it is data for Problem 2.1, and it is the constant factor, located. The count predicted the shapes; the constants own the neighborhood.\n", "\n", "## 5. The first plot\n", "\n", "Six chapters of tables; time for the picture. `matplotlib` draws it — three moves for now: `plt.plot` draws a curve from lists of x and y values, `plt.loglog` does the same with both axes multiplying (so power laws become straight lines), and `plt.show()` reveals." ] }, { "cell_type": "code", "execution_count": null, "id": "80a2c2ab", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "ns = [8, 32, 128, 512, 2048]\n", "ins_counts = []\n", "mrg_counts = []\n", "for n in ns:\n", " worst = list(range(n, 0, -1))\n", " ins_counts.append(insertion_sort_count(worst)[1])\n", " mrg_counts.append(merge_sort_count(worst)[1])\n", "\n", "plt.loglog(ns, ins_counts, \"o-\", label=\"insertion (counted)\")\n", "plt.loglog(ns, mrg_counts, \"s-\", label=\"merge (counted)\")\n", "plt.xlabel(\"n\")\n", "plt.ylabel(\"steps\")\n", "plt.legend()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "0334209b", "metadata": {}, "source": [ "Two nearly straight lines, diverging — and their *slopes* are the exponents: the insertion line climbs twice as steeply (n² against n·log n's almost-1). You are looking at Θ notation before it had a name: the plot ignores constants (they only shift a line up or down on these axes) and shows shape, which is exactly the deal the notation offers. Then plot the clocked data from §4 the same way and find the crossover as a *crossing of curves* — the picture of the constants' neighborhood.\n", "\n", "## 6. The humbling\n", "\n", "One more clock. Python ships with `sorted()` — Timsort, the deep water's engineered descendant of exactly the two algorithms on your screen. Predict the ratio before running: your merge sort versus the professionals, n = 2,048, shuffled. Twice as fast? Five times?" ] }, { "cell_type": "code", "execution_count": null, "id": "093e1d8a", "metadata": {}, "outputs": [], "source": [ "items = list(range(2048))\n", "random.shuffle(items)\n", "t_mine = clock(merge_sort, items, 11)\n", "t_builtin = clock(sorted, items, 11)\n", "print(\"mine:\", round(t_mine * 1e3, 2), \"ms built-in:\",\n", " round(t_builtin * 1e3, 2), \"ms ratio:\", round(t_mine / t_builtin))" ] }, { "cell_type": "markdown", "id": "ea06cda5", "metadata": {}, "source": [ "The ratio is humbling — and the humility has *structure*, so spend it wisely. The built-in is the same Θ(n log n) as yours; the fence guarantees it cannot be a different shape. The entire margin is constants: decades of engineering, plus the quiet fact that `sorted` runs in C beneath Python's floor. Your algorithm and theirs will scale *identically* — double n and both double-and-a-bit — which you can verify by clocking both at 4,096 and checking the two ratios-to-before. The shapes are yours; the constants are an industry; and you now own the instrument that tells those two stories apart.\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "**1.** Feed §2's counted race *already-sorted* inputs instead of reversed: `list(range(n))` in both places. Predict both columns before running. One algorithm's column collapses to almost nothing; which, why, and what is its exact new count? Connect to the chapter's recorded virtue — and to why \"insertion sort is Θ(n²)\" needed the words *worst case* attached.\n", "\n", "**2.** Sabotage the timing protocol: change `clock` so all repeats share one list instead of sorting fresh copies (`copy = items` instead of `list(items)`). Predict what happens to insertion sort's clocked numbers and *why* — then run §4's race with the corrupted clock and watch the standings change. Which algorithm benefited from the corruption, and what does Break-it 1 have to do with it? (Measurement bugs that flatter one contestant are the most dangerous kind; you have just built one.)\n", "\n", "**3.** Time a *single* run instead of a median of 51 (set repeats to 1) and run the n = 64 comparison ten times in a loop, printing the winner each time. Predict: same winner all ten times? Report the tally. The median protocol exists because of what you just witnessed; state the lesson in one sentence about believing any single measurement, anywhere, ever.\n", "\n", "**4.** Build the chapter's counting sort for exam scores (whole numbers 0–100): 101 buckets, one pass in, read out in order. Count its touches at n = 1,000,000 (simulate with random scores) and clock it against `sorted` on the same data. Predict the winner first — you are betting a linear algorithm against the best-engineered n log n on Earth. Then betray it: change the keys from scores to `random.random()` decimals and explain, in the theorem-and-gate language of the chapter, why your algorithm doesn't just slow down but *stops making sense*.\n", "\n", "\n", "\n", "
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }