{ "cells": [ { "cell_type": "markdown", "id": "737e79eb", "metadata": {}, "source": [ "# Dictionaries" ] }, { "cell_type": "code", "execution_count": 1, "id": "200584f6", "metadata": { "tags": [ "hide-input" ] }, "outputs": [], "source": [ "import sys\n", "from pathlib import Path\n", "\n", "current = Path.cwd()\n", "for parent in [current, *current.parents]:\n", " if (parent / '_config.yml').exists():\n", " project_root = parent # ← Add project root, not chapters\n", " break\n", "else:\n", " project_root = Path.cwd().parent.parent\n", "\n", "sys.path.insert(0, str(project_root))\n", "\n", "from shared import thinkpython, diagram, jupyturtle\n", "from shared.download import download\n", "\n", "# Register as top-level modules so direct imports work in subsequent cells\n", "sys.modules['thinkpython'] = thinkpython\n", "sys.modules['diagram'] = diagram\n", "sys.modules['jupyturtle'] = jupyturtle\n" ] }, { "cell_type": "markdown", "id": "9963a57e", "metadata": {}, "source": [ "This chapter presents a built-in type called a dictionary.\n", "\n", "It is one of Python's best features -- and the building block of many efficient and elegant algorithms.\n" ] }, { "cell_type": "markdown", "id": "be7467bb", "metadata": {}, "source": [ "## What Is a Dictionary?\n", "\n", "A dictionary in Python is a built-in data type used to store data in key–value pairs. A Python dictionary is like a real world dictionary, where you look up a word for its definition. In Python dictionary, you look up a **key** for the **value**. \n", "\n", "The key characteristics of a dictionary are:\n", "\n", "1. Dictionaries are **mutable** (can be changed)\n", "2. Keys must be **immutable** (strings, numbers, tuples)\n", "3. A dictionary represents a **mapping** from **keys** to **values**. \n", "4. **Keys** must be **unique**\n", "5. **Values** can be any data type\n", "\n", "In terms formatting, \n", "- Each dictionary item consists of a **key** and a **value** separated by a **colon**. \n", "- Dictionary items are separated by **commas** and enclosed in **curly braces**." ] }, { "cell_type": "markdown", "id": "3a94f8ae", "metadata": {}, "source": [ "A **dictionary** is like a list, but more general. In a list, the indices have to be integers; in a dictionary they can be (almost) any type.\n", "\n", "| Feature | List | Dictionary |\n", "| --------- | ---------------- | ----------------- |\n", "| Access by | Index (0,1,2) | Key |\n", "| Structure | Ordered sequence | Key-value mapping |\n", "| Best for | Ordered data | Labeled data |\n" ] }, { "cell_type": "markdown", "id": "bb0fdc15", "metadata": {}, "source": [ "As seen in the example below: \n", "\n", "- A **list** of number words can be accessed using an integer as an **index**. \n", "- A **dictionary** goes in the other direction, and look up a word to get the corresponding integer; in other words, using the keys to look up the values." ] }, { "cell_type": "code", "execution_count": 2, "id": "20dd9f32", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['zero', 'one', 'two']\n", "one\n", "{'zero': 0, 'one': 1, 'two': 2}\n", "1\n" ] } ], "source": [ "nums_lst = ['zero', 'one', 'two']\n", "print(nums_lst)\n", "print(nums_lst[1])\n", "\n", "nums_dic = {'zero': 0, 'one': 1, 'two': 2}\n", "print(nums_dic)\n", "print(nums_dic['one'])" ] }, { "cell_type": "markdown", "id": "2c2f6f79", "metadata": {}, "source": [ "In mathematical language, a dictionary represents a **mapping** from keys to values, so you can also say that each key \"maps to\" a value.\n", "In this example, each number word maps to the corresponding integer.\n", "\n", "The following figure shows the state diagram for `numbers`.\n", "A dictionary is represented by a box with the word \"dict\" outside and the items inside.\n", "Each item is represented by a key and an arrow pointing to a value.\n", "The quotation marks indicate that the keys here are strings, not variable names." ] }, { "cell_type": "code", "execution_count": 3, "id": "e9004edf", "metadata": { "tags": [ "remove-input" ] }, "outputs": [], "source": [ "from diagram import make_dict, Binding, Value\n", "\n", "numbers = {'zero': 0, 'one': 1, 'two': 2}\n", "\n", "d1 = make_dict(numbers, dy=-0.3, offsetx=0.37)\n", "binding1 = Binding(Value('numbers'), d1)" ] }, { "cell_type": "code", "execution_count": 4, "id": "3b05ed1f", "metadata": { "tags": [ "remove-input" ] }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAMsAAACQCAYAAACmsp8HAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjcsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvTLEjVAAAAAlwSFlzAAAPYQAAD2EBqD+naQAACz5JREFUeJzt3QVoVX0YBvB3zsLC7g5snd3xqSioOJNNVCwEGSbqZCbYmCjqsBWdYmEiGOjsbuyuWdiBdd3H88K9bOq2V73bDZ8fDHfv7u499+w85/8/m+c5AbGxsbFCRElKlfRDiIhhIfoNHFmIjBgWIiOGhciIYSEyYliIjBgWIiOGhciIYSEyYliIjBgWIiOGhciIYSEyYliIjBgWIiOGhciIYSEyYliIjBgWIiOGhciIYfFSOXPmlLt370rLli3l2rVriT528+bNcuzYsRRbtn8Vw+LlduzYIaVLl070MQxLymBYvMTWrVulbNmyUqlSJQkPD3fdX7RoUTl37px+/ujRI+nYsaNUrFhRHzd69GgNE7532rRpEhQUJIsXL/bgu/BvqT29ACTy7Nkz6dmzpxw8eFDKlSsnCxculBcvXvy0arp27SrNmzeXDRs26O3nz59Lrly5pE2bNhqUQYMGcXUmI44sXgDHGxgpEBTo3bu3pE2bNt5j3r9/L4cOHZIhQ4a47kNQKOUwLF4oICDA04tAv8CweIE6derIhQsX5OrVq3p76dKl8uXLl3iPyZQpkzRs2FBmzJjhug/TMMiSJYu8efMmhZf638OweAFMpxCQdu3aSeXKleXGjRuSI0eOnx63cuVKOXXqlJQvX16PUebOnav3d+vWTdatWydVqlThAX4yCmCLPpENRxYiI4aFyIhhITLiHyU97N27d55ehH9e5syZTeuAIwuREcNCZMSwEBkxLERGDAuREcNCZMSwEBkxLERGDAuRr4Yl7jnnFF+FChX86nXc6ebNm9KsWTM9TaFRo0Zy5coV8fuwuMO3b988vQhezR/Xz6BBg7TH4OzZszJ48GDp27evZ8OC010nTZokNWvWlGLFismyZcsSHBGqV68u0dHR+nnjxo313HGc6Ve4cGFXK0n9+vX1+2bOnBnvdaKioqRatWpSsmRJbS1xwklRrVq1kho1aug5686Tn5zLNnbsWP1aRESEnteO58BJUthTRkZGiqc4HA5ZsmSJ7Nq1S8+l/1M4IQxnVNarV8/1UaBAAZk8ebJ+/fTp09K6dWvds2Ldbtq0Se+/d++eFCpUSMaMGSMNGjSQBQsWyK1bt7ToAmdp4nm2b98e73U8zeFwyJo1a2T//v3y4cOHRB+LM0YRkpCQEL0dHBysTTh4jx79j5Tp0qWTEydO6Cmw2DBxll7q1Ek/DX5g+/btk7dv32pAXr16pW0mMTEx2ovVq1cvyZo1qz726dOnekYgGk6qVq2qP8xatWpJ586dZdWqVVKmTBn5+PGj1K5dW+/HckBgYKCcPHnStcKGDh2q3wN4PU/BcuE9onACy4flrVu3rp4q/Duw4cDhw4f13wMHDkj//v2le/fu8vr1axk4cKA2v+TNm1fXHYKB9QM47Rjrbdy4cXr7v//+058d1jumME2bNtUdEHZmztfxpMDAQClRooRua+fPn9czSLEDzpgx40+PffjwoeTJk8e1HWLHWbBgQb0fz+GxsHTp0kX/xYrHwj158kQXLCnou8IKyJYtmxQvXlz3gHhT2DPitFq0L2IUcLab4GtoZWzfvr3s2bNHg3Tp0iUJDQ2N9z92L1++7AoLfvBO2BjGjx+vo1GTJk10T/sjrExswLGxsZISsJ4Q2uPHj7tGPoy2fwLvOywsTE8nzp8/v+zcuVPXYYcOHeI9Du8fO6c0adK41h3WGzbA3bt3622M4Bhhjhw5omFJTExMjAY+pdZZvnz5NOhnzpzRD3Sm4djEE347LOnTp3d9jo3fOf9FcDB0On369CnR70voeX4FwcEPJ3v27Ike/MfdU2MOi9EFQRsxYoROxebPny/+4PHjxzpi4v0465OwfrADw/v91aieIUMGSZUq1V83ygR4YfMMdkKYjWAbwnaIdYEdoWUn7pHzWbB3wh4Te0sMnUn18yZm+fLlOu9++fKlzrsxd8U0Bi0mOE7CgRxg+oAA4eNHeH18T58+fXS+jsD8CCsz7kiVnDCC4QM7FEyNnNOw3z2fBY/v1KmTvp+4oxKe0znVxagKOL5BgH51/gamNZjS9ujRQ+f2R48elalTp5r29MHBwZISsB3h4/v37zodT2gahpkJ3s/atWt15rNlyxadsbhzCubWsEyYMEHnzjh4xJCOBpI/hTeP0GH47devn25YgINQjBizZs3SjQ7TtNWrV//yOXDwv3fvXi2rw8gVt0IopWFZEV78wP/kWCUuVLVev35d5syZox/O6SemruvXr5dRo0bJyJEj5evXr7ozwI7mV1Dzit8aof0SowXWF3Yq3sLhcGiIMe1KKCRxzZ49W38DNn36dN2pJscsgu0uHsYzJT2PZ0oSuZlf/lGSKDkwLERGDAuREcNCZMSwEBkxLERGDAuREcNCZMSwEBkxLERGDAuREcNCZMSwEBkxLERGDAuREcNCZMSwEBkxLERGDAuREcNCZMSw+KjkbLr3xRb9YcOG6XKjBgl9acmBYSG/0LZtW62wTap+9m8wLD7K2XSP/l90/6LYEFcrQIdy3Ob8iRMnanMlGhuxMTkl1Lgf97l9pUUfnFcUSE5ua6SklIWN6MuXL9K1a1dtpkRgUMGK284+aDR6YmqChkqUgA8fPlxatGiRaOM+SsZ9rUU/pTAsPgwN+Sj7drbKY3TJnTu3XLx4UTd6lK/jGiyAa+rcuXNHP0cndUKN+/i+xMSwRZ/8RdyWe1xLx3kbe2rnVQ4Sa9z/nef/13Bk8WGlSpXShnkUoOMaNBgxcOkFlGljapWQxBr3UaTuay36KYXF4D5eDI4D/PDwcD0IxkiCS+ZhOoYw4MD9wYMH+jhcng9TLFx5DXBcg8Z9XNYjbuN+3OvmeJLD4XBdqMkSEhyD4RcY2FngEiS4UgGOddxZDM6weBhb9D2PLfpEbsa/sxAZMSxERgwLkRHDQmTEsBAZMSxERgwLkRHDQmTEsBAZMSxERgwLkRHDQmTEsBAZMSxERgwLkRHDQmTEsBAZMSxERgwLkRHDQmTEsPgwZ9v9vHnztALIXSZNmiRRUVHiKz59+iSdO3eWKlWqSN26dbXX7NatW25/HYbFD0RGRro1LL6oR48e2qF25MgRadmypfTv39/tr8Gw+DC03U+ZMkUeP36sGwua5NEsWbp0ab0Punfv7upC/vz5sxQpUkT/RYkdSvbQTomPoUOHatE4oKDO02V7jt9o0ceyovDcWS1bo0YNuX//vtuXifWtPszZdr9q1SpZvny5VKpUSW/jMhKoZg0NDdWS8NSpU2sTJfa8QUFB2ly5ePFivX3gwAHtQQ4JCdHp3ODBg2XAgAE+3aIfGRmpo4u7MSx+CNdpiY6OlrJly2rvca5cueTQoUO64eFrgK936dJFgwMYmRYtWqRh8eUW/enTp8vt27dl27Ztbl8WTsP8EMq+MepgdEE4cBuf4wOjzt+04wd4cYs+rlODkGzcuFEyZMjg9ufnyOInXb3Owm/n3hjXVly6dKluPDi2iYiI0F5lTMMAIcIxQadOnfQaLytWrNAm/qTk89IW/blz5+rFmbZs2SJZs2ZNluVhWPxA37599bc/2Jtivo5jF4QBrfLFihXTx+AiR7gfwYCePXvqxY1wxS9A435YWJh4C4fDob/+xbQrqWOVR48eyYgRI6Ro0aJ66T/ApTMwkroTW/Q9jC36nscWfSI34wE+kRHDQmTEsBAZMSxERgwLkRHDQmTEsBAZMSxERgwLkRHDQmTE/xtGZMSRhciIYSEyYliIjBgWIiOGhciIYSEyYliIjBgWIiOGhciIYSEyYliIjBgWIiOGhciIYSEyYliIjBgWIiOGhciIYSEyYliIxOZ/T4d3FbPW4PEAAAAASUVORK5CYII=", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from diagram import diagram, adjust, Bbox\n", "\n", "width, height, x, y = [1.83, 1.24, 0.49, 0.85]\n", "ax = diagram(width, height)\n", "bbox = binding1.draw(ax, x, y)\n", "# adjust(x, y, bbox)" ] }, { "cell_type": "markdown", "id": "fc778385", "metadata": {}, "source": [ "### When to Use a Dictionary\n", "\n", "You use a dictionary when:\n", "- You need labeled data\n", "- You want fast lookups by name\n", "- You need a mapping relationship\n", "\n", "Examples of dictionaries:\n", "\n", "- Student records\n", "- **Configuration** settings\n", "- Word counts\n", "- **JSON** data" ] }, { "cell_type": "markdown", "id": "6ef15bbc", "metadata": {}, "source": [ "## Creating Dictionaries\n", "\n", "Python provides several ways to create a dictionary, depending on whether you already have the data or are building it incrementally. T \n", "\n", "1. **dict literal**: the most common approach to create a dictionary\n", "2. `dict()` constructor: to turn sequences into dictionaries\n", "3. dictionary comprehensions: are useful when keys and values come from other sources" ] }, { "cell_type": "markdown", "id": "657c28ae", "metadata": {}, "source": [ "Python also has a `dict.fromkeys()` method, which is a special case in creating dictionaries. Overall, common ways ways to create a dictionary include:\n", "\n", "| # | Method | Syntax | Notes |\n", "|---|---|---|---|\n", "| 1 | Empty dict literal | `{}` | Fastest way to create an empty dict |\n", "| 2 | Dict literal | `{'a': 1, 'b': 2}` | Keys and values known up front |\n", "| 3 | `dict()` constructor | `dict(a=1, b=2)` | Keys must be valid identifiers |\n", "| 4 | From list of tuples | `dict([('a', 1), ('b', 2)])` | Useful when pairs are already in a sequence |\n", "| 5 | `dict.fromkeys()` | `dict.fromkeys(['a', 'b'], 0)` | All keys share the same default value |\n", "| 6 | Dict comprehension | `{k: v for k, v in items}` | Build from any iterable with an expression |" ] }, { "cell_type": "markdown", "id": "9e3f77f0", "metadata": {}, "source": [ "Pay attention to ways 2, 3, and 4. We usually use dict literal for creating dictionaries but you should know how to use the `dict()` constructor to turn a sequence into a dictionary. Also, try to transfer your skill in list comprehension and tuple comprehension to dictionary comprehension. " ] }, { "cell_type": "code", "execution_count": 5, "id": "fe26184b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Empty literal: {}\n", "Dict literal: {'zero': 0, 'one': 1, 'two': 2}\n", "dict() keywords: {'zero': 0, 'one': 1, 'two': 2}\n", "dict() from tuples: {'zero': 0, 'one': 1, 'two': 2}\n", "dict.fromkeys(): {'zero': 0, 'one': 0, 'two': 0}\n", "Dict comprehension: {'zero': 0, 'one': 1, 'two': 2}\n" ] } ], "source": [ "# 1. Empty dict literal\n", "d1 = {}\n", "\n", "# 2. Dict literal with items\n", "d2 = {'zero': 0, 'one': 1, 'two': 2}\n", "\n", "# 3. dict() constructor with keyword arguments (keys must be valid identifiers)\n", "d3 = dict(zero=0, one=1, two=2)\n", "\n", "# 4. dict() from a list of (key, value) tuples\n", "d4 = dict([('zero', 0), ('one', 1), ('two', 2)])\n", "\n", "# 5. dict.fromkeys() — all keys share the same default value\n", "d5 = dict.fromkeys(['zero', 'one', 'two'], 0)\n", "\n", "# 6. Dict comprehension\n", "words = ['zero', 'one', 'two']\n", "d6 = {word: idx for idx, word in enumerate(words)} # note the two variables\n", "\n", "print(\"Empty literal: \", d1)\n", "print(\"Dict literal: \", d2)\n", "print(\"dict() keywords: \", d3)\n", "print(\"dict() from tuples: \", d4)\n", "print(\"dict.fromkeys(): \", d5)\n", "print(\"Dict comprehension: \", d6)" ] }, { "cell_type": "markdown", "id": "e5909815", "metadata": {}, "source": [ "To give some details about dictionary creation, let's use the dictionary literal to create a dictionary, which is to put the items inside curly braces. " ] }, { "cell_type": "code", "execution_count": 6, "id": "d73e8aab", "metadata": {}, "outputs": [], "source": [ "numbers = {'zero': 0, 'one': 1, 'two': 2}" ] }, { "cell_type": "markdown", "id": "b79066d8", "metadata": {}, "source": [ "Each item consists of a **key** and a **value** separated by a **colon**.\n", "The items are separated by commas and enclosed in curly braces.\n", "\n", "Another way to create a dictionary is to use the `dict` function.\n", "We can make an empty dictionary like this." ] }, { "cell_type": "code", "execution_count": 7, "id": "f597dc41", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{}" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "empty = dict()\n", "empty" ] }, { "cell_type": "markdown", "id": "991fb3e2", "metadata": {}, "source": [ "Or, if you have a list like [ \"zero\", \"one\", \"two\"], you can use `enumerate()` to create a dictionary." ] }, { "cell_type": "code", "execution_count": 8, "id": "888528e3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'zero': 0, 'one': 1, 'two ': 2}\n" ] } ], "source": [ "lst = [\"zero\", \"one\", \"two \"]\n", "\n", "dict_words = {}\n", "for idx, word in enumerate(lst):\n", " dict_words[word] = idx\n", "\n", "print(dict_words)" ] }, { "cell_type": "markdown", "id": "d5cbea30", "metadata": {}, "source": [ "And we can make a copy of a dictionary like this." ] }, { "cell_type": "code", "execution_count": 9, "id": "88f7eab1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'zero': 0, 'one': 1, 'two': 2}" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "numbers_copy = dict(numbers)\n", "numbers_copy" ] }, { "cell_type": "markdown", "id": "959ce6d9", "metadata": {}, "source": [ "It is often useful to make a copy before performing operations that modify dictionaries." ] }, { "cell_type": "markdown", "id": "53f15908", "metadata": {}, "source": [ "## Core Operations" ] }, { "cell_type": "markdown", "id": "253c1a59", "metadata": {}, "source": [ "Common dictionary operations involve the following methods. \n", "\n", "| Group | Method | Description |\n", "|---|---|---|\n", "| **Reading** | `d.get(key, default)` | Get value safely, no KeyError |\n", "| | `d.keys()` | All keys |\n", "| | `d.values()` | All values |\n", "| | `d.items()` | All key-value pairs |\n", "| **Adding/Updating** | `d.update({...})` | Add or overwrite from another dict |\n", "| | `d.setdefault(key, default)` | Set value only if key doesn't exist |\n", "| **Removing** | `d.pop(key, default)` | Remove & return a specific key |\n", "| | `d.popitem()` | Remove & return last inserted pair |\n", "| | `d.clear()` | Remove everything |\n", "| **Copying/Creating** | `d.copy()` | Shallow copy |\n", "| | `dict.fromkeys(keys, value)` | Create new dict from a list of keys |\n", "| **Checking** | `'key' in d` | Check if key exists |\n", "| | `len(d)` | Count of key-value pairs |" ] }, { "cell_type": "markdown", "id": "278901e5", "metadata": {}, "source": [ "### Accessing Items\n", "\n", "Common ways to access values in a dictionary include:\n", "\n", "- `dict[key]` \n", "- `dict.get(key)`\n", "- `dict.get(key, default)`\n", "\n", "We use square brackets `[]` to access and modify items in a Python dictionary by **key**. Reading a value looks like `dict[key]`, which returns the value stored under `key`.\n", " \n", "If a key you a key you try to access is missing, you will receive an error. To avoid the error, use `dict.get(key)`, which returns `None` or a default value you provide when error. " ] }, { "cell_type": "code", "execution_count": 10, "id": "8df66a13", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Alice\n", "{'name': 'Alice', 'age': 28, 'city': 'Rolla'}\n" ] } ], "source": [ "person = {\n", " \"name\": \"Alice\",\n", " \"age\": 28,\n", " \"city\": \"Rolla\"\n", "}\n", "\n", "# Access an item\n", "print(person[\"name\"]) # Alice\n", "print(person)" ] }, { "cell_type": "markdown", "id": "966d157c", "metadata": {}, "source": [ "`KeyError` when trying to access a nonexistent key. " ] }, { "cell_type": "code", "execution_count": 11, "id": "a572dad5", "metadata": {}, "outputs": [ { "ename": "KeyError", "evalue": "'phone'", "output_type": "error", "traceback": [ "\u001b[31mKeyError\u001b[39m\u001b[31m:\u001b[39m 'phone'\n" ] } ], "source": [ "%%expect KeyError\n", "\n", "print(person[\"phone\"]) # KeyError" ] }, { "cell_type": "markdown", "id": "ee517266", "metadata": {}, "source": [ "When accessing, it is safer to use `dict.get()` to avoid the error because it\n", "\n", "- returns `None` when the key does not exist\n", "- returns a default value you specify when the key does not exist" ] }, { "cell_type": "code", "execution_count": 12, "id": "66f12238", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "None\n", "N/A\n" ] } ], "source": [ "print(person.get(\"phone\")) # None\n", "print(person.get(\"phone\", \"N/A\")) # N/A" ] }, { "cell_type": "markdown", "id": "bfe9aba3", "metadata": {}, "source": [ "To access all the keys and values at once:\n", "\n", "- `keys()` returns a view of all the dictionary's keys\n", "- `values()` returns a view of all the dictionary's values.\n", "- `items()` returns a view of all key-value pairs as tuples." ] }, { "cell_type": "code", "execution_count": 13, "id": "e841ea8c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "zero one two \n", "0 1 2 \n", "zero 0 one 1 two 2 " ] } ], "source": [ "for k in numbers.keys():\n", " print(k, end=' ')\n", "print()\n", "\n", "for v in numbers.values():\n", " print(v, end=' ')\n", "print()\n", "\n", "for k, v in numbers.items():\n", " print(k, v , end=' ')\n" ] }, { "cell_type": "markdown", "id": "2a027a6b", "metadata": {}, "source": [ "The `len` function works on dictionaries; it returns the number of items." ] }, { "cell_type": "code", "execution_count": 14, "id": "1b4ea0c2", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(numbers)" ] }, { "cell_type": "code", "execution_count": 15, "id": "75edaa2a", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Accessing Dictionary Values\n", "# Given the dictionary below:\n", "person = {\"name\": \"Bob\", \"age\": 25, \"city\": \"Chicago\"}\n", "\n", "# 1. Print the value associated with \"name\".\n", "# 2. Use .get() to retrieve \"email\" with a default of \"N/A\".\n", "# 3. Print all keys and values using .items().\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": 16, "id": "1c7bf62e", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bob\n", "N/A\n", "name Bob\n", "age 25\n", "city Chicago\n" ] } ], "source": [ "person = {\"name\": \"Bob\", \"age\": 25, \"city\": \"Chicago\"}\n", "\n", "# 1. Access \"name\"\n", "print(person[\"name\"])\n", "\n", "# 2. Get \"email\" safely with a default\n", "print(person.get(\"email\", \"N/A\"))\n", "\n", "# 3. Iterate with .items()\n", "for key, value in person.items():\n", " print(key, value)" ] }, { "cell_type": "markdown", "id": "53355982", "metadata": {}, "source": [ "### Adding/Updating Items" ] }, { "cell_type": "markdown", "id": "767dd9a6", "metadata": {}, "source": [ "You also use the square brackets to update values. An item assignment like `person[\"age\"] = 30` will either \n", " - updates an existing item, or \n", " - creates a new item if the key does not already exist. \n", "\n", "Note that, since dictionary keys are immutable, you can not modify it directly. " ] }, { "cell_type": "code", "execution_count": 17, "id": "1364437e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'name': 'Bob', 'age': 29, 'city': 'Chicago', 'email': 'alice@rolla.com'}\n" ] } ], "source": [ "# Modify an existing item\n", "person[\"age\"] = 29\n", "\n", "# Add a new item\n", "person[\"email\"] = \"alice@rolla.com\"\n", "\n", "print(person)" ] }, { "cell_type": "markdown", "id": "6c98292a", "metadata": {}, "source": [ "`d.update()` is used to add new key-value pairs or change existing ones in a dictionary. `d.update()` behaves like above but can work with multiple key-value pairs:\n", "\n", "- if the key already exists, its value is replaced\n", "- if the key does not exist, it is added" ] }, { "cell_type": "code", "execution_count": 18, "id": "ee77f927", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'a': 1, 'b': 20, 'c': 3}\n" ] } ], "source": [ "d = {\"a\": 1, \"b\": 2}\n", "d.update({\"b\": 20, \"c\": 3})\n", "\n", "print(d) # {'a': 1, 'b': 20, 'c': 3}" ] }, { "cell_type": "markdown", "id": "9878c801", "metadata": {}, "source": [ "An alternative syntax for `d.update()` is as follows." ] }, { "cell_type": "code", "execution_count": 19, "id": "53c15a08", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'a': 10, 'b': 20, 'c': 3, 'd': 4}\n" ] } ], "source": [ "d.update(a=10, d=4)\n", "print(d) # {'a': 10, 'b': 20, 'c': 3, 'd': 4}" ] }, { "cell_type": "markdown", "id": "73968a37", "metadata": {}, "source": [ "You cannot rename or update a key in place because dictionary keys are immutable. Instead, you could:\n", "\n", "1. Add a new key\n", "2. Copy the value\n", "3. Delete the old key\n", "\n", "You can do all three steps in one line of code, because `pop()` will return the value that's been removed, as shown below. I think that's pretty neat." ] }, { "cell_type": "code", "execution_count": 35, "id": "c60b6dac", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'name': 'Doris', 'years': 29}\n" ] } ], "source": [ "student = {\n", " \"name\": \"Doris\",\n", " \"age\": 29\n", "}\n", "\n", "# Rename key \"age\" to \"years\"\n", "student[\"years\"] = student.pop(\"age\")\n", "\n", "print(student)" ] }, { "cell_type": "code", "execution_count": 21, "id": "a48929a3", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Adding and Updating Dictionary Items\n", "# Start with this dictionary:\n", "person = {\"name\": \"Alice\", \"age\": 28}\n", "\n", "# 1. Add a new key \"email\" with value \"alice@example.com\".\n", "# 2. Update \"age\" to 30.\n", "# 3. Use d.update() to add \"city\": \"Boston\" and change \"name\" to \"Alicia\".\n", "# 4. Print the final dictionary.\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": 22, "id": "39ca8124", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'name': 'Alicia', 'age': 30, 'email': 'alice@example.com', 'city': 'Boston'}\n" ] } ], "source": [ "person = {\"name\": \"Alice\", \"age\": 28}\n", "\n", "# 1. Add \"email\"\n", "person[\"email\"] = \"alice@example.com\"\n", "\n", "# 2. Update \"age\"\n", "person[\"age\"] = 30\n", "\n", "# 3. Use update()\n", "person.update({\"city\": \"Boston\", \"name\": \"Alicia\"})\n", "\n", "# 4. Print\n", "print(person)" ] }, { "cell_type": "markdown", "id": "b7d350b0", "metadata": {}, "source": [ "### Deleting Items\n", "\n", "You can delete items from a dictionary when you no longer need a key-value pair. \n", "\n", "- `del`: The `del` statement removes an item by its key, such as del person[\"city\"]. \n", "- `d.pop()`: Another option is `pop()`, which removes the item and also returns its value, which is useful if you want to use that value later. \n", "- `d.popitem()`: removes and returns the last inserted key–value pair from a dictionary.\n", "- `d.clear()`: removes everything in the dictionary." ] }, { "cell_type": "code", "execution_count": 23, "id": "2d66454f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "person:\t\t {'name': 'Alice', 'age': 29, 'city': 'Rolla', 'email': 'alice@rolla.com'}\n", "city deleted:\t {'name': 'Alice', 'age': 29, 'email': 'alice@rolla.com'}\n", "x_city_email:\t {'name': 'Alice', 'age': 29}\n", "email_popped:\t alice@rolla.com\n", "person_updated\t {'name': 'Alice', 'age': 29}\n", "popped_k_v:\t ('age', 29)\n", "after_popitem:\t {'name': 'Alice'}\n", "after_clear:\t {}\n" ] } ], "source": [ "person = {\n", " \"name\": \"Alice\",\n", " \"age\": 29,\n", " \"city\": \"Rolla\",\n", " \"email\": \"alice@rolla.com\"\n", "}\n", "print(\"person:\\t\\t\", person)\n", "\n", "# Delete an item using del\n", "del person[\"city\"] # in place\n", "print(\"city deleted:\\t\", person)\n", "\n", "# Delete an item using pop()\n", "email_popped = person.pop(\"email\")\n", "\n", "print(\"x_city_email:\\t\", person) # {'name': 'Alice', 'age': 29}\n", "print(\"email_popped:\\t\", email_popped) # alice@rolla.com\n", "\n", "print(\"person_updated\\t\", person)\n", "\n", "# Delete the last added item using popitem() \n", "key, value = person.popitem()\n", "print(\"popped_k_v:\\t\", (key, value)) # ('age', 29) or ('name', 'Alice') depending on the order of items in the dict\n", "print(\"after_popitem:\\t\", person) # {'name': 'Alice'}\n", "\n", "# Clear all items from the dictionary\n", "person.clear()\n", "print(\"after_clear:\\t\", person) # {}" ] }, { "cell_type": "code", "execution_count": 24, "id": "421def9d", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Deleting Dictionary Items\n", "# Start with this dictionary:\n", "person = {\"name\": \"Bob\", \"age\": 25, \"city\": \"Boston\", \"email\": \"bob@email.com\"}\n", "\n", "# 1. Delete \"city\" using del.\n", "# 2. Remove and capture \"email\" using pop(). Print the popped value.\n", "# 3. Print the remaining dictionary.\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": 25, "id": "1954cc0b", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Popped email: bob@email.com\n", "{'name': 'Bob', 'age': 25}\n" ] } ], "source": [ "person = {\"name\": \"Bob\", \"age\": 25, \"city\": \"Boston\", \"email\": \"bob@email.com\"}\n", "\n", "# 1. Delete \"city\"\n", "del person[\"city\"]\n", "\n", "# 2. Pop \"email\"\n", "email_val = person.pop(\"email\")\n", "print(\"Popped email:\", email_val)\n", "\n", "# 3. Print remaining\n", "print(person)" ] }, { "cell_type": "markdown", "id": "4bafae76", "metadata": {}, "source": [ "### Membership Testing\n", "\n", "The `in` membership operator works on dictionaries, too; it tells you whether a **key** exists in the dictionary, which returns `True` if the key is present and `False` if it is not. You can also use `not in` to check that a key is missing. \n", "\n", "Member testing is useful when you want to safely decide whether to access, update, or delete a dictionary item.\n" ] }, { "cell_type": "code", "execution_count": 26, "id": "a50e687e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n", "False\n", "True\n", "Age exists: 29\n" ] } ], "source": [ "person = {\n", " \"name\": \"Alice\",\n", " \"age\": 29,\n", " \"city\": \"Rolla\"\n", "}\n", "\n", "print(\"name\" in person) # True\n", "print(\"email\" in person) # False\n", "print(\"email\" not in person) # True\n", "\n", "if \"age\" in person: # safety: Check if key exists before accessing\n", " print(\"Age exists:\", person[\"age\"])" ] }, { "cell_type": "markdown", "id": "91cba20b", "metadata": {}, "source": [ "The `in` operator does *not* check whether something appears as a value." ] }, { "cell_type": "code", "execution_count": 27, "id": "79ff562e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"Alice\" in person" ] }, { "cell_type": "markdown", "id": "93e478fe", "metadata": {}, "source": [ "To see whether something appears as a **value** in a dictionary, you can use the method `values`, which returns a sequence of values, and then use the `in` operator." ] }, { "cell_type": "code", "execution_count": 28, "id": "5b24c03a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"Alice\" in person.values()" ] }, { "cell_type": "code", "execution_count": 29, "id": "f77a0477", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Membership Testing\n", "# Use the dictionary below:\n", "person = {\"name\": \"Alice\", \"age\": 29, \"city\": \"Rolla\"}\n", "\n", "# 1. Check if \"name\" is in the dictionary and print the result.\n", "# 2. Check if \"phone\" is NOT in the dictionary and print the result.\n", "# 3. Check if \"Alice\" appears as a value and print the result.\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": 30, "id": "1dc0509f", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n", "True\n", "True\n" ] } ], "source": [ "person = {\"name\": \"Alice\", \"age\": 29, \"city\": \"Rolla\"}\n", "\n", "# 1. \"name\" in person\n", "print(\"name\" in person) # True\n", "\n", "# 2. \"phone\" not in person\n", "print(\"phone\" not in person) # True\n", "\n", "# 3. \"Alice\" in values\n", "print(\"Alice\" in person.values()) # True" ] }, { "cell_type": "markdown", "id": "55a0666a", "metadata": {}, "source": [ "## Select Topics " ] }, { "cell_type": "markdown", "id": "df773f07", "metadata": {}, "source": [ "### Dictionary Comprehension\n", "\n", "Dictionary comprehensions provide a concise way to build dictionaries from existing data.\n", "The pattern is similar to a list comprehension, but each result contains a key and a value. \n", "\n", "The basic syntax: \n", "\n", "```python\n", "{key_expr: value_expr for item in iterable}\n", "```" ] }, { "cell_type": "code", "execution_count": 31, "id": "d230f7a5", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Square dict: {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}\n", "Combined dict: {'a': 1, 'b': 2, 'c': 3, 'd': 4}\n", "Expensive fruits: {'orange': 0.8, 'grape': 1.2}\n" ] } ], "source": [ "# Dictionary comprehensions\n", "\n", "# Create a dictionary of squares\n", "square_dict = {x: x**2 for x in range(5)}\n", "print(\"Square dict:\", square_dict)\n", "\n", "# From two lists\n", "keys = ['a', 'b', 'c', 'd']\n", "values = [1, 2, 3, 4]\n", "combined_dict = {k: v for k, v in zip(keys, values)}\n", "print(\"Combined dict:\", combined_dict)\n", "\n", "# Filter and transform\n", "prices = {'apple': 0.50, 'banana': 0.30, 'orange': 0.80, 'grape': 1.20}\n", "expensive_fruits = {fruit: price for fruit, price in prices.items() if price > 0.50}\n", "print(\"Expensive fruits:\", expensive_fruits)" ] }, { "cell_type": "code", "execution_count": 32, "id": "cff2cd5d", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Dictionary Comprehension\n", "# 1. Use a dict comprehension to create a dictionary that maps\n", "# each number 1-5 to its cube (n**3).\n", "# 2. Given the prices dict below, use a dict comprehension to keep\n", "# only fruits that cost more than $1.00.\n", "prices = {'apple': 1.20, 'banana': 0.50, 'cherry': 2.00, 'grape': 0.80}\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": 33, "id": "c768140f", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cubes: {1: 1, 2: 8, 3: 27, 4: 64, 5: 125}\n", "Pricey: {'apple': 1.2, 'cherry': 2.0}\n" ] } ], "source": [ "# 1. Cubes\n", "cubes = {n: n**3 for n in range(1, 6)}\n", "print(\"Cubes:\", cubes)\n", "\n", "# 2. Expensive fruits\n", "prices = {'apple': 1.20, 'banana': 0.50, 'cherry': 2.00, 'grape': 0.80}\n", "pricey = {fruit: price for fruit, price in prices.items() if price > 1.00}\n", "print(\"Pricey:\", pricey)" ] }, { "cell_type": "markdown", "id": "da23616d", "metadata": {}, "source": [ "### Counting with Dictionaries\n", "\n", "Suppose you are given a string and you want to count how many times each letter appears.\n", "A dictionary is a good tool for this job.\n", "We'll start with an empty dictionary.\n" ] }, { "cell_type": "code", "execution_count": 43, "id": "d800452b", "metadata": {}, "outputs": [], "source": [ "counter = {}" ] }, { "cell_type": "markdown", "id": "21732020", "metadata": {}, "source": [ "As we loop through the letters in the string, suppose we see the letter `'a'` for the first time.\n", "We can add it to the dictionary like this." ] }, { "cell_type": "code", "execution_count": 44, "id": "1bac940d", "metadata": {}, "outputs": [], "source": [ "counter['a'] = 1" ] }, { "cell_type": "markdown", "id": "fb83e4ab", "metadata": {}, "source": [ "The value `1` indicates that we have seen the letter once.\n", "Later, if we see the same letter again, we can increment the counter like this." ] }, { "cell_type": "code", "execution_count": 45, "id": "7a29d3c5", "metadata": {}, "outputs": [], "source": [ "counter['a'] += 1" ] }, { "cell_type": "markdown", "id": "a6cd4999", "metadata": {}, "source": [ "Now the value associated with `'a'` is `2`, because we've seen the letter twice." ] }, { "cell_type": "code", "execution_count": null, "id": "2ca074c6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'a': 2}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "counter" ] }, { "cell_type": "markdown", "id": "ca68ff9e", "metadata": {}, "source": [ "The following function uses these features to count the number of times each letter appears in a string." ] }, { "cell_type": "markdown", "id": "a91d784b", "metadata": {}, "source": [ "(value_counts)=" ] }, { "cell_type": "code", "execution_count": null, "id": "c9be0de9", "metadata": {}, "outputs": [], "source": [ "def value_counts(string):\n", " counter = {}\n", " for letter in string:\n", " if letter not in counter:\n", " counter[letter] = 1\n", " else:\n", " counter[letter] += 1\n", " return counter" ] }, { "cell_type": "markdown", "id": "cb1c1f64", "metadata": {}, "source": [ "Each time through the loop, if `letter` is not in the dictionary, we create a new item with key `letter` and value `1`.\n", "If `letter` is already in the dictionary we increment the value associated with `letter`.\n", "\n", "Here's an example." ] }, { "cell_type": "code", "execution_count": null, "id": "e4dbc1c3", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "counter = value_counts('brontosaurus')\n", "counter" ] }, { "cell_type": "markdown", "id": "75ae9b41", "metadata": {}, "source": [ "The items in `counter` show that the letter `'b'` appears once, `'r'` appears twice, and so on." ] }, { "cell_type": "code", "execution_count": null, "id": "b52d3ba5", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Counting with a Dictionary\n", "# 1. Use the value_counts() function defined above to count the\n", "# frequency of each letter in the word \"mississippi\".\n", "# 2. Print the letter that appears the most (highest count).\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": null, "id": "962130bf", "metadata": { "tags": [ "hide-input" ] }, "outputs": [], "source": [ "### solution\n", "\n", "# 1. Count letters\n", "result = value_counts(\"mississippi\")\n", "print(result)\n", "\n", "# 2. Most frequent letter\n", "most_common = max(result, key=result.get)\n", "print(\"Most common letter:\", most_common, \"->\", result[most_common])" ] }, { "cell_type": "markdown", "id": "912bdf5d", "metadata": {}, "source": [ "### Iterating Through Dictionaries\n", "\n", "If you use a dictionary in a `for` statement, it traverses the keys of the dictionary.\n", "To demonstrate, let's make a dictionary that counts the letters in `'banana'`.\n" ] }, { "cell_type": "code", "execution_count": 37, "id": "310e1489", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'b': 1, 'a': 3, 'n': 2}" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "counter = value_counts('banana')\n", "counter" ] }, { "cell_type": "markdown", "id": "fe263f3d", "metadata": {}, "source": [ "The following loop prints the keys, which are the letters." ] }, { "cell_type": "code", "execution_count": 38, "id": "da4ec7fd", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "b\n", "a\n", "n\n" ] } ], "source": [ "for key in counter:\n", " print(key)" ] }, { "cell_type": "markdown", "id": "bf1b7824", "metadata": {}, "source": [ "To print the values, we can use the `values` method." ] }, { "cell_type": "code", "execution_count": 39, "id": "859fe1ad", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "3\n", "2\n" ] } ], "source": [ "for value in counter.values():\n", " print(value)" ] }, { "cell_type": "markdown", "id": "721135be", "metadata": {}, "source": [ "To print the keys and values, we can loop through the keys and look up the corresponding values." ] }, { "cell_type": "code", "execution_count": 40, "id": "7242ab5b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "b 1\n", "a 3\n", "n 2\n" ] } ], "source": [ "for key in counter:\n", " value = counter[key]\n", " print(key, value)" ] }, { "cell_type": "code", "execution_count": 41, "id": "e533c7d7", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Iterating Through a Dictionary\n", "# Use this dictionary:\n", "scores = {\"alice\": 92, \"bob\": 85, \"charlie\": 78}\n", "\n", "# 1. Print only the names (keys).\n", "# 2. Print only the scores (values).\n", "# 3. Print each name and score together using .items().\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": 42, "id": "edcc0f5d", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "alice\n", "bob\n", "charlie\n", "92\n", "85\n", "78\n", "alice 92\n", "bob 85\n", "charlie 78\n" ] } ], "source": [ "scores = {\"alice\": 92, \"bob\": 85, \"charlie\": 78}\n", "\n", "# 1. Keys only\n", "for name in scores:\n", " print(name)\n", "\n", "# 2. Values only\n", "for score in scores.values():\n", " print(score)\n", "\n", "# 3. Key-value pairs\n", "for name, score in scores.items():\n", " print(name, score)" ] }, { "cell_type": "markdown", "id": "be226db8", "metadata": {}, "source": [ "### Why Dictionary Lookup Is Fast\n", "\n", "The items in a Python dictionary are stored in a **hash table**, which is a way of organizing data that has a remarkable property: the `in` operator takes about the same amount of time no matter how many items are in the dictionary.\n", "That makes it possible to write some remarkably efficient algorithms.\n" ] }, { "cell_type": "markdown", "id": "6bf8f5d2", "metadata": {}, "source": [ "(dict-bigo)=\n", ":::{note} Big O Notation\n", "\n", "**Big O notation** is a way of describing how the time (or memory) an operation needs grows as the size of the data grows. We use the letter *n* to represent the number of items.\n", "\n", "The two cases you'll encounter most often here:\n", "\n", "| Notation | Name | Meaning |\n", "|---|---|---|\n", "| O(1) | Constant time | Time stays the same regardless of *n* |\n", "| O(n) | Linear time | Time grows in proportion to *n* |\n", "\n", "Imagine searching for a word in a book.\n", "\n", "- **O(1)** is like looking up a word in a dictionary: you go directly to the page. You know exactly which page to turn to, so the search takes the same time no matter how thick the book is, that's O(1).\n", "- **O(n)** is like finding a word in a novel: you read until you find it. The worst case is you may have to scan every page until the end of the book, that's O(n): the more pages you have, the more time it would likely to take.\n", "\n", "Dictionary lookup is O(1) because Python computes a **hash** of the key and jumps directly to the right slot in memory, without scanning. List lookup with `in` is O(n) because Python checks each element in order until it finds a match (or reaches the end).\n", "\n", "The full treatment of Big O notation — including O(log n), O(n²), and others — comes in the Algorithms chapter.\n", ":::" ] }, { "cell_type": "markdown", "id": "21a79d6e", "metadata": {}, "source": [ "The following example builds a list and a dictionary with one million entries, then times a worst-case lookup in each. It shows the difference between O(n) linear search (list) and O(1) constant-time lookup (dictionary) in practice.\n", "\n" ] }, { "cell_type": "code", "execution_count": 66, "id": "e5071e5e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "List lookup (O(n)): 0.003670 s\n", "Dict lookup (O(1)): 0.000019 s\n", "Dict was ~192x faster\n" ] } ], "source": [ "import time\n", "\n", "# Build a large list and a large dictionary with the same 1 million keys\n", "n = 1_000_000\n", "big_list = list(range(n))\n", "big_dict = {i: True for i in range(n)}\n", "\n", "target = n - 1 # worst case: last element\n", "\n", "# O(n): list search time scales up to n elements\n", "start = time.time()\n", "result = target in big_list\n", "list_time = time.time() - start\n", "\n", "# O(1): dict lookup jumps directly\n", "start = time.time()\n", "result = target in big_dict\n", "dict_time = time.time() - start\n", "\n", "print(f\"List lookup (O(n)): {list_time:.6f} s\")\n", "print(f\"Dict lookup (O(1)): {dict_time:.6f} s\")\n", "print(f\"Dict was ~{list_time / dict_time:.0f}x faster\")" ] }, { "cell_type": "markdown", "id": "7dc9ee5e", "metadata": {}, "source": [ "To demonstrate, we'll compare two algorithms for finding pairs of words where one is the reverse of another -- like `stressed` and `desserts`.\n", "We'll start by reading the word list." ] }, { "cell_type": "code", "execution_count": 1, "id": "b3abef30", "metadata": {}, "outputs": [], "source": [ "from pathlib import Path\n", "words_file = Path('../../data/words.txt')\n", "if not words_file.exists():\n", " download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt', words_file)" ] }, { "cell_type": "code", "execution_count": 2, "id": "5e79453d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "113783\n", "\n" ] } ], "source": [ "word_list = words_file.read_text().split()\n", "\n", "print(len(word_list))\n", "print(type(word_list))" ] }, { "cell_type": "markdown", "id": "7dae7359", "metadata": {}, "source": [ "To check out the file content:" ] }, { "cell_type": "code", "execution_count": 3, "id": "55a7e052", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "aa\n", "aah\n", "aahed\n", "aahing\n", "aahs\n", "aal\n", "aalii\n", "aaliis\n", "aals\n", "aardvark\n" ] } ], "source": [ "for word in word_list[:10]:\n", " print(word)" ] }, { "cell_type": "markdown", "id": "2f2bac00", "metadata": {}, "source": [ "And here's the `reverse_word` function." ] }, { "cell_type": "code", "execution_count": 4, "id": "b907de3b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'olleh'" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def reverse_word(word):\n", " return ''.join(reversed(word))\n", "\n", "reverse_word('hello')" ] }, { "cell_type": "markdown", "id": "a135f873", "metadata": {}, "source": [ "The following function loops through the words in the list.\n", "For each one, it reverses the letters and then checks whether the reversed word is in the word list." ] }, { "cell_type": "code", "execution_count": 5, "id": "dfaac85d", "metadata": {}, "outputs": [], "source": [ "def too_slow():\n", " count = 0\n", " for word in word_list:\n", " if reverse_word(word) in word_list: ### O(n) lookup in a list is slow\n", " count += 1\n", " return count" ] }, { "cell_type": "markdown", "id": "a5b60786", "metadata": {}, "source": [ "To measure how long a function takes, we can use `%time` which is one of Jupyter's \"built-in magic commands\".\n", "These commands are not part of the Python language, so they might not work in other development environments." ] }, { "cell_type": "markdown", "id": "3b737103", "metadata": {}, "source": [ "```python\n", "%time too_slow()\n", "```\n", "Output:\n", "```python\n", "CPU times: user 1min 9s, sys: 182 ms, total: 1min 9s\n", "Wall time: 1min 9s\n", "\n", "885\n", "```" ] }, { "cell_type": "markdown", "id": "4268dac5", "metadata": {}, "source": [ "Uncomment the line to run the command in Live Code mode or in your editor." ] }, { "cell_type": "code", "execution_count": 53, "id": "0fda8ec0", "metadata": {}, "outputs": [], "source": [ "# %time too_slow()" ] }, { "cell_type": "markdown", "id": "545e2247", "metadata": {}, "source": [ "This function takes more than a minute to run.\n", "The problem is that the `in` operator checks the words in the list one at a time, starting at the beginning.\n", "If it doesn't find what it's looking for -- which happens most of the time -- it has to search all the way to the end." ] }, { "cell_type": "markdown", "id": "e7f68731", "metadata": {}, "source": [ "And the `in` operator is inside the loop, so it runs once for each word.\n", "Since there are more than 100,000 words in the list, and for each one we check more than 100,000 words, the total number of comparisons is the number of words squared -- roughly -- which is almost 13 billion. " ] }, { "cell_type": "code", "execution_count": 54, "id": "0092808d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "12946571089" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(word_list)**2" ] }, { "cell_type": "markdown", "id": "19917c3d", "metadata": {}, "source": [ "We can make this function much faster with a dictionary.\n", "The following loop creates a dictionary that contains the words as keys." ] }, { "cell_type": "code", "execution_count": 6, "id": "47de6063", "metadata": {}, "outputs": [], "source": [ "word_dict = {}\n", "for word in word_list:\n", " word_dict[word] = 1" ] }, { "cell_type": "markdown", "id": "c65e22da", "metadata": {}, "source": [ "Or, you can use dictionary comprehension: " ] }, { "cell_type": "code", "execution_count": 7, "id": "b36fcf70", "metadata": {}, "outputs": [], "source": [ "word_dict = {word: 1 for word in word_list}" ] }, { "cell_type": "markdown", "id": "5400a4bc", "metadata": {}, "source": [ "The values in `word_dict` are all `1`, but they could be anything, because we won't ever look them up -- we will only use this dictionary to check whether a key exists.\n", "\n", "Now here's a version of the previous function that replaces `word_list` with `word_dict`." ] }, { "cell_type": "code", "execution_count": 70, "id": "75120705", "metadata": {}, "outputs": [], "source": [ "def much_faster():\n", " count = 0\n", " for word in word_dict:\n", " if reverse_word(word) in word_dict:\n", " count += 1\n", " return count" ] }, { "cell_type": "markdown", "id": "d87baa51", "metadata": {}, "source": [ "This function takes less than one hundredth of a second, so it's about 10,000 times faster than the previous version." ] }, { "cell_type": "markdown", "id": "e5d80228", "metadata": {}, "source": [ "In general, the time it takes to find an element in a list is proportional to the length of the list.\n", "The time it takes to find a key in a dictionary is almost constant -- regardless of the number of items." ] }, { "cell_type": "code", "execution_count": 59, "id": "54da29ff", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 31.9 ms, sys: 1.76 ms, total: 33.7 ms\n", "Wall time: 33.5 ms\n" ] }, { "data": { "text/plain": [ "885" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%time much_faster()" ] }, { "cell_type": "code", "execution_count": null, "id": "518de41c", "metadata": { "tags": [ "thebe-interactive" ] }, "outputs": [], "source": [ "### Exercise: Dictionary vs. List Lookup\n", "# Given the list of fruits below:\n", "fruits = ['apple', 'banana', 'cherry', 'date', 'elderberry']\n", "\n", "# 1. Create a dictionary with fruits as keys and 1 as values using dict comprehension.\n", "# 2. Use the `in` operator to check if 'cherry' is in:\n", "# a) the list b) the dictionary\n", "# 3. Print both results.\n", "### Your code starts here.\n", "\n", "\n", "\n", "### Your code ends here." ] }, { "cell_type": "code", "execution_count": null, "id": "6ff7ed63", "metadata": { "tags": [ "hide-input" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n", "True\n" ] } ], "source": [ "### solution\n", "\n", "fruits = ['apple', 'banana', 'cherry', 'date', 'elderberry']\n", "\n", "# 1. Build lookup dictionary\n", "fruit_dict = {fruit: 1 for fruit in fruits}\n", "\n", "# 2 & 3. Check membership and print\n", "print('cherry' in fruits) # True -- linear search\n", "print('cherry' in fruit_dict) # True -- hash lookup (O(1))" ] } ], "metadata": { "celltoolbar": "Tags", "kernelspec": { "display_name": ".venv", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.7" } }, "nbformat": 4, "nbformat_minor": 5 }