08-linked-structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "# Linked Structures\n",
    "\n",
    "## Agenda\n",
    "\n",
    "1. Motivation\n",
    "2. Wishlist\n",
    "3. Mechanisms\n",
    "4. Linked Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "## 1. Motivation: built-in, array-backed list runtimes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "What are the runtime complexities of some common operations for updating an array-backed list?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from timeit import timeit\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### Index-based update"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "size = 10_000\n",
    "\n",
    "ts = [timeit('lst[{}] = None'.format(n),\n",
    "             setup=f'lst = list(range({size}))',\n",
    "             number=100)\n",
    "      for n in range(0, size, 10)]\n",
    "\n",
    "plt.plot(ts, 'ro');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### Appending"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "ns = np.linspace(100, 10000, 50, dtype=int)\n",
    "\n",
    "ts = [timeit('lst.append(None)',\n",
    "             setup=f'lst = list(range({n}))',\n",
    "             number=1000)\n",
    "      for n in ns]\n",
    "\n",
    "plt.plot(ns, ts, 'ro');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### Insertion & Deletion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "ns = np.linspace(100, 10000, 50, dtype=int)\n",
    "\n",
    "# timing insertion at front\n",
    "ins_ts = [timeit('lst.insert(0, None)',\n",
    "                 setup=f'lst = list(range({n}))',\n",
    "                 number=100)\n",
    "          for n in ns]\n",
    "\n",
    "# timing deletion at front\n",
    "del_ts = [timeit('del lst[0]',\n",
    "                 setup=f'lst = list(range({n}))',\n",
    "                 number=100)\n",
    "          for n in ns]\n",
    "\n",
    "plt.plot(ns, ins_ts, 'go')\n",
    "plt.plot(ns, del_ts, 'ro');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### Concatenation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "def concat1(lst1, lst2):\n",
    "    for x in lst2:\n",
    "        lst1.append(x)\n",
    "    return lst1\n",
    "\n",
    "def concat2(lst1, lst2):\n",
    "    lst1.extend(lst2)\n",
    "    return lst1\n",
    "\n",
    "def concat3(lst1, lst2):\n",
    "    return lst1 + lst2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "ns = np.linspace(100, 10000, 50, dtype=int)\n",
    "\n",
    "ts = [[timeit('{}(lst1, lst2)'.format(fn),\n",
    "              setup=f'lst1 = list(range({n})); lst2 = list(range({n}))',\n",
    "              number=100,\n",
    "              globals=globals())\n",
    "       for n in ns] \n",
    "      for fn in ('concat1', 'concat2', 'concat3')]\n",
    "\n",
    "plt.plot(ns, ts[0], 'ro')\n",
    "plt.plot(ns, ts[1], 'go')\n",
    "plt.plot(ns, ts[2], 'bo');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### Conclusion\n",
    "\n",
    "While index-based updates and appends are $O(1)$, operations that may require changing the relative positions of elements en masse (e.g., insertion, deletion, concatenation) are $O(N)$. \n",
    "\n",
    "This is due to the **monolithic, contiguous memory allocation** of the array used to hold references to elements in the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "## 2. Wishlist\n",
    "\n",
    "For applications that frequently perform operations such as insertions & deletions (which are inefficient in an array-backed list) we would like to have an improved storage mechanism that:\n",
    "\n",
    "- does **not** require monolithic, contiguous memory allocation,\n",
    "- supports flexible and efficient reorganization of substructures (e.g., for concatenation and relocation),\n",
    "- and allows us to build other commonly needed operations (e.g., for indexing, iteration, search) on top of it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "## 3. Mechanisms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### 3.1. Two-Element Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# data items\n",
    "i1 = 'lions'\n",
    "i2 = 'tigers'\n",
    "i3 = 'bears'\n",
    "i4 = 'oh, my'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# creating individual \"links\"\n",
    "l1 = []\n",
    "l2 = []\n",
    "l3 = []\n",
    "l4 = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# link-ing them together\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# data access\n",
    "head = l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# iteration\n",
    "def link_iterator(l):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "for x in link_iterator(head):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# prepending\n",
    "i0 = 'walruses'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "for x in link_iterator(head):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# insertion\n",
    "i2_5 = 'elephants'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "for x in link_iterator(head):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# deletion\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "for x in link_iterator(head):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### 3.2. \"Link\" objects"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "class Link:\n",
    "    def __init__(self, val, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# manually constructing a list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# data access\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# iteration\n",
    "def link_iterator(l):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "for x in link_iterator(head):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "## 4. Linked Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### 4.1 Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    class Link:\n",
    "        def __init__(self, val, next=None):\n",
    "            self.val = val\n",
    "            self.next = next\n",
    "\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def prepend(self, val):\n",
    "        pass\n",
    "        \n",
    "    def __iter__(self):\n",
    "        pass\n",
    "            \n",
    "    def __repr__(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "l = LinkedList()\n",
    "for x in range(10):\n",
    "    l.prepend(x)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### 4.2 Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "class BinaryLink:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "# an \"expression tree\" representing the arithmetic expression ((5+3)*(8-4))\n",
    "t = BinaryLink('*')\n",
    "t.left = BinaryLink('+')\n",
    "t.left.left  = BinaryLink('5')\n",
    "t.left.right = BinaryLink('3')\n",
    "t.right = BinaryLink('-')\n",
    "t.right.left  = BinaryLink('8')\n",
    "t.right.right = BinaryLink('4')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "def print_expr_tree(t):\n",
    "    if t:\n",
    "        if not t.val.isdigit():\n",
    "            print('(', end='')\n",
    "        print_expr_tree(t.left)\n",
    "        print(t.val, end='')\n",
    "        print_expr_tree(t.right)\n",
    "        if not t.val.isdigit():\n",
    "            print(')', end='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "print_expr_tree(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "state": "normal"
   },
   "source": [
    "### 4.3 N-ary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "class NaryLink:\n",
    "    def __init__(self, val, n=2):\n",
    "        self.val = val\n",
    "        self.children = [None] * n\n",
    "        \n",
    "    def __getitem__(self, idx):\n",
    "        return self.children[idx]\n",
    "    \n",
    "    def __setitem__(self, idx, val):\n",
    "        self.children[idx] = val\n",
    "        \n",
    "    def __iter__(self):\n",
    "        for c in self.children:\n",
    "            yield c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "root = NaryLink('Kingdoms', n=5)\n",
    "\n",
    "root[0] = NaryLink('Animalia', n=35)\n",
    "root[1] = NaryLink('Plantae', n=12)\n",
    "root[2] = NaryLink('Fungi', n=7)\n",
    "root[3] = NaryLink('Protista', n=5)\n",
    "root[4] = NaryLink('Monera', n=5)\n",
    "\n",
    "root[2][0] = NaryLink('Chytridiomycota')\n",
    "root[2][1] = NaryLink('Blastocladiomycota')\n",
    "root[2][2] = NaryLink('Glomeromycota')\n",
    "root[2][3] = NaryLink('Ascomycota')\n",
    "root[2][4] = NaryLink('Basidiomycota')\n",
    "root[2][5] = NaryLink('Microsporidia')\n",
    "root[2][6] = NaryLink('Neocallimastigomycota')\n",
    "\n",
    "def tree_iter(root):\n",
    "    if root:\n",
    "        yield root.val\n",
    "        for c in root:\n",
    "            yield from tree_iter(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "state": "normal"
   },
   "outputs": [],
   "source": [
    "for x in tree_iter(root):\n",
    "    print(x)"
   ]
  }
 ],
 "metadata": {
  "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.9.1"
  },
  "mimir": {
   "data": {},
   "last_submission_id": "",
   "project_id": "bf398baa-c055-424e-bd0f-454e6a8b9944"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}