index.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Матрицы и Python\n",
    "---\n",
    "\n",
    "*fedor1113*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Структуры данных\n",
    "\n",
    "\n",
    "<div style=\"text-align: right !important\">\n",
    "«В рубежах поденной структуры <br>\n",
    "Переполох - <br>\n",
    "Сбой фазы огорошил цепь.»\n",
    "<br>\n",
    "- группа «Алиса», «Пересмотри»\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "В презентации будет рассмотрен в основном *Python 3.7* (конечно, ничего крайне специфичного не будет, поэтому экстраполировать для других версий (в том числе  - *Python 2.x*) не составит труда)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "В математических расчётах мы используем структуры типа $ \\begin{bmatrix}\n",
    "    x_{11}       & x_{12} \\\\\n",
    "    x_{21}       & x_{22}\n",
    "\\end{bmatrix} $. Резонно надеяться найти наиболее похожий на эту структуру объект для её хранения. \n",
    "\n",
    "Обычно в разных языках программирования используется АТД двумерного массива. \n",
    "\n",
    "В Питоне, как известно, вообще вместо классического массива используется структура списка. Поэтому для хранения матриц мы используем… правильно, двумерный список.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Лирическое отступление: конечно, в виде двумерных списков можно представить любую таблицу данных. Также можно создавать и вложенные, многомерные списки."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Матрицы <=> Списки\n",
    "По сути – тут ничего сложного. Это просто список списков.\n",
    "\n",
    "Каждый внутренний список – строка матрицы. Тогда при вызове элемента дважды используем индекс (просто последовательно применяем; тут это является примером *method chaining*, т.к. всё в Питоне – объект, просто используется особый, зарезервированный спец. синтаксис квадратных скобок): `m[j][k]` – вернёт элемент матрицы m<sub>*j,k*</sub>. Здесь j является номером строки (выбираем один из внутр. списков), k – номером столбца (в этом списке выбираем элемент)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## «Talk is cheap. Show me the code.»\n",
    "\n",
    "(Фраза Линуса Торвальдса;\n",
    "\n",
    "лит. пер.: «Хватит дешёвой болтовни. Покажите мне код.»)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Многомерные списки"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Абстракции вложенных списков\n",
    "*это \"list comprehensions\"*\n",
    "\n",
    "Напоминаю синтаксис данного синтаксического сахара. \n",
    "Для двумерного списка: `l1 = [[l for l in r] for r in rs]`.\n",
    "Здесь мы проходимся по всем элементам `r` объекта `rs`, а затем по всем элементам каждого из этих элементов `r`, которые становятся элементами `len(rs)` вложенных списков. Тут нужно заметить, что это был вообще неполезный пример почти в любой ситуации (да, мы получили объект с теми же элементами), однако к каждому добавляемому элементу можно применять функции и проч."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Поэтому для каждого отдельного выражения вложенной абстракции имеем следующий общий синтаксис.\n",
    "\n",
    "В целом есть две ситуации:\n",
    " * Для каждого элемента итерируемого объекта, если выполняется условие, добавляем в список f1() от этого элемента, иначе - f2() от этого элемента:\n",
    " ```python \n",
    "l1 = [f1(e) if cond(e) else f2(e) for e in iterable]\n",
    "```\n",
    " * Для каждого элемента итерируемого объекта, если выполняется условие, добавляем в список f1() от этого элемента, иначе - пропускаем его:\n",
    " ```python\n",
    "l1 = [f1(e) for e in iterable if cond(e)]\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Наглядное «разворачивание» абстракции списков\n",
    "\n",
    "Разобранная выше сокращённая запись  ```l1 = [f1(e) if cond(e) else f2(e) for e in iterable]``` будет эквивалентна следующему коду.\n",
    "\n",
    " ```python \n",
    "l1 = []\n",
    "for e in iterable:\n",
    "    if cond(e):\n",
    "        l1.append(f1(e))\n",
    "    else:\n",
    "        l1.append(f2(e))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### Более сложный пример\n",
    "Списковое включение:\n",
    " ```python \n",
    "dimensions = (7, 6); d = dimensions\n",
    "s = \"111000101000111000100101100010100010000100\"\n",
    "l1 = [[s[r * d[1] + c] for c in range(d[1])] for r in range(d[0])]\n",
    "for r in l1:\n",
    "    print(*r, sep=\"\")\n",
    "```\n",
    "Развёрнутый вариант:\n",
    " ```python \n",
    "dimensions = (7, 6); d = dimensions\n",
    "s = \"111000101000111000100101100010100010000100\"\n",
    "l1 = []\n",
    "[s[r * d[1] + c] for c in range(d[1])] for r in range(d[0])\n",
    "for r in range(d[0]):\n",
    "    l1.append([])\n",
    "    for c in range(d[1]):\n",
    "        l1[r].append(s[r * d[1] + c])\n",
    "for r in l1:\n",
    "    print(*r, sep=\"\")\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "###   \n",
      "# #   \n",
      "###   \n",
      "#  # #\n",
      "#   # \n",
      "#   # \n",
      "   #  \n"
     ]
    }
   ],
   "source": [
    "dimensions = (7, 6); d = dimensions\n",
    "s = \"111000101000111000100101100010100010000100\"\n",
    "l1 = [[\"#\" if s[r * d[1] + c] == \"1\"\n",
    "       else \" \"\n",
    "       for c in range(d[1])] \n",
    "      for r in range(d[0])]\n",
    "for r in l1:\n",
    "    print(*r, sep=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Ввод"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 5\n",
      "1 2 3 4 5\n",
      "6 7 8 9 10\n",
      "11 12 13 14 15\n",
      "16 17 18 19 20\n"
     ]
    }
   ],
   "source": [
    "# Вот так можно ввести матрицу\n",
    "# - используем *list comprehension*\n",
    "# (то, что часто по-русски крайне неудачно\n",
    "# называют \"генераторы списков\")\n",
    "# Лучшим переводом \n",
    "# (хотя подходящим лишь по историческим причинам)\n",
    "# будет \"абстракция списков\"\n",
    "# или   \"списковое включение\"\n",
    "rows, cols = map(int, input().split())\n",
    "matrix = [list(map(int, input().split())) for r in range(rows)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Вывод"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5\n",
      "6 7 8 9 10\n",
      "11 12 13 14 15\n",
      "16 17 18 19 20\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Неформатированный вывод матриц - дело несложное\n",
    "srepr = \"\".join((\" \".join(map(str, r)) + \"\\n\"\n",
    "                         for r in matrix))\n",
    "print(srepr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Кроме строкового метода `join()` полезна в работе с матрицами, конечно, и незаменимая вообще в работе со списками и кортежами их распаковка - через унарный `*`-оператор.\n",
    "\n",
    "Однако нужно помнить: к сожалению (или к счастью - т.к. при добавлении подобной опции появляются проблемы с двусмысленностью/неочевидностью синтаксиса), пока *Python* не поддерживает распаковку итерируемого объекта внутри выражений *list comprehension*. ~~Т.е. `[*l for l in lst]` работать не будет, даже если Вам очень хочется так последовательно распаковывать матрицы.~~"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5\n",
      "6 7 8 9 10\n",
      "11 12 13 14 15\n",
      "16 17 18 19 20\n"
     ]
    }
   ],
   "source": [
    "# Можно реализовать вывод и таким способом:\n",
    "for r in matrix:\n",
    "    print(*r)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Форматирование\n",
    "Для форматированного вывода лучше всего, конечно, использовать одну из опций языка *Python*, специально отведённых для форматирования строк.\n",
    "Метод строк `format()` или форматированную строку `f\"\"`.\n",
    "\n",
    "Второй метод быстрее и удобнее, но появился только в версии *3.6*.\n",
    "\n",
    "Форматирование строк имеет свой особый синтаксис, который имеет смысл изучить. Для работы с числовыми матрицами полезны синтаксические конструкции, позволяющие выводить тип `float` с заданной точностью, выводить строку заданной длины (заполняющие её заданным символом).\n",
    "\n",
    "Последнее очень важно для форматированного вывода таблиц.\n",
    "Для форматируемой переменной нужно в строке задать опцию `>длина`, чтобы строка заполнилась пробелами слева. Т.е. `f\"{variable:>lngth}\"`. Пробел - заполнитель по умолчанию. Вообще можно указать явно: `f\"{variable: >lngth}\"`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "На всякий случай: для вывода чисел с плавающей точкой с заданной точностью используется флаг f. Пример: `f\"{variable:.4f}\"` - выводит с точностью 4 знака после запятой.\n",
    "\n",
    "Также полезной функцией форматирования является вывод в разных системах счисления (поддерживаются двоичная, восьмиричная, десятиричная и шестнадцатиричная). Всё это хорошо описано в документации *Python*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Введение специального класса для матриц"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Развивая тему [*method chaining*](https://en.wikipedia.org/wiki/Method_chaining), хотелось бы отметить, что *Python* позволяет нам использовать (вводить) синтаксис с квадратными скобками (англ. *brackets*) в наших собственных классах через специальные методы (например, метод `__getitem__(self, key) -> obj[key]`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Matrix:\n",
    "    \"\"\"A simple wrapper around a two-dimensional list\"\"\"\n",
    "    \"\"\"Простая обёртка вокруг 2-мерного списка - пример\"\"\"\n",
    "    def __init__(self, lst=[[]]):\n",
    "        self._lst = lst\n",
    "    # ...\n",
    "    def __getitem__(self, index):\n",
    "        return self._lst[index]\n",
    "\n",
    "    def __setitem__(self, index, val):\n",
    "        self._lst[index] = val\n",
    "\n",
    "    def __delitem__(self, index):\n",
    "        del self._lst[index]\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self._lst.__iter__()\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._lst)\n",
    "\n",
    "    def __contains__(self, item):\n",
    "        return item in self._lst\n",
    "\n",
    "    def __add__(self, other):\n",
    "        assert type(other) is Matrix\n",
    "        return Matrix([[e1 + e2 for e1, e2 in zip(r1, r2)]\n",
    "                       for r1, r2 in zip(self._lst, other)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Matrix(Matrix):\n",
    "    def __str__(self):\n",
    "        from functools import partial\n",
    "        def _frmt(el, max_len=0):\n",
    "            # r = f\"{el:>{max_len}}\"  # PEP 498 -- Literal String Interpolation\n",
    "            # с Python 3.6\n",
    "            r = \"{:>{}}\".format(el, max_len)  # Медленнее, сложнее\n",
    "            \n",
    "            return r\n",
    "        \n",
    "        srepr = \"\"\n",
    "        max_len = 0\n",
    "        max_len = max((len(str(elem))\n",
    "                       for row in self._lst\n",
    "                       for elem in row),\n",
    "                      default=0)\n",
    "        _frmt = partial(_frmt, max_len=max_len)\n",
    "            \n",
    "        for row in self._lst:\n",
    "            srepr += \" \".join(map(_frmt, map(str, row))) + \"\\n\"\n",
    "        \n",
    "        return srepr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11 12 13 14\n",
      "21 22 23 24\n",
      "31 32 33 34\n",
      "41 42 43 44\n",
      "\n",
      "1 1 1 1\n",
      "2 2 2 2\n",
      "3 3 3 3\n",
      "4 4 4 4\n",
      "\n",
      "11\n",
      "12 13 14 15\n",
      "23 24 25 26\n",
      "34 35 36 37\n",
      "45 46 47 48\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Протестируем\n",
    "m1 = Matrix([[11, 12, 13, 14], [21, 22, 23, 24],\n",
    "                [31, 32, 33, 34], [41, 42, 43, 44]])\n",
    "\n",
    "m2 = Matrix([[1, 1, 1, 1], [2, 2, 2, 2],\n",
    "                [3, 3, 3, 3], [4, 4, 4, 4]])\n",
    "\n",
    "print(m1)\n",
    "print(m2)\n",
    "print(m1[0][0])\n",
    "print(m1 + m2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Комментарии\n",
    "\n",
    "Мы можем таким образом легко расширять встроенный функционал списков. Как видно из примера выше. Можно добавить любые необходимые операции с матрицами.\n",
    "\n",
    "Мы, конечно, могли бы сделать матрицу подклассом списка, но для наглядности переписали всё сами."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Умножение матриц в Python\n",
    "\n",
    "У работы с матрицами в *Python*-е есть одна очень интересная и малоизвестная особенность. В *Python*-е есть встроенный оператор, отведённый под перемножение двух матриц. Оператор `@`.\n",
    "\n",
    "Появился он с [**PEP 465**](https://www.python.org/dev/peps/pep-0465/). Замечу: это **Python 3.5+**.\n",
    "\n",
    "Оператор есть; имплементация отсутствует (опять-таки - обычная философия *Python* «batteries included» здесь работает, правда, не на 100%))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Тем не менее, с этим оператором мы можем очень легко расширить наш класс `Matrix`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Matrix_extended(Matrix):\n",
    "    def __init__(self, lst=[[]]):\n",
    "        super().__init__(lst)\n",
    "        self.update_order()\n",
    "        \n",
    "    def update_order(self):\n",
    "        self.order = (len(self._lst), len(self._lst[0]))\n",
    "        # количество строк, количество столбцов\n",
    "    \n",
    "    def __delitem__(self, index):\n",
    "        super().__delitem__(index)\n",
    "        self.update_order()\n",
    "    \n",
    "    def __len__(self):\n",
    "        # return len([r for r in self._lst])\n",
    "        # Пожалуй, больше подходит для матриц\n",
    "        return self.order[0] * self.order[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Matrix_extended(Matrix_extended):\n",
    "    def __matmul__(self, multiplier):\n",
    "        if self.order[1] != multiplier.order[0]:\n",
    "            raise ArithmeticError(\"Матрицы не согласованы.\")\n",
    "        \n",
    "        return Matrix([[sum(a*b for a, b in zip(srow, mcol))\n",
    "                 for mcol in zip(*multiplier._lst)]\n",
    "                for srow in self._lst])\n",
    "\n",
    "    def __rmatmul__(self, multiplicand):\n",
    "        if multiplicand.order[1] != self.order[0]:\n",
    "            raise ArithmeticError(\"Матрицы не согласованы.\")\n",
    "        \n",
    "        return Matrix([[sum(a*b for a, b in zip(mrow, scol))\n",
    "                 for scol in zip(*self._lst)]\n",
    "                for mrow in multiplicand._lst])\n",
    "    \n",
    "    def __imatmul__(self, multiplier):\n",
    "        \"\"\"Для a @= b\"\"\"\n",
    "        self._lst = self @ multiplier\n",
    "        return Matrix(self._lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11 12 13 14\n",
      "21 22 23 24\n",
      "31 32 33 34\n",
      "41 42 43 44\n",
      "\n",
      "1 1 1 1\n",
      "2 2 2 2\n",
      "3 3 3 3\n",
      "4 4 4 4\n",
      "\n",
      "130 130 130 130\n",
      "230 230 230 230\n",
      "330 330 330 330\n",
      "430 430 430 430\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Протестируем умножение:\n",
    "\n",
    "m1 = Matrix_extended([[11, 12, 13, 14], [21, 22, 23, 24],\n",
    "                [31, 32, 33, 34], [41, 42, 43, 44]])\n",
    "    \n",
    "m2 = Matrix_extended([[1, 1, 1, 1], [2, 2, 2, 2],\n",
    "             [3, 3, 3, 3], [4, 4, 4, 4]])\n",
    "\n",
    "print(m1)\n",
    "print(m2)\n",
    "\n",
    "print(m1 @ m2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Заключение\n",
    "---\n",
    "\n",
    "С этой информацией, думаю, программист уже имеет представление о многих элементарных функциях Питона, полезных в работе с матрицами; можно закончить этот небольшой *tutorial*.\n",
    "\n",
    "В заключение, для быстрой, профессиональной работы с матрицами лучше использовать специальные модули (а не встроенные средства языка) - [***numpy***](http://www.numpy.org/) со встроенными массивами, которые поддерживают умножение на скаляр и тому подобные операции, - одно из самых популярных решений. Кстати, как ни странно, в *numpy* часто для матриц удобнее использовать именно вложенные массивы, а не встроенный класс матриц, т.к. они поддерживают больше операций."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Полезные ресурсы\n",
    " * [Python Docs: 5.1.4. Nested List Comprehensions](https://docs.python.org/3.7/tutorial/datastructures.html#nested-list-comprehensions)\n",
    " * Русский перевод (там 5.1.3): https://pythoner.name/documentation/tutorial/structures (прим.: не переводите *list comprehensions* - генераторы; это не генераторы, генераторы - отдельный тип объекта!)\n",
    " * [Python Docs: `string` - Format Specification Mini-Language](https://docs.python.org/3.7/library/string.html#formatspec)\n",
    " * [Питонтьютор: Занятие 9. Двумерные массивы](https://pythontutor.ru/lessons/2d_arrays/) - тут можно потренироваться работать с двумерными списками"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# >>> ..."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}