{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "55a0666a",
   "metadata": {},
   "source": [
    "# Select Topics "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f0c8403",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "# Find project root by looking for _config.yml\n",
    "current = Path.cwd()\n",
    "for parent in [current, *current.parents]:\n",
    "    if (parent / '_config.yml').exists():\n",
    "        project_root = parent\n",
    "        break\n",
    "else:\n",
    "    project_root = Path.cwd().parent.parent\n",
    "\n",
    "# Add project root to path\n",
    "sys.path.insert(0, str(project_root))\n",
    "\n",
    "# Import shared teaching helpers and cell magics\n",
    "from shared import thinkpython, diagram, jupyturtle, structshape\n",
    "from shared.download import download\n"
   ]
  },
  {
   "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",
      "<class 'list'>\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
}