{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Seminar 01: Python Basics\n", "\n", "Welcome to Python seminars!\n", "\n", "Our goal for today is that you become familiar with Python basic syntax, terminology and ideas.\n", "\n", "We hope by the end you can write and run simple Python programs.\n", "\n", "Topics:\n", "\n", "1. Basic types\n", "2. Collections and Time Complexity\n", "3. Immutability\n", "4. Functions\n", "\n", "---" ], "id": "dbf0406fae42f243" }, { "metadata": {}, "cell_type": "markdown", "source": "### **How to launch python**", "id": "ab8018ee9effadb5" }, { "metadata": {}, "cell_type": "code", "source": [ "# show in terminal\n", "! python #REPL\n", "! ipython #IPython" ], "id": "126f59bdd681e8c5", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "You can run the course materials as Jupyter Notebooks (which we are already using).", "id": "f7a182b0e6204092" }, { "metadata": {}, "cell_type": "code", "source": [ "! pip install notebook\n", "! jupyter notebook" ], "id": "63a72640196b8d45", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Basic Types\n", "\n", "In Python, variables are not bound to a specific data type. This means you don’t have to declare their type explicitly. Because the type is determined automatically at runtime, Python is called a dynamically typed language.\n", "\n" ], "id": "8a49ad3183db8741" }, { "metadata": {}, "cell_type": "code", "source": [ "# int\n", "x = 1\n", "print(type(x))\n", "\n", "# float\n", "x = 1.0 # we changed the type of variable\n", "print(type(x))\n", "\n", "#complex\n", "x = 1j \n", "print(type(x))" ], "id": "6264f8ee7eccdf17", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "### Numeric types", "id": "b9454eb3aee9139" }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Problem**\n", "\n", "A phone has a 64 GB memory card. The system uses 2 GB and installed apps use another 6 GB. Each photo is a 20 MB image plus a 4 MB thumbnail.\n", "\n", "Work out the following:\n", "\n", "- space free after the system and apps?\n", "- the size of one photo?\n", "- the number of photos that fit\n", "- space after all possible photos are taken" ], "id": "7897a3b65aa9b57e" }, { "metadata": {}, "cell_type": "code", "source": [ "card = 64 * 1024 # GB -> MB\n", "used = (2 + 6) * 1024 # system + apps, GB -> MB\n", "free = card - used\n", "photo_size = 20 + 4 # image + thumbnail\n", "photos = free / photo_size # how many photos fit?\n", "print(photos)\n", "type(photos)" ], "id": "6ff99025ffe2bbf7", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "Can you see the problem in the code above?", "id": "b59eb375fe906b9" }, { "metadata": {}, "cell_type": "code", "source": [ "photos = free // photo_size # integer photos!\n", "leftover = free % photo_size\n", "photos, leftover" ], "id": "591a6b2f54327349", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": "### Boolean types", "id": "bafa067c6a02b797" }, { "metadata": {}, "cell_type": "code", "source": [ "(4 < 5, # less\n", "4 <= 3, # less or equal\n", "4 == 3, # equal\n", "4 != 3, # not equal\n", "5 > 6, # greater\n", "5 >= 6) # greater or equal" ], "id": "71bce79898f93f14", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# problem\n", "my_list = [1, 2, 3, 4, 5]\n", "idx = 10\n", "\n", "condition_one = idx < len(my_list)\n", "condition_two = my_list[idx] % 2 == 0\n", "\n", "if condition_one and condition_two:\n", " print(f\"Number at index {idx} is even and equal to {my_list[idx]}\")\n", "else:\n", " print(f\"Number at index {idx} is not even or does not exist\")" ], "id": "2a5ffdbd1249e55f", "outputs": [], "execution_count": null }, { "cell_type": "code", "metadata": {}, "source": [ "# solution: short-circuiting\n", "if idx < len(my_list) and my_list[idx] % 2 == 0:\n", " print(f\"Number at index {idx} is even and equal to {my_list[idx]}\")\n", "else:\n", " print(f\"Number at index {idx} is not even or does not exist\")" ], "id": "4d6818b47f998a24", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# short-circuiting; we won't evaluate the second operand if the first one is enough to determine the result\n", "\n", "print(False and NON_EXISTING_VARIABLE)\n", "print(True or NON_EXISTING_VARIABLE)" ], "id": "f70fe44d324062f5", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": "### Type Conversion", "id": "40b962567e9820d5" }, { "metadata": {}, "cell_type": "code", "source": [ "# What the result is?\n", "True + 1" ], "id": "56df674a3d9c029d", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# note: float is structural subtype of int\n", "1 + 1.0" ], "id": "29794d91351502af", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# no support for equality check between string and int types\n", "\"1\" == 1, \\\n", "\"1\" == 1.0, \\\n", "\"1\" == True" ], "id": "e3d93be1154601ed", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "True == 1, \\\n", "1.0 == 1" ], "id": "5f0243c9f84a99ff", "outputs": [], "execution_count": null }, { "cell_type": "code", "metadata": {}, "source": [ "#Explicit (you call a constructor)\n", "\n", "print(int(\"123\")) # 123\n", "print(float(\"3.14\")) # 3.14\n", "print(str(42)) # \"42\"\n", "print(bool([])) # False – empty containers are falsy." ], "id": "342d2333f9a40a33", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Strings\n", "\n" ], "id": "fba7230d46c651e" }, { "metadata": {}, "cell_type": "code", "source": [ "hello = \"'Hello'\"\n", "avocado = '\"avocado\"'\n", "\n", "# several lines\n", "multiline = \"\"\"\n", " ...\n", " 'multi'\n", " \"line\"\n", " '''\n", " ...\n", "\"\"\"\n", "\n", "pineapple = '''\n", " ...\n", " 'pine'\n", " \"apple\"\n", " \"\"\"\n", " ...\n", "'''\n", "\n", "print(hello, avocado, multiline, pineapple)\n", "print(\"Length of 'Hello' string: \", len(hello)) #we can get string length\n", "type(hello), type(multiline)" ], "id": "43c43684e82d1e90", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Task.** A phone number arrives as a string in the format:\n", "\n", "```python\n", "phone_number = \"+1-415-5551234\"\n", "```\n", "\n", "A phone number is considered **malicious** if, after replacing every `\"-\"` character with `\"0\"`, the resulting string contains `\"000\"` as a substring.\n", "\n", "If the number is malicious, return `None`.\n", "\n", "Otherwise, return the phone number in this format:\n", "\n", "```text\n", " \n", "```\n", "\n", "For example:\n", "\n", "```text\n", "\"+1-415-5551234\" → \"1 415 555 1234\"\n", "```\n" ], "id": "9a0e7e35e36184ba" }, { "metadata": {}, "cell_type": "code", "source": [ "phone = \"+1-415-5551234\"\n", "\n", "check = phone.replace(\"-\", \"0\")\n", "\n", "if \"000\" in check:\n", " result = None\n", "else:\n", " parts = phone[1:].split(\"-\")\n", "\n", " country = parts[0]\n", " region = parts[1]\n", " local = parts[2]\n", "\n", " result = \" \".join([\n", " country,\n", " region,\n", " local[:3],\n", " local[3:]\n", " ])\n", "\n", "print(result)" ], "id": "e75e095e110ca104", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": "Strings are immutable", "id": "8c6a1fb88166af15" }, { "cell_type": "code", "metadata": {}, "source": [ "text = \"some_text\"\n", "text [0] = \"S\"" ], "id": "e3e1949a6ecff891", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "words = [\"some_text\"] * 100000\n", "\n", "%%timeit\n", "# Bad example\n", "text_with_hyphen = words[0]\n", "for word in words[1:]:\n", " text_with_hyphen += \"-\" + word" ], "id": "a447391f5b524417", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "%%timeit\n", "'-'.join(words)" ], "id": "84a8fc38ca5eaf70", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "**Almost 10x faster! Why?**", "id": "e1d6d8af430ed1df" }, { "metadata": {}, "cell_type": "markdown", "source": "Strings are immutable objects, so when we execute `+=' on each iteration of the loop, we create a new string with the result of concatenation. So we are allocating unnecessary memory.", "id": "1fc71bfb5496e89e" }, { "metadata": {}, "cell_type": "markdown", "source": [ "**Why is join faster?**\n", "\n", "Because it calculates the total length of the resulting string and allocates memory for it only once. Then it copies all the strings into the new memory space." ], "id": "4f234f365117a5e4" }, { "metadata": {}, "cell_type": "markdown", "source": [ "### None\n", "\n", "In Python, every value is an object and every class is subclass of object.\n", "\n", "An object has:\n", "\n", "- a type\n", "- an identity\n", "- a value/state\n" ], "id": "ae8993ec96a1e1bf" }, { "metadata": {}, "cell_type": "code", "source": [ "x = 42\n", "name = \"Alice\"\n", "numbers = [1, 2, 3]\n", "\n", "print(isinstance(x, object))\n", "print(isinstance(name, object))\n", "print(isinstance(numbers, object))" ], "id": "d03dad7c88f75dca", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "a = [1, 2, 3]\n", "b = a\n", "c = [1, 2, 3]\n", "\n", "print(id(a))\n", "print(id(b))\n", "print(id(c))\n", "\n", "print(a is b)\n", "print(a is c)" ], "id": "5e8a43bd8e925763", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "In CPython specifically, id() is implemented using the object's memory address.", "id": "ad7f3bffb2635fea" }, { "cell_type": "markdown", "metadata": {}, "source": "## Collections and Time Complexity", "id": "e1ca5d7177e3b5e6" }, { "metadata": {}, "cell_type": "markdown", "source": "### List", "id": "80e3234ba0fb47dd" }, { "metadata": {}, "cell_type": "code", "source": [ "numbers = [10, 20, 30, 40]\n", "\n", "print(numbers[2]) # O(1) - access by index\n", "\n", "numbers[2] = 35 # O(1) - assignment by index\n", "\n", "numbers.append(50) # O(1) amortized - add one element to the end\n", "\n", "numbers.extend([60, 70, 80]) # O(k) - add k elements to the end\n", "# Usually faster than calling append() k times in a Python loop.\n", "\n", "print(70 in numbers) # O(n) - may need to check every element\n", "\n", "numbers.insert(0, 5) # O(n) - elements must be shifted right\n", "\n", "numbers.pop() # O(1) - remove the last element\n", "\n", "numbers.pop(0) # O(n) - remaining elements must be shifted left\n", "\n", "print(len(numbers)) # O(1) - list stores its current size" ], "id": "533c3345f298bd9d", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### List: Task\n", "\n", "Remove all zeros from the list" ], "id": "9aacfa5498e234e9" }, { "metadata": {}, "cell_type": "code", "source": [ "# Guess time and memory complexity\n", "\n", "def remove_all_zeros_v1(numbers: list[int]):\n", " while 0 in numbers:\n", " numbers.remove(0)\n", "\n", " return numbers\n", "\n", "\n", "def remove_all_zeros_v2(numbers: list[int]):\n", " for i in range(len(numbers) - 1, -1, -1):\n", " if numbers[i] == 0:\n", " numbers.pop(i)\n", "\n", " return numbers\n", "\n", "\n", "def remove_all_zeros_v3(numbers: list[int]):\n", " result = []\n", " for number in numbers:\n", " if number != 0:\n", " result.append(number)\n", " return result\n", "\n", "\n", "data = [1, 0, 2, 0, 3, 0, 4]\n", "\n", "print(remove_all_zeros_v1(data))\n", "print(remove_all_zeros_v2(data))\n", "print(remove_all_zeros_v3(data))" ], "id": "c63295f68be7db75", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "### Set", "id": "57b96d23f03dbbac" }, { "metadata": {}, "cell_type": "code", "source": [ "numbers = {10, 20, 30, 40}\n", "\n", "print(30 in numbers) # O(1) average - membership check\n", "\n", "numbers.add(50) # O(1) average - add an element\n", "\n", "numbers.add(30) # O(1) average - existing element changes nothing\n", "\n", "numbers.remove(20) # O(1) average - remove an element\n", "# Raises KeyError if the element does not exist.\n", "\n", "numbers.discard(100) # O(1) average - remove if present\n", "# Does nothing if the element does not exist.\n", "\n", "print(len(numbers)) # O(1) - set stores its current size" ], "id": "d4866ceaed661c36", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### How does a set achieve O(1) lookup?\n", "\n", "Suppose we have a table with several slots:\n", "\n", "```text\n", "index: 0 1 2 3 4 5 6 7\n", " +-----+-----+-----+-----+-----+-----+-----+-----+\n", " | | | | | | | | |\n", " +-----+-----+-----+-----+-----+-----+-----+-----+\n", "```\n", "\n", "For an element x, Python first computes:\n", "\n", "```python\n", "hash(x)\n", "```\n", "\n", "The hash is an integer that Python uses to determine approximately where the object should be stored in the table.\n", "\n", "So instead of checking:\n", "\n", "element 1\n", "element 2\n", "element 3\n", "...\n", "\n", "Python can jump directly to a small region of the table.\n", "\n", "This is why membership testing is approximately:\n", "\n", "```python\n", "x in my_set # O(1) average\n", "```" ], "id": "cefcf2c86b3ff017" }, { "metadata": {}, "cell_type": "code", "source": [ "print(hash(\"cat\"))\n", "print(hash(\"dog\"))\n", "print(hash(123))\n", "print(hash((1, 2)))" ], "id": "d62921b565ce85e5", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Hash collisions\n", "\n", "Hashes are **not unique identifiers**.\n", "\n", "Two different objects may produce the same hash, or may map to the same region of the hash table.\n", "\n", "This is called a **hash collision**.\n", "\n", "Conceptually:\n", "\n", "```text\n", "hash(A) ----+\n", " +----> same table position\n", "hash(B) ----+\n", "```\n", "\n", "Therefore Python cannot assume:\n", "\n", "```text\n", "same hash => same object\n", "```\n", "\n", "When a collision occurs, Python has to inspect additional table locations and may also compare the objects for equality.\n", "\n", "This is one reason why set operations are described as O(1) average, rather than guaranteed O(1)." ], "id": "8df2d57f30bd3ef0" }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Task: list or set?\n", "\n", "Consider the two implementations below.\n", "\n", "What is the time and memory complexity of each one?" ], "id": "24bebe8305676d81" }, { "metadata": {}, "cell_type": "code", "source": [ "def has_duplicates_v1(values: list):\n", " seen = []\n", "\n", " for x in values:\n", " if x in seen:\n", " return True\n", "\n", " seen.append(x)\n", "\n", " return False\n", "\n", "\n", "def has_duplicates_v2(values: list):\n", " seen = set()\n", "\n", " for x in values:\n", " if x in seen:\n", " return True\n", "\n", " seen.add(x)\n", "\n", " return False\n", "\n", "\n", "def has_duplicates_v3(values: list):\n", " return len(set(values)) != len(values)" ], "id": "56774244f43eee73", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Answer\n", "\n", "| Version | Time Complexity | Extra Memory | Notes |\n", "|---|---:|---:|---|\n", "| `v1` | `O(n²)` worst case | `O(n)` | Slow because `x in seen` is `O(n)` for a list |\n", "| `v2` | `O(n)` average | `O(n)` | Fast and can stop early when a duplicate is found |\n", "| `v3` | `O(n)` average | `O(n)` | Shortest and simplest, but always processes the whole input |\n", "\n", "#### Best choice\n", "\n", "Usually, `v2` is the best implementation:\n", "\n", "- same asymptotic complexity as `v3`\n", "- can return early as soon as a duplicate is found\n", "- makes the algorithmic idea explicit\n", "\n", "`v3` is the most concise and is often preferable when readability is the main goal." ], "id": "8f9453cbb5d3eaad" }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Another Task\n", "\n", "Given lists `a` and `b`, return the **unique elements that occur in both lists**.\n", "\n", "The order of the returned elements does **not** matter.\n", "\n", "Example:\n", "\n", "```python\n", "a = [1, 2, 1, 3, 4, 2]\n", "b = [2, 3, 5]\n", "\n", "# -> [2, 3]\n", "# or [3, 2]\n", "```\n", "\n", "What is time and memory complexity of each implementation?" ], "id": "c7919883958ff6bb" }, { "metadata": {}, "cell_type": "code", "source": [ "def common_unique_v1(a: list, b: list):\n", " result = []\n", "\n", " for x in a:\n", " if x in b and x not in result:\n", " result.append(x)\n", "\n", " return result\n", "\n", "\n", "def common_unique_v2(a: list, b: list):\n", " b_set = set(b)\n", " seen = set()\n", " result = []\n", "\n", " for x in a:\n", " if x in b_set and x not in seen:\n", " result.append(x)\n", " seen.add(x)\n", "\n", " return result\n", "\n", "\n", "def common_unique_v3(a: list, b: list):\n", " return list(set(a) & set(b))" ], "id": "79f190b363fcef7f", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "a = [1, 2, 1, 3, 4, 2]\n", "b = [2, 3, 5]\n", "\n", "print(common_unique_v1(a, b))\n", "print(common_unique_v2(a, b))\n", "print(common_unique_v3(a, b))" ], "id": "94f22bf50028cfa7", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Answer\n", "\n", "Let:\n", "\n", "- `n = len(a)`\n", "- `m = len(b)`\n", "\n", "| Version | Time Complexity | Extra Memory | Notes |\n", "|---|---:|---:|---|\n", "| `v1` | `O(nm + n²)` worst case | `O(n)` | Repeated list membership checks |\n", "| `v2` | `O(n + m)` average | `O(n + m)` | Uses sets for fast membership checks |\n", "| `v3` | `O(n + m)` average | `O(n + m)` | Shortest solution using set intersection |\n", "\n", "`v2` and `v3` are asymptotically better than `v1`.\n", "\n", "If order does not matter, `v3` is usually the cleanest solution." ], "id": "e0b294bee76b54a8" }, { "metadata": {}, "cell_type": "code", "source": [ "ages = {\n", " \"Alice\": 20,\n", " \"Bob\": 25,\n", " \"Charlie\": 30\n", "}\n", "\n", "print(ages[\"Bob\"]) # O(1) average - lookup by key\n", "\n", "ages[\"David\"] = 22 # O(1) average - insert\n", "\n", "ages[\"Alice\"] = 21 # O(1) average - update\n", "\n", "print(\"Charlie\" in ages) # O(1) average - key membership\n", "\n", "print(30 in ages.values()) # O(n) - search through values\n", "\n", "del ages[\"Bob\"] # O(1) average - delete by key\n", "\n", "print(len(ages)) # O(1)" ], "id": "9634e61d205bd95c", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### How dictionary lookup works\n", "\n", "A dictionary is implemented using a **hash table**.\n", "\n", "For a lookup like:\n", "\n", "```python\n", "ages[\"Charlie\"]\n", "```\n", "\n", "Python roughly does:\n", "\n", "1) Compute the hash of the key:\n", "```python\n", "h = hash(\"Charlie\")\n", "```\n", "2) Use the hash to determine where in the table to start looking.\n", "```text\n", "hash(\"Charlie\")\n", " |\n", " v\n", "\n", "+---+---+---+---+---+---+---+---+\n", "| | | | ? | | | | |\n", "+---+---+---+---+---+---+---+---+\n", " ^\n", " |\n", " likely position\n", "```\n", "3) Check the key stored there.\n", "4) If necessary, resolve a collision by checking other positions and comparing keys.\n", "5) Return the corresponding value.\n", "\n", "Therefore:\n", "\n", "```python\n", "key in my_dict # O(1) average\n", "my_dict[key] # O(1) average\n", "```\n", "\n", "This is fundamentally different from a list lookup, which may need to scan elements one by one." ], "id": "c581a568cd788dbb" }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Hashability\n", "\n", "Dictionary keys must be **hashable**.\n", "\n", "Hashable examples:\n", "\n", "- `int`\n", "- `str`\n", "- `tuple` of hashable values\n", "\n", "Non-hashable examples:\n", "\n", "- `list`\n", "- `dict`\n", "- `set`\n", "\n", "This fails:" ], "id": "e163f65c5ce42ada" }, { "metadata": {}, "cell_type": "code", "source": [ "d = {}\n", "d[[1, 2]] = \"value\"" ], "id": "f481cea900ce53e3", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Task: Check whether an order can be fulfilled\n", "\n", "`stock` contains available items and `order` contains requested items.\n", "\n", "Each occurrence matters.\n", "\n", "Example:\n", "\n", "```python\n", "stock = [\"apple\", \"apple\", \"banana\", \"orange\"]\n", "order = [\"apple\", \"apple\", \"banana\"]\n", "# True\n", "```\n", "\n", "What is time and memory complexity of each implementation?" ], "id": "46d36662b5895dc0" }, { "metadata": {}, "cell_type": "code", "source": [ "def can_fulfill_v1(stock: list, order: list):\n", " used = [False] * len(stock)\n", "\n", " for requested_item in order:\n", " found = False\n", "\n", " for i, available_item in enumerate(stock):\n", " if not used[i] and requested_item == available_item:\n", " used[i] = True\n", " found = True\n", " break\n", "\n", " if not found:\n", " return False\n", "\n", " return True\n", "\n", "\n", "def can_fulfill_v1_pythonic(stock: list, order: list):\n", " used = [False] * len(stock)\n", "\n", " for requested_item in order:\n", " for i, available_item in enumerate(stock):\n", " if not used[i] and requested_item == available_item:\n", " used[i] = True\n", " break\n", " else:\n", " return False\n", "\n", " return True" ], "id": "3ab68e043ad2b742", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "def can_fulfill_v2(stock: list, order: list):\n", " counts = {}\n", "\n", " for item in stock:\n", " counts[item] = counts.get(item, 0) + 1\n", "\n", " for item in order:\n", " if counts.get(item, 0) == 0:\n", " return False\n", "\n", " counts[item] -= 1\n", "\n", " return True" ], "id": "4b35b3222bee94c0", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "from collections import Counter\n", "\n", "\n", "def can_fulfill_v3(stock: list, order: list):\n", " available = Counter(stock)\n", " required = Counter(order)\n", "\n", " return required <= available" ], "id": "4715f637568eadeb", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "stock = [\"apple\", \"apple\", \"banana\", \"orange\", \"banana\"]\n", "order = [\"apple\", \"apple\", \"banana\", \"orange\"]\n", "\n", "print(can_fulfill_v1(stock, order))\n", "print(can_fulfill_v1_pythonic(stock, order))\n", "print(can_fulfill_v2(stock, order))\n", "print(can_fulfill_v3(stock, order))" ], "id": "be7e7203d749ddb2", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Answer\n", "\n", "Let:\n", "\n", "- `n = len(stock)`\n", "- `m = len(order)`\n", "\n", "| Version | Time Complexity | Extra Memory | Notes |\n", "|---|---:|---:|---|\n", "| `v1` | `O(nm)` worst case | `O(n)` | Repeatedly scans `stock` |\n", "| `v2` | `O(n + m)` average | `O(k)` | Uses a dictionary of frequencies |\n", "| `v3` | `O(n + m)` average | `O(k)` | Same idea using `Counter` |\n", "\n", "Here, `k` is the number of distinct items.\n", "\n", "`v2` and `v3` are asymptotically better. `v3` is the most concise, while `v2` makes the underlying dictionary logic explicit." ], "id": "f54d2e1b88ca52af" }, { "metadata": {}, "cell_type": "code", "source": [ "from collections import Counter\n", "\n", "items = [\"apple\", \"banana\", \"apple\", \"orange\", \"banana\", \"apple\"]\n", "\n", "counts = Counter(items)\n", "\n", "print(counts)\n", "# Counter({'apple': 3, 'banana': 2, 'orange': 1})\n", "\n", "print(counts[\"apple\"]) # 3 - frequency of an item\n", "print(counts[\"pear\"]) # 0 - missing keys return 0\n", "\n", "counts[\"banana\"] += 1 # update count\n", "print(counts)\n", "\n", "print(counts.most_common(2))\n", "# [('apple', 3), ('banana', 3)]\n", "\n", "required = Counter([\"apple\", \"apple\", \"banana\"])\n", "available = Counter([\"apple\", \"apple\", \"apple\", \"banana\", \"orange\"])\n", "\n", "print(required <= available) # True - all required counts are available\n", "\n", "print(required - available)\n", "# Counter() - nothing is missing\n", "\n", "print(Counter([\"apple\", \"apple\", \"banana\"]) - Counter([\"orange\"]))" ], "id": "f461a76866fa184e", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "### Collection: DEQUE", "id": "1d90a78813668b56" }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Task\n", "For each new value, compute the average of the last at most `k` values.\n", "\n", "```python\n", "values = [10, 20, 30, 40, 50]\n", "k = 3\n", "# -> [10, 15, 20, 30, 40]\n", "```" ], "id": "43058b50b96a61f5" }, { "metadata": {}, "cell_type": "code", "source": [ "def moving_average_v1(values: list, k: int):\n", " result = []\n", "\n", " for i in range(len(values)):\n", " start = max(0, i - k + 1)\n", " window = values[start:i + 1]\n", " result.append(sum(window) / len(window))\n", "\n", " return result" ], "id": "f2b4c22223921f00", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "from collections import deque\n", "\n", "\n", "def moving_average_v2(values: list, k: int):\n", " window = deque()\n", " window_sum = 0\n", " result = []\n", "\n", " for x in values:\n", " window.append(x)\n", " window_sum += x\n", "\n", " if len(window) > k:\n", " window_sum -= window.popleft()\n", "\n", " result.append(window_sum / len(window))\n", "\n", " return result" ], "id": "1e299aa63f978b74", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "from queue import Queue\n", "\n", "\n", "def moving_average_v3(values: list, k: int):\n", " window = Queue()\n", " window_sum = 0\n", " result = []\n", "\n", " for x in values:\n", " window.put(x)\n", " window_sum += x\n", "\n", " if window.qsize() > k:\n", " window_sum -= window.get()\n", "\n", " result.append(window_sum / window.qsize())\n", "\n", " return result" ], "id": "85b75634c12905f9", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "values = [10, 20, 30, 40, 50]\n", "k = 3\n", "\n", "print(moving_average_v1(values, k))\n", "print(moving_average_v2(values, k))\n", "print(moving_average_v3(values, k))" ], "id": "db5b235df311642c", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "#### Complexity\n", "\n", "Let `n = len(values)`.\n", "\n", "| Version | Time | Extra Memory |\n", "|---|---:|---:|\n", "| `v1` — slicing + `sum` | `O(nk)` | `O(n + k)` |\n", "| `v2` — `deque` | `O(n)` | `O(n + k)` |\n", "| `v3` — `Queue` | `O(n)` | `O(n + k)` |\n", "\n", "The `O(n)` part of memory is the returned result.\n", "If we exclude the output, `v2` and `v3` use only `O(k)` extra memory." ], "id": "220cc7f2a8b2d4d3" }, { "metadata": {}, "cell_type": "markdown", "source": "### Comprehensions", "id": "ca57445e1be9afa6" }, { "metadata": {}, "cell_type": "markdown", "source": [ "Comprehensions in Python provide a short and clear way to create new sequences from existing iterables (including collections).\n", "\n", "- Improve readability by replacing long loops with a single statement.\n", "- Encourage modular and clean coding practices.\n", "- Commonly used in data processing, web development, and automation tasks." ], "id": "f00a254b3291518d" }, { "metadata": {}, "cell_type": "markdown", "source": [ "- List comprehension:\n", "```python\n", "[x for x in iterable]\n", "```\n", "- Dict comprehension:\n", "```python\n", "{k: x for k, x in iterable}\n", "```\n", "- Set comprehension:\n", "```python\n", "{x for x in iterable}\n", "```" ], "id": "6e4211ea490872a0" }, { "metadata": {}, "cell_type": "markdown", "source": "Let's rewrite previous examples using comprehensions.", "id": "dbf66014fc7f59b6" }, { "metadata": {}, "cell_type": "code", "source": [ "# 1. Remove all zeros\n", "\n", "def remove_all_zeros_comprehension(numbers: list[int]):\n", " return [x for x in numbers if x != 0]\n", "\n", "\n", "data = [1, 0, 2, 0, 3, 0, 4]\n", "\n", "expected = remove_all_zeros_v3(data)\n", "\n", "result = remove_all_zeros_comprehension(data)\n", "\n", "print(result)\n", "print(result == expected) # True" ], "id": "27e55239251871cb", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# 2. Common unique elements\n", "\n", "def common_unique_comprehension(a: list, b: list):\n", " b_set = set(b)\n", " return {x for x in a if x in b_set}\n", "\n", "\n", "a = [1, 2, 1, 3, 4, 2]\n", "b = [2, 3, 5]\n", "\n", "expected = set(common_unique_v3(a, b))\n", "\n", "result = common_unique_comprehension(a, b)\n", "\n", "print(result)\n", "print(result == expected) # True" ], "id": "31ccd691820c5ba4", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# 3. EXTRA: Dict comprehension\n", "\n", "names = [\"Alice\", \"Bob\", \"Charlie\"]\n", "\n", "lengths_loop = {}\n", "for name in names:\n", " lengths_loop[name] = len(name)\n", "\n", "lengths_comprehension = {\n", " name: len(name)\n", " for name in names\n", "}\n", "\n", "print(lengths_comprehension)\n", "print(lengths_comprehension == lengths_loop) # True" ], "id": "f98ff48714edc96a", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "Are comprehensions just syntax sugar?", "id": "f4a3ae7f79471c98" }, { "metadata": {}, "cell_type": "code", "source": [ "squares = [x**2 for x in range(10)]\n", "print(x)" ], "id": "d0d643c6016f1d50", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "for x in range(3):\n", " print(x)\n", "\n", "print(x) # x is available outside the loop scope" ], "id": "500fbd90420a0640", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "Comprehensions have their own scope. More on scopes later", "id": "b8af6830a70e8d21" }, { "metadata": {}, "cell_type": "markdown", "source": [ "Advice: Use Pythonic syntax and built-ins to write cleaner and more readable code.\n", "\n", "Check out [Clean Code Game](https://cleanpygame.web.app/) to practice it." ], "id": "302d8e7d432561e7" }, { "metadata": {}, "cell_type": "markdown", "source": "## Immutability\n", "id": "433a28929ddbd7f3" }, { "metadata": {}, "cell_type": "code", "source": [ "# Q: What the result is?\n", "print([1, 2] + [3, 4])\n", "print([2, 3] * 4)" ], "id": "5f4fb505711e69", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# guess the result\n", "a = [[1], [1], [1]]\n", "print(a)\n", "\n", "a[0][0] = 2\n", "print(a) # [[2], [1], [1]] (?)" ], "id": "ddc7e88a5405ff7e", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "a = [[1]]\n", "a = a * 3\n", "print(a)\n", "\n", "a[0][0] = 2\n", "print(a) # [[2], [1], [1]] (?)\n" ], "id": "4c8dfeed7a5ea1a4", "outputs": [], "execution_count": null }, { "cell_type": "code", "metadata": {}, "source": [ "# After multiplication, the content of the list is repeated (not copied), so all elements point to the same object\n", "\n", "id(a[0]) == id(a[1]) == id(a[2]), a[0]" ], "id": "12a4d3d5b2021075", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# Tuples are immutable. you can't change tuple\n", "my_tuple = (1, 2, 3)\n", "my_tuple[0] = 100" ], "id": "b44ca23666a869ac", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": [ "tuples are immutable\n", "\n", "why would we want something to be immutable?" ], "id": "1fbc6f1ea1af1f6d" }, { "metadata": {}, "cell_type": "markdown", "source": [ "
\n", "Why Mutable and Immutable\n", "\n", "| Need mutability ➜ “edit-in-place” | Need immutability ➜ “share-safely” |\n", "| --------------------------------- | ---------------------------------- |\n", "| **Performance / memory** – updating a large list in-place avoids copying the whole thing. | **Hashability** – only immutable objects can be stable `dict` keys / `set` members. |\n", "| **Algorithms** – many in-place ops (`list.sort`, graph traversals, caches) are O(1) extra space. | **Safety & correctness** – value can’t “change under your feet,” so shared references are harmless. |\n", "| **Interactivity** – building a UI model, accumulating results, buffering I/O. | **Identity-free equality** – two `7`s or `\"foo\"`s are interchangeable; easy to reason about. |\n", "| **Flexibility** – you can mutate, slice, or replace parts without reallocating the container. | **Thread/concurrency friendliness** – no locks needed when data can’t change. |\n", "\n", "
" ], "id": "662ba428f015157b" }, { "metadata": {}, "cell_type": "code", "source": [ "# IMMUTABLE advantage: safe dictionary key\n", "point = (3, 4) # tuple is immutable\n", "dist_cache = {point: 5.0} # fine ✓\n", "point = (5, 6)\n", "dist_cache # if key would change, our invariant would break" ], "id": "65ef3225a327a0ca", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# MUTABLE pitfall: shared state surprise\n", "a = [1, 2]\n", "b = a\n", "b.append(3)\n", "print(a) # [1, 2, 3] ← changed via alias!" ], "id": "fcadc366f833856", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# MUTABLE pitfall: shared state surprise\n", "def foo(bad_default_value=[]):\n", " bad_default_value.append(1)\n", " return bad_default_value\n", "\n", "print(foo())\n", "print(foo())" ], "id": "c9035d5a83a0f8d0", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "\n", "# MUTABLE pitfall: shared state surprise\n", "def foo(good_default_value=None):\n", " good_default_value = good_default_value or [] # note: google how this syntax work; in short: if value is None return default_value else return value\n", " good_default_value.append(1)\n", " return good_default_value\n", "\n", "print(foo())\n", "print(foo())" ], "id": "a5f24b002663aa1a", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": "### Shallow vs Deep copy", "id": "aa347edc6c1e20ff" }, { "metadata": {}, "cell_type": "code", "source": [ "from copy import deepcopy, copy\n", "\n", "initial_list = [1, [1, 2], {\"a\": 1}]\n", "\n", "alias_list = initial_list\n", "shallow_copy_list = copy(initial_list)\n", "deep_copy_list = deepcopy(initial_list)\n", "\n", "initial_list[0] = 100\n", "initial_list[1][0] = 100\n", "initial_list[2][\"a\"] = 100\n", "\n", "print(initial_list)\n", "print(alias_list)\n", "print(shallow_copy_list)\n", "print(deep_copy_list)" ], "id": "d3afd5c3244b1ac5", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "print(f\"{initial_list is alias_list=}\")\n", "print(f\"{initial_list is shallow_copy_list=}\")\n", "print(f\"{initial_list is deep_copy_list=}\")\n", "\n", "print(f\"{initial_list[1] is alias_list[1]=}\")\n", "print(f\"{initial_list[1] is shallow_copy_list[1]=}\")\n", "print(f\"{initial_list[1] is deep_copy_list[1]=}\")" ], "id": "67f19f944d27b4fa", "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": "## Functions", "id": "41abdd942cebb4b0" }, { "metadata": {}, "cell_type": "markdown", "source": "What do you think about this order processing function?", "id": "b4bde3e68ce93111" }, { "metadata": {}, "cell_type": "code", "source": [ "def process_order(cart, customer_name, is_premium = False):\n", " total = 0\n", "\n", " print(\"PYTHON SHOP\")\n", " print(f\"Customer: {customer_name}\")\n", "\n", " for name, price, quantity in cart:\n", " total += price * quantity\n", " print(f\"{name}: {quantity} x ${price}\")\n", "\n", " if is_premium:\n", " total *= 0.9\n", "\n", " total *= 1.19\n", " print(f\"Total: ${total:.2f}\")\n", "\n", " print(f\"Charging {customer_name}: ${total:.2f}\")\n", " print(\"Making external payment operation ...\")\n", " print(\"Payment successful\")" ], "id": "aae7efe22b25e4c3", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# Better example\n", "\n", "def process_order(cart, customer_name, is_premium = False):\n", " total = calculate_total(cart, is_premium)\n", " print_receipt(cart, customer_name, total)\n", " charge_customer(customer_name, total)\n", "\n", "def calculate_total(cart, is_premium):\n", " total = sum(price * quantity for _, price, quantity in cart)\n", "\n", " if is_premium:\n", " total *= 0.9\n", "\n", " return total * 1.19\n", "\n", "\n", "def print_receipt(cart, customer_name, total):\n", " print(\"PYTHON SHOP\")\n", " print(f\"Customer: {customer_name}\")\n", "\n", " for name, price, quantity in cart:\n", " print(f\"{name}: {quantity} x ${price}\")\n", "\n", " print(f\"Total: ${total:.2f}\")\n", "\n", "def charge_customer (customer_name, total):\n", " print(f\"Charging {customer_name}: ${total:.2f}\")\n", " print(\"Making external payment operation ...\")\n", " print(\"Payment successful\")" ], "id": "5852602d98578ab", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "Here you can see the single responsibility principle in action.\n", "\n", "Functions are useful to reuse behavior and split responsibilities." ], "id": "9f83765c12b291a0" }, { "metadata": {}, "cell_type": "markdown", "source": "**See any other problems ...?**", "id": "bc1d1e0a00d5febc" }, { "metadata": {}, "cell_type": "markdown", "source": [ "What is \"process\"?\n", "\n", "Total what?" ], "id": "807deddcb0205436" }, { "metadata": {}, "cell_type": "code", "source": [ "def complete_payment(cart, customer_name, is_premium=False):\n", " order_total_cost = calculate_total(cart, is_premium)\n", " print_receipt(cart, customer_name, order_total_cost)\n", " charge_customer(customer_name, order_total_cost)" ], "id": "1fb2fb8cfcf6c2ca", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "AI may generate code with poor naming. Try to make the code self-explanatory.\n", "\n", "Check out [Clean Code Game](https://cleanpygame.web.app/) to practice.\n" ], "id": "8fe2b1a6e41594fc" }, { "metadata": {}, "cell_type": "markdown", "source": [ "Functions are first-class objects: they can be assigned to variables, passed as arguments, and returned from functions.\n", "\n", "For example this allow us to create factory functions.\n", "\n", "A factory function can create and return functions with customized behavior." ], "id": "8c87eab19a27934" }, { "metadata": {}, "cell_type": "code", "source": [ "from random import uniform\n", "from math import log, cos, pi\n", "\n", "def normal_distribution_sampler_factory(mu, sigma):\n", "\n", " def normal_distribution_sampler(size):\n", " R_array = [(-2 * log(uniform(0, 1))) ** 0.5 for i in range(size)]\n", " theta_array = [2 * pi * uniform(0, 1) for i in range(size)]\n", " return [sigma * R * cos(theta) + mu for R, theta in zip(R_array, theta_array)]\n", "\n", " return normal_distribution_sampler\n" ], "id": "d54e48aa0e1d3183", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "import matplotlib.pyplot as plt\n", "\n", "sampler_1 = normal_distribution_sampler_factory(mu=0, sigma=10)\n", "sampler_2 = normal_distribution_sampler_factory(mu=3, sigma=3)\n", "\n", "plt.hist(sampler_1(10_000), bins=50, alpha=0.6, color=\"blue\", label=\"μ=0, σ=10\")\n", "plt.hist(sampler_2(10_000), bins=50, alpha=0.6, color=\"red\", label=\"μ=3, σ=3\")\n", "plt.legend()\n", "plt.show()" ], "id": "bdd969e2526f855c", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "As in many other languages, functions can be recursive.", "id": "e7a50d828c0f441" }, { "metadata": {}, "cell_type": "code", "source": [ "# Recursion is useful when the data itself is recursive.\n", "# Example: computing the total size of a nested structure.\n", "\n", "data = [\n", " 1,\n", " [2, 3],\n", " [4, [5, 6]]\n", "]\n", "\n", "\n", "def recursive_sum(value):\n", " if isinstance(value, list):\n", " return sum(recursive_sum(x) for x in value)\n", "\n", " return value\n", "\n", "\n", "print(recursive_sum(data))" ], "id": "bc49bc1b7f3d1029", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "### Args and kwargs", "id": "cb8c8805167f84b2" }, { "metadata": {}, "cell_type": "code", "source": [ "# Positional and keyword arguments.\n", "\n", "def greet(name, greeting=\"Hello\"):\n", " return f\"{greeting}, {name}!\"\n", "\n", "\n", "print(greet(\"Alice\"))\n", "print(greet(\"Alice\", \"Hi\"))\n", "print(greet(name=\"Alice\", greeting=\"Welcome\"))" ], "id": "454ae9fd8b6d400a", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# *args collects extra positional arguments into a tuple.\n", "\n", "def total(*args):\n", " return sum(args)\n", "\n", "\n", "print(total(1, 2, 3, 4))" ], "id": "942bdbdbfecb1678", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# **kwargs collects extra keyword arguments into a dictionary.\n", "\n", "def print_user(**kwargs):\n", " for key, value in kwargs.items():\n", " print(key, \"=\", value)\n", "\n", "\n", "print_user(name=\"Alice\", age=20, city=\"Bremen\")" ], "id": "ca0c04300b524d0", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# Arguments can be unpacked with * and **.\n", "\n", "values = [3, 7]\n", "\n", "def add(a, b):\n", " return a + b\n", "\n", "\n", "print(add(*values))\n", "\n", "options = {\"name\": \"Bob\", \"greeting\": \"Hi\"}\n", "print(greet(**options))" ], "id": "4c6825eedb085d8a", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": "## Scopes", "id": "8d4b63e829fbbb87" }, { "metadata": {}, "cell_type": "code", "source": [ "# Scope: variables created inside a function are local.\n", "\n", "x = 10\n", "\n", "def example():\n", " x = 20\n", " print(\"inside:\", x)\n", "\n", "\n", "example()\n", "print(\"outside:\", x)" ], "id": "a7aa3b59eee77551", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# Functions can read variables from an enclosing scope.\n", "\n", "def make_multiplier(factor):\n", " def multiply(x):\n", " return x * factor\n", " return multiply\n", "\n", "\n", "double = make_multiplier(2)\n", "triple = make_multiplier(3)\n", "\n", "print(double(10))\n", "print(triple(10))" ], "id": "32a29f3226175d2a", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "code", "source": [ "# nonlocal modifies a variable in the nearest enclosing function scope.\n", "\n", "def make_counter():\n", " count = 0\n", "\n", " def increment():\n", " nonlocal count\n", " count += 1\n", " return count\n", "\n", " return increment\n", "\n", "\n", "counter = make_counter()\n", "\n", "print(counter())\n", "print(counter())\n", "print(counter())" ], "id": "aac2711feac5c1a6", "outputs": [], "execution_count": null }, { "metadata": {}, "cell_type": "markdown", "source": [ "Remember to practice!\n", "\n", "Python Gym: https://gym.andgein.ru/\n", "\n", "Introduction to Python in-IDE course: https://academy.jetbrains.com/course/16630\n", "\n", "Clean Code Game: https://cleanpygame.web.app/" ], "id": "97728848103e0f93" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }