Chapter5_Common_DS_Python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "forced-relay",
   "metadata": {},
   "source": [
    "# Chapter 5 - Common Data Structures in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "behind-caribbean",
   "metadata": {},
   "source": [
    "### References \n",
    "\n",
    "Time Complexity: https://wiki.python.org/moin/TimeComplexity\n",
    "___\n",
    "## 5.1 Dictionaries, Maps and hashtables\n",
    "\n",
    "Dictionaries are often called maps, hashmaps, lookup tables or associative arrays. They provide performance characteristics that you would expect such as: \n",
    "\n",
    "* O(1) time complexity for lookup, insert, update, and\n",
    "delete operations in the average case\n",
    "\n",
    "### Summary \n",
    "\n",
    "* Dictionaries are the central data structure in Python.\n",
    "* The built-in ```dict``` type will be “good enough” most of the time.\n",
    "* Specialized implementations, like read-only or ordered dicts,\n",
    "are available in the Python standard library."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "facial-mathematics",
   "metadata": {},
   "source": [
    "### ```dict``` the in-built dictionary\n",
    "\n",
    "There are some restrictions on which objects can be used as valid keys. Immutable types like strings and numbers are hashable and work well as keys. You can also use ```tuple``` objects as keys, as long as they contain only hashable types themselves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "material-conservation",
   "metadata": {},
   "outputs": [],
   "source": [
    "phonebook = {\n",
    "    'bob': 7387,\n",
    "    'alice': 3719,\n",
    "    'jack': 7052,\n",
    "}\n",
    "\n",
    "squares = {x: x * x for x in range(6)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "czech-latest",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3719"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phonebook['alice']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "timely-chester",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "squares"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dramatic-appraisal",
   "metadata": {},
   "source": [
    "### ```collections.OrderedDict``` - Remember the insertion of keys\n",
    "\n",
    "Python includes a specialized dict subclass that remembers the insertion order of keys added to it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "smart-tradition",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "d = collections.OrderedDict(one=1, two=2, three=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "elementary-wings",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "OrderedDict([('one', 1), ('two', 2), ('three', 3)])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "consolidated-mileage",
   "metadata": {},
   "outputs": [],
   "source": [
    "d['four'] = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "decent-moisture",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "odict_keys(['one', 'two', 'three', 'four'])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "interior-beauty",
   "metadata": {},
   "source": [
    "### ```collections.defaultdict``` – Return Default Values for Missing Keys\n",
    "\n",
    "The ```defaultdict``` class is another dictionary subclass that accepts a callable in its constructor whose return value will be used if a requested key cannot be found."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ceramic-merchant",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Rufus', 'Kathrin', 'Mr Sniffles']"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "dd = defaultdict(list)\n",
    "\n",
    "# Accessing a missing key creates it and\n",
    "# initializes it using the default factory,\n",
    "dd['dogs'].append('Rufus')\n",
    "dd['dogs'].append('Kathrin')\n",
    "dd['dogs'].append('Mr Sniffles')\n",
    "dd['dogs']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "composed-enforcement",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dd['cats']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "earned-diagram",
   "metadata": {},
   "source": [
    "### ```collections.Chainmap``` - search multiple dictionaries as a single mapping\n",
    "\n",
    "This data structure groups multiple dictionaries into a single mapping. Lookups search the underlying mappings\n",
    "one by one until a key is found. Insertions, updates, and deletions\n",
    "only affect the first mapping added to the chain."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "signed-pension",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import ChainMap\n",
    "dict1 = {'one': 1, 'two': 2}\n",
    "dict2 = {'three': 3, 'four': 4}\n",
    "chain = ChainMap(dict1, dict2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "floral-light",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "wound-spyware",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chain['three']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "rolled-miniature",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chain['one']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "ignored-mobility",
   "metadata": {},
   "outputs": [],
   "source": [
    "chain['five'] = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "adaptive-charge",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ChainMap({'one': 1, 'two': 2, 'five': 5}, {'three': 3, 'four': 4})"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# as expected only the first mapping allows insertions \n",
    "chain"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "personalized-broadcast",
   "metadata": {},
   "source": [
    "### ```types.MappingProxyType``` - A Wrapper for making read-only dictionaries\n",
    "\n",
    "```MappingProxyType``` is a wrapper around a standard dictionary that provides a read-only view into the wrapped dictionary's data.\n",
    "\n",
    "For example, this can be helpful if you'd like to return a dictionary carrying internal state from a class or module, while discouraging write access to this object. Using ```MappingProxyType``` allows you to put these restrictions in place without having to create a full copy of the dictionary. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "bridal-disposal",
   "metadata": {},
   "outputs": [],
   "source": [
    "from types import MappingProxyType\n",
    "\n",
    "writable = {'one' : 1, 'two' : 2}\n",
    "read_only = MappingProxyType(writable)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "tight-friendship",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "read_only['one']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "mineral-myrtle",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'mappingproxy' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-19-8d269ba54945>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mread_only\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m'one'\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m23\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'mappingproxy' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "read_only['one'] = 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "local-station",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mappingproxy({'one': 42, 'two': 2})"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# updates to the original are reflected in the proxy\n",
    "writable['one'] = 42\n",
    "read_only"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "advised-numbers",
   "metadata": {},
   "source": [
    "___\n",
    "## 5.2 Array Data Structures\n",
    "\n",
    "Arrays consist of fixed-size data records that allow each element to be\n",
    "efficiently located based on its index.\n",
    "Because arrays store information in adjoining blocks of memory,\n",
    "they’re considered **contiguous data structures**. \n",
    "\n",
    "### Summary \n",
    "\n",
    "* **You need to store arbitrary objects, potentially with mixed\n",
    "data types?** Use a list or a tuple, depending on whether you want\n",
    "an immutable data structure or not.\n",
    "\n",
    "* **You have numeric (integer or floating point) data and tight\n",
    "packing and performance is important?** Try out ```array.array```\n",
    "and see if it does everything you need. Also, consider going beyond\n",
    "the standard library and try out packages like NumPy or Pandas.\n",
    "\n",
    "* **You have textual data represented as Unicode characters?**\n",
    "Use Python’s built-in ```str```. If you need a “mutable string,” use a list\n",
    "of characters.\n",
    "\n",
    "* **You want to store a contiguous block of bytes?** Use the immutable bytes type, or bytearray if you need a mutable data structure."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bibliographic-election",
   "metadata": {},
   "source": [
    "### ```list``` - Mutable Dynamic Arrays\n",
    "\n",
    "* They are implemented as *dynamic arrays* behind the scenes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "appropriate-concentrate",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'one'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = ['one', 'two', 'three']\n",
    "arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "determined-sponsorship",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['one', 'two', 'three']"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Lists have a nice repr:\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "expressed-software",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['one', 'hello', 'three']"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Lists are mutable:\n",
    "arr[1] = 'hello'\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "classified-rapid",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['one', 'three']"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "del arr[1]\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "patent-button",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['one', 'three', 23]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Lists can hold arbitrary data types:\n",
    "arr.append(23)\n",
    "arr"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "destroyed-portable",
   "metadata": {},
   "source": [
    "### ```tuple``` immutable containers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "consolidated-president",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'one'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = 'one', 'two', 'three'\n",
    "arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "modified-metabolism",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('one', 'two', 'three')"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# repr is clean\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "piano-affairs",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'tuple' object doesn't support item deletion",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-28-df001b61e2e0>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mdel\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'tuple' object doesn't support item deletion"
     ]
    }
   ],
   "source": [
    "del arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "lesser-password",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('one', 'two', 'three', 23)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# tuples can hold arbitrary data types\n",
    "arr + (23,)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "canadian-approach",
   "metadata": {},
   "source": [
    "### ```array.array``` basic typed arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "senior-rehabilitation",
   "metadata": {},
   "outputs": [],
   "source": [
    "import array \n",
    "arr = array.array('f', (1.0, 1.5, 2.0, 2.5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "stopped-aging",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "fantastic-riverside",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array('f', [1.0, 23.0, 2.0, 2.5])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[1] = 23.0\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "overall-north",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array('f', [1.0, 2.0, 2.5])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "del arr[1]\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "royal-shame",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array('f', [1.0, 2.0, 2.5, 42.0])"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr.append(42.0)\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "impossible-alert",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "must be real number, not str",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-35-c52072c764fd>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'hello'\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: must be real number, not str"
     ]
    }
   ],
   "source": [
    "arr[1] = 'hello'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "chief-nylon",
   "metadata": {},
   "source": [
    "### ```str``` - immutable arrays of unicode characters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "humanitarian-flashing",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'b'"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = 'abcd'\n",
    "arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "appropriate-trigger",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'abcd'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "theoretical-vegetarian",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'str' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-38-fb67077f22eb>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'e'\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'str' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "arr[1] = 'e'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "stupid-union",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'str' object doesn't support item deletion",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-39-df001b61e2e0>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mdel\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'str' object doesn't support item deletion"
     ]
    }
   ],
   "source": [
    "del arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "musical-synthetic",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'b', 'c', 'd']"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list('abcd')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "thirty-resort",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'abcd'"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "''.join(list('abcd'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "synthetic-thickness",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "str"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# they are recursive data structures\n",
    "type('abc')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "wooden-storm",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "str"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type('abc'[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "photographic-feedback",
   "metadata": {},
   "source": [
    "### ```bytes``` immutable arrays of single bytes\n",
    "\n",
    "Bytes objects are immutable sequences of single bytes (**integers in the\n",
    "range of 0 <= x <= 255**). Conceptually, they’re similar to ```str``` objects,\n",
    "and you can also think of them as immutable arrays of bytes.\n",
    "\n",
    "Like strings, bytes have their own literal syntax for creating objects\n",
    "and they’re space-efficient. Bytes objects are immutable, but unlike\n",
    "strings, there’s a dedicated “mutable byte array” data type called\n",
    "```bytearray``` that they can be unpacked into."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "inclusive-rover",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = bytes((0,1,2,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "ecological-neighborhood",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "biblical-remove",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'\\x00\\x01\\x02\\x03'"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# bytes have their own syntax\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "operating-hardwood",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "bytes() argument 2 must be str, not int",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-47-8c847e7b22d6>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mbytes\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m300\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: bytes() argument 2 must be str, not int"
     ]
    }
   ],
   "source": [
    "bytes(0,300)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "instrumental-investment",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'bytes' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-48-792eca00e7aa>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m23\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'bytes' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "arr[1] = 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "cross-apartment",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'bytes' object doesn't support item deletion",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-49-df001b61e2e0>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mdel\u001b[0m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'bytes' object doesn't support item deletion"
     ]
    }
   ],
   "source": [
    "del arr[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "middle-renewal",
   "metadata": {},
   "source": [
    "### ```bytearray``` - mutable arrays of single bytes\n",
    "\n",
    "The ```bytearray``` type is a mutable sequence of integers in the range\n",
    "0 <= x <= 255. They’re closely related to bytes objects with the\n",
    "main difference being that bytearrays can be modified freely—you can\n",
    "overwrite elements, remove existing elements, or add new ones. \n",
    "\n",
    "The ```bytearray``` object will grow and shrink accordingly.\n",
    "Bytearrays can be converted back into immutable bytes objects but\n",
    "this involves copying the stored data in full—a slow operation taking\n",
    "O(n) time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "helpful-stake",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = bytearray((0,1,2,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "stock-hearts",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "naval-context",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "bytearray(b'\\x00\\x01\\x02\\x03')"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "genetic-unemployment",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "bytearray(b'\\x00\\x17\\x02\\x03')"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[1] = 23\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "foreign-trail",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "endangered-billy",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr.append(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "going-advocacy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "bytearray(b'\\x00\\x17\\x02\\x03*')"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "expensive-catch",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'str' object cannot be interpreted as an integer",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-57-3099852c85ee>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m# Bytearrays can only only \"bytes\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'hello'\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'str' object cannot be interpreted as an integer"
     ]
    }
   ],
   "source": [
    "# Bytearrays can only only \"bytes\"\n",
    "arr[1] = 'hello'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "based-receptor",
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "byte must be in range(0, 256)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-58-6088e2f482e7>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0marr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m300\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mValueError\u001b[0m: byte must be in range(0, 256)"
     ]
    }
   ],
   "source": [
    "arr[1] = 300"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "authentic-choir",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'\\x00\\x17\\x02\\x03*'"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# bytearrays can be converted back into bytes objects:\n",
    "# (this will copy the date)\n",
    "bytes(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "outstanding-humanity",
   "metadata": {},
   "source": [
    "___\n",
    "## 5.3 Records, Structs and Data Transfer Objects"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "identified-sterling",
   "metadata": {},
   "source": [
    "Compared to arrays, records and data structures provide a fixed number of fields, where each field can have a name and may also have a different type. \n",
    "\n",
    "### Summary \n",
    "\n",
    "Now, which type should you use for data objects in Python? As you’ve\n",
    "seen, there’s quite a number of different options for implementing\n",
    "records or data objects. Generally your decision will depend on your\n",
    "use case:\n",
    "\n",
    "* **You only have a few (2-3) fields**: Using a plain ```tuple``` object may\n",
    "be okay if the field order is easy to remember or field names are superfluous. For example, think of an (x, y, z) point in 3D space.\n",
    "\n",
    "* **You need immutable fields**: In this case, plain tuples,\n",
    "```collections.namedtuple```, and ```typing.NamedTuple``` would all\n",
    "make good options for implementing this type of data object.\n",
    "\n",
    "* **You need to lock down field names to avoid typos**:\n",
    "```collections.namedtuple``` and ```typing.NamedTuple``` are your friends\n",
    "here.\n",
    "\n",
    "* **You want to keep things simple**: A plain dictionary object might\n",
    "be a good choice due to the convenient syntax that closely resembles\n",
    "JSON.\n",
    "\n",
    "* **You need full control over your data structure**: It’s time to\n",
    "write a custom class with ```@property``` setters and getters.\n",
    "\n",
    "* **You need to add behavior (methods) to the object**: You\n",
    "should write a custom class, either from scratch or by extending\n",
    "```collections.namedtuple``` or ```typing.NamedTuple```.\n",
    "\n",
    "* **You need to pack data tightly to serialize it to disk or to send\n",
    "it over the network**: Time to read up on ```struct.Struct``` because this is a great use case for it. \n",
    "\n",
    "Generally a safe default choice is a ```collections.namedtuple``` in python 2.x or ```typing.NamedTuple``` in python 3."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "incredible-cycling",
   "metadata": {},
   "source": [
    "### ```dict``` - simple data objects\n",
    "Data objects created using dictionaries are mutable and there's little protection against misspelled field names. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "accepted-pollution",
   "metadata": {},
   "outputs": [],
   "source": [
    "car1 = {\n",
    "    'color': 'red',\n",
    "    'mileage': 3812.4,\n",
    "    'automatic': True,\n",
    "}\n",
    "car2 = {\n",
    "    'color': 'blue',\n",
    "    'mileage': 40231,\n",
    "    'automatic': False,\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "conditional-execution",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'color': 'blue', 'mileage': 40231, 'automatic': False}"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "car2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "manufactured-mirror",
   "metadata": {},
   "outputs": [],
   "source": [
    "# mutable data structures\n",
    "car1['mileage'] = 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "daily-morning",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'color': 'red', 'mileage': 12, 'automatic': True}"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "car1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "accessory-passport",
   "metadata": {},
   "source": [
    "### ```tuple``` immutable groups of objects\n",
    "\n",
    "Tuples take up slightly less memory then lists. As you can see in the bytecode dissembly, below the list constructions takes several more operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "preliminary-young",
   "metadata": {},
   "outputs": [],
   "source": [
    "import dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "round-persian",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  1           0 LOAD_CONST               0 ((23, 'a', 'b', 'c'))\n",
      "              2 RETURN_VALUE\n"
     ]
    }
   ],
   "source": [
    "dis.dis(compile(\"(23, 'a', 'b', 'c')\", '', 'eval'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "viral-tumor",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  1           0 LOAD_CONST               0 (23)\n",
      "              2 LOAD_CONST               1 ('a')\n",
      "              4 LOAD_CONST               2 ('b')\n",
      "              6 LOAD_CONST               3 ('c')\n",
      "              8 BUILD_LIST               4\n",
      "             10 RETURN_VALUE\n"
     ]
    }
   ],
   "source": [
    "dis.dis(compile(\"[23, 'a', 'b', 'c']\", '', 'eval'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "southern-avatar",
   "metadata": {},
   "source": [
    "However, **you shouldn’t place too much emphasis on these differences**.\n",
    "In practice, the performance **difference will often be negligible**, and\n",
    "trying to squeeze extra performance out of a program by switching\n",
    "from lists to tuples will likely be the wrong approach.\n",
    "\n",
    "A potential downside of plain tuples is that the data you store in them\n",
    "can only be pulled out by accessing it through integer indexes. You\n",
    "can’t give names to individual properties stored in a tuple. This can\n",
    "impact code readability.\n",
    "\n",
    "Also, a tuple is always an ad-hoc structure: **It’s difficult to ensure that\n",
    "two tuples have the same number of fields and the same properties\n",
    "stored on them.**\n",
    "\n",
    "This makes it easy to introduce *slip-of-the-mind* bugs, such as mixing up the field order. Therefore it is recommended that you keep\n",
    "the number of fields stored in a tuple as low as possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "unauthorized-gravity",
   "metadata": {},
   "outputs": [],
   "source": [
    "# no protection against mising extra/fields\n",
    "car1 = ('red', 3812.4, True)\n",
    "car2 = (3431.5, 'green', True, 'silver')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "retired-request",
   "metadata": {},
   "source": [
    "### Writing a Custom Class – More Work, More Control\n",
    "\n",
    "Fields stored on classes are mutable, and new fields can be added\n",
    "freely, which you may or may not like. It’s possible to provide more\n",
    "access control and to create read-only fields using the ```@property``` decorator, but once again, **this requires writing more boilerplate code**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "convertible-health",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Car:\n",
    "    def __init__(self, color, mileage, automatic):\n",
    "        self.color = color\n",
    "        self.mileage = mileage\n",
    "        self.automatic = automatic"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bearing-clone",
   "metadata": {},
   "source": [
    "### ```collections.namedtuple``` convenient data objects\n",
    "\n",
    "Namedtuples can be an easy way to clean up your code and make it\n",
    "more readable by enforcing a **better structure for your data**.\n",
    "\n",
    "When it comes to memory usage, they are also “better” than\n",
    "regular classes and just as memory efficient as regular tuples.\n",
    "\n",
    "Using namedtuples over regular (unstructured) tuples and dicts can\n",
    "also make **coworkers’ lives easier**: Namedtuples make the data\n",
    "that’s being passed around “self-documenting”, at least to a degree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "annoying-velvet",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "from sys import getsizeof\n",
    "\n",
    "p1 = namedtuple('Point', 'x y z')(1, 2, 3)\n",
    "p2 = (1, 2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "younger-tunisia",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "64"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getsizeof(p1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "civil-stocks",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "64"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getsizeof(p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "regulated-freeware",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Car(color='red', mileage=3812.4, automatic=True)"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# they have a nice repr so save time\n",
    "# read only and protects against mispelt fields\n",
    "Car = namedtuple('Car' , 'color mileage automatic')\n",
    "car1 = Car('red', 3812.4, True)\n",
    "car1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "cutting-stevens",
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "can't set attribute",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-73-b5f0e1add0af>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mcar1\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mmileage\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m12\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m: can't set attribute"
     ]
    }
   ],
   "source": [
    "car1.mileage = 12"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "permanent-nicholas",
   "metadata": {},
   "source": [
    "### ```typing.NamedTuple``` - improved Namedtuples\n",
    "\n",
    "Very similar to ```namedtuple``` with the main difference being an **updated syntax and support for type hints**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "unknown-resistance",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import NamedTuple\n",
    "\n",
    "class Car(NamedTuple):\n",
    "    # type hints can be very helpful\n",
    "    color : str\n",
    "    mileage : float \n",
    "    automatic : bool"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "global-garden",
   "metadata": {},
   "outputs": [],
   "source": [
    "car1 = Car('red', 3812.4, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "close-communications",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Car(color='red', mileage=3812.4, automatic=True)"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "car1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "periodic-commodity",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3812.4"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "car1.mileage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "norman-france",
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "can't set attribute",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-78-b5f0e1add0af>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mcar1\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mmileage\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;36m12\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m: can't set attribute"
     ]
    }
   ],
   "source": [
    "car1.mileage = 12"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "statewide-radar",
   "metadata": {},
   "source": [
    "#### Type annotations are not enforced without a separate type checking tool like ```mypy```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "great-material",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Car(color='red', mileage='NOT_A_FLOAT', automatic=99)"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Car('red', 'NOT_A_FLOAT', 99)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "suburban-click",
   "metadata": {},
   "source": [
    "### ```struct.Struct``` serialized C structs \n",
    "\n",
    "This class **converts between python values and C structs** serialized into Python ```bytes``` objects. Structs are defined using a format strings-like mini language that allows you to define the arrangement of various C data types like ```char```, ```int``` and ```long``` aswell as their ```unsigned``` variants. \n",
    "\n",
    "They’re intended primarily as a\n",
    "**data exchange format**, rather than as a way of holding data in memory\n",
    "that’s only used by Python code.\n",
    "\n",
    "Reference : https://docs.python.org/3/library/struct.html#struct.Struct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "documented-programming",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'\\x17\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00(B'"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from struct import Struct \n",
    "# accepts integers, booleans or floats\n",
    "MyStruct = Struct('i?f')\n",
    "data = MyStruct.pack(23, False, 42.0)\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "pretty-dialogue",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(23, False, 42.0)"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MyStruct.unpack(data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "streaming-columbus",
   "metadata": {},
   "source": [
    "### ```types.SimpleNamespace``` fancy attribute access\n",
    "\n",
    "A bit of an esoteric choice for implementing data objects in Python that provides attribute access to its namespace. \n",
    "\n",
    "This means ```SimpleNamespace``` instances expose all of their keys as\n",
    "class attributes. This means you can use ```obj.key``` “dotted” attribute\n",
    "access instead of the ```obj['key']``` square-brackets indexing syntax\n",
    "that’s used by regular dicts. All instances also include a meaningful\n",
    "```__repr__``` by default."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "alternative-factory",
   "metadata": {},
   "outputs": [],
   "source": [
    "from types import SimpleNamespace\n",
    "car1 = SimpleNamespace(color='red', mileage=3812.4, automatic=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "complimentary-given",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "namespace(color='red', mileage=3812.4, automatic=True)"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "car1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "quantitative-breathing",
   "metadata": {},
   "source": [
    "Instances support attribute access and are mutable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "grave-crash",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "namespace(color='red', mileage=12, windshield='broken')"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "car1.mileage = 12\n",
    "car1.windshield = 'broken'\n",
    "del car1.automatic\n",
    "car1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "driving-plastic",
   "metadata": {},
   "source": [
    "___\n",
    "## 5.4 Sets and Multisets\n",
    "\n",
    "A set is an **unordered collection of objects that does not allow duplicate elements**. Typically, sets are used to quickly test a value for membership in the set, to insert or delete new values from a set, and to\n",
    "compute the union or intersection of two sets.\n",
    "\n",
    "In a “proper” set implementation, membership tests are expected to\n",
    "run in fast O(1) time. Union, intersection, difference, and subset operations should take O(n) time on average. The set implementations\n",
    "included in Python’s standard library follow these performance characteristics.\n",
    "\n",
    "### Key Takeaways\n",
    "* Sets are another useful and commonly used data structure included with Python and its standard library.\n",
    "* Use the built-in ```set``` type when looking for a mutable set.\n",
    "* frozenset objects are hashable and can be used as dictionary\n",
    "or set keys.\n",
    "* ```collections.Counter``` implements multiset or “bag” data\n",
    "structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "entertaining-bikini",
   "metadata": {},
   "outputs": [],
   "source": [
    "# special set syntax \n",
    "vowels = {'a'}\n",
    "squares = {x*x for x in range(10)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "italic-minutes",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# this is a dictionary\n",
    "my_set = {}\n",
    "type(my_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "announced-ranch",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you need to use set()\n",
    "my_set = set()\n",
    "type(my_set)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sacred-specialist",
   "metadata": {},
   "source": [
    "### ```set``` - the go to"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "written-northwest",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vowels = {'a', 'e', 'i', 'o', 'u'}\n",
    "'e' in vowels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "digital-savings",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a', 'e', 'i'}"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "letters = set('alice')\n",
    "letters.intersection(vowels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "constant-square",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a', 'e', 'i', 'o', 'u', 'x'}"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vowels.add('x')\n",
    "vowels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "rubber-wrapping",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(vowels)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "worthy-accordance",
   "metadata": {},
   "source": [
    "### ```frozenset``` - immutable sets\n",
    "They can be **used as dictionary keys**!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "administrative-authentication",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "frozenset({'a', 'e', 'i', 'o', 'u'})"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vowels = frozenset('aeiou')\n",
    "vowels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "focal-sessions",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {frozenset({1,2,3}) : 'hello'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "equipped-atlantic",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'hello'"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d[frozenset({1,2,3})]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "involved-founder",
   "metadata": {},
   "source": [
    "### ```collections.Counter``` - multisets\n",
    "\n",
    "A class which allows elements in the set to have more than one occurance. This is useful if you need to keep track if objects occur and **how many times they occur**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "ideal-leather",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter \n",
    "inventory = Counter()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "mexican-standard",
   "metadata": {},
   "outputs": [],
   "source": [
    "# update is a powerful method\n",
    "loot = {'sword' : 1, 'bread' : 3}\n",
    "inventory.update(loot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "recovered-picking",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'sword': 1, 'bread': 3})"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inventory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "accessory-weight",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'sword': 4, 'bread': 3, 'apple': 1})"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "more_loot = {'sword': 3, 'apple': 1}\n",
    "inventory.update(more_loot)\n",
    "inventory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "small-coaching",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# unique elements in inventory\n",
    "len(inventory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "entire-humanitarian",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# total number of items in inventory\n",
    "sum(inventory.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "known-wireless",
   "metadata": {},
   "source": [
    "___\n",
    "## 5.5 Stacks (LIFO)\n",
    "\n",
    "A stack is a collection of objects that supports fast last-in, first-out\n",
    "(LIFO) semantics for inserts and deletes. Unlike lists or arrays, stacks\n",
    "typically don’t allow for random access to the objects they contain.\n",
    "The insert and delete operations are also often called push and pop.\n",
    "\n",
    "With a **queue**, you remove the the first item in(first-in, firstout or FIFO); but with a **stack**, you remove the item most recently\n",
    "added (last-in, first-out or LIFO).\n",
    "\n",
    "### Summary \n",
    "\n",
    "* Python ships with several stack implementations that have\n",
    "slightly different performance and usage characteristics.\n",
    "* ```collections.deque``` provides a safe and fast general-purpose\n",
    "stack implementation.\n",
    "* The built-in list type can be used as a stack, but be careful\n",
    "to only append and remove items with append() and pop() in\n",
    "order to avoid slow performance."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "informative-sector",
   "metadata": {},
   "source": [
    "### ```list``` - simple built-in stacks\n",
    "\n",
    "Python’s built-in list type makes a decent stack data structure as it\n",
    "supports push and pop operations in amortized O(1) time.\n",
    "\n",
    "To get the amortized O(1) performance for inserts and deletes, new\n",
    "**items must be added to the end of the list with the append() method\n",
    "and removed again from the end using pop()**. \n",
    "\n",
    "Adding and removing from the front is much slower and takes O(n)\n",
    "time, as the existing elements must be shifted around to make room\n",
    "for the new element. This is a **performance antipattern** that you\n",
    "should avoid as much as possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "textile-syntax",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['eat', 'sleep', 'code']"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = []\n",
    "s.append('eat')\n",
    "s.append('sleep')\n",
    "s.append('code')\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "accomplished-bennett",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'code'"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "active-needle",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'sleep'"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "boring-survivor",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eat'"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "palestinian-championship",
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "pop from empty list",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-105-c88c8c48122b>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0ms\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mIndexError\u001b[0m: pop from empty list"
     ]
    }
   ],
   "source": [
    "s.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exterior-courtesy",
   "metadata": {},
   "source": [
    "### ```collections.deque``` - Fast & Robust Stacks \n",
    "\n",
    "The deque class implements a double-ended queue that supports\n",
    "adding and removing elements from either end in O(1) time (nonamortized). Because deques support adding and removing elements\n",
    "from either end equally well, they can serve both as queues and as\n",
    "stacks.\n",
    "\n",
    "Python’s deque objects are implemented as **doubly-linked lists** which\n",
    "gives them excellent and consistent performance for inserting and\n",
    "deleting elements, but **poor O(n) performance for randomly accessing\n",
    "elements in the middle of a stack**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "illegal-referral",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['eat', 'sleep', 'code'])"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque \n",
    "s = deque()\n",
    "s.append('eat')\n",
    "s.append('sleep')\n",
    "s.append('code')\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "controlled-scholarship",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'code'"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "weekly-meeting",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eat'"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.popleft()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cooperative-czech",
   "metadata": {},
   "source": [
    "### ```queue.LifoQueue``` - Locking semantics for parallel computing\n",
    "\n",
    "This stack implementation in the Python standard library is synchronized and provides locking semantics to support multiple concurrent\n",
    "producers and consumers. \n",
    "\n",
    "Besides ```LifoQueue```, the ```queue``` module contains several other classes\n",
    "that implement multi-producer/multi-consumer queues that are useful for **parallel computing**.\n",
    "\n",
    "Be careful with ```s.get()``` because this can cause the program to wait forever. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "lesser-holmes",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<queue.LifoQueue at 0x229ea0c82b0>"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from queue import LifoQueue\n",
    "s = LifoQueue()\n",
    "s.put('eat')\n",
    "s.put('sleep')\n",
    "s.put('code')\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "after-rugby",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'code'"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "intermediate-albert",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'sleep'"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "consolidated-orlando",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eat'"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.get_nowait()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "substantial-vaccine",
   "metadata": {},
   "outputs": [
    {
     "ename": "Empty",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mEmpty\u001b[0m                                     Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-113-0bd7ad76be38>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0ms\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mget_nowait\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m~\\anaconda3\\envs\\Keras-workspace\\lib\\queue.py\u001b[0m in \u001b[0;36mget_nowait\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m    196\u001b[0m         \u001b[1;32mraise\u001b[0m \u001b[0mthe\u001b[0m \u001b[0mEmpty\u001b[0m \u001b[0mexception\u001b[0m\u001b[1;33m.\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    197\u001b[0m         '''\n\u001b[1;32m--> 198\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mget\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mblock\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mFalse\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    199\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    200\u001b[0m     \u001b[1;31m# Override these methods to implement other queue organizations\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\anaconda3\\envs\\Keras-workspace\\lib\\queue.py\u001b[0m in \u001b[0;36mget\u001b[1;34m(self, block, timeout)\u001b[0m\n\u001b[0;32m    165\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mblock\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    166\u001b[0m                 \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_qsize\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 167\u001b[1;33m                     \u001b[1;32mraise\u001b[0m \u001b[0mEmpty\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    168\u001b[0m             \u001b[1;32melif\u001b[0m \u001b[0mtimeout\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    169\u001b[0m                 \u001b[1;32mwhile\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_qsize\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mEmpty\u001b[0m: "
     ]
    }
   ],
   "source": [
    "s.get_nowait()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exterior-ivory",
   "metadata": {},
   "source": [
    "### Comparing stack implementations\n",
    "\n",
    "If you’re **not looking for parallel processing support** (or don’t want to\n",
    "handle locking and unlocking manually), your choice comes down to\n",
    "the built-in ```list``` type or ```collections.deque```. The difference lies in\n",
    "the data structure used behind the scenes and overall ease of use:\n",
    "\n",
    "* ```list``` is backed by a dynamic array which makes it great for **fast random access**, but requires occasional resizing when elements are added or removed. The list over-allocates its backing storage so that not every push or pop requires resizing, and you get an amortized O(1) time complexity for these operations. But you do need to **be careful to only insert and remove items “from the right side” using append() and pop()**. Otherwise, performance slows down to O(n).\n",
    "* ```collections.deque``` is backed by a **doubly-linked list** which optimizes appends and deletes at **both ends** and provides consistent O(1) performance for these operations. Not only is its performance more stable, the deque class is also easier to use because **you don’t have to worry about adding or removing items from “the wrong end.”**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "boolean-article",
   "metadata": {},
   "source": [
    "___\n",
    "## 5.6 Queues (FIFO)\n",
    "\n",
    "A queue is a collection of objects that supports fast first-in, first-out\n",
    "(FIFO) semantics for inserts and deletes. The insert and delete operations are sometimes called enqueue and dequeue. Unlike lists or\n",
    "arrays, queues typically don’t allow for random access to the objects\n",
    "they contain.\n",
    "\n",
    "Performance-wise, a proper queue implementation is expected to take\n",
    "O(1) time for insert and delete operations. These are the two main\n",
    "operations performed on a queue, and in a correct implementation,\n",
    "they should be fast.\n",
    "\n",
    "### Summary \n",
    "\n",
    "* Python includes several queue implementations as part of the\n",
    "core language and its standard library.\n",
    "* list objects can be used as queues, but this is generally not\n",
    "recommended due to slow performance.\n",
    "* If you’re not looking for parallel processing support, the implementation offered by collections.deque is an excellent default choice for implementing a FIFO queue data structure in\n",
    "Python. It provides the performance characteristics you’d expect from a good queue implementation and can also be used\n",
    "as a stack (LIFO Queue).\n",
    "\n",
    "### Applications \n",
    "\n",
    "* A short and beautiful algorithm using a queue is breadth-first search (BFS) on a tree or graph data structure.\n",
    "* Scheduling algorithms often use **priority queues** internally. These are specialized queues: Instead of retrieving the next element by insertion time, a priority queue retrieves the **highest-priority element**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "favorite-communist",
   "metadata": {},
   "source": [
    "### ```list``` - slow queues\n",
    "\n",
    "Lists are quite slow for this purpose because inserting or deleting an element at the beginning requires shifting all of the other elements by one, requiring O(n) time.\n",
    "\n",
    "Therefore, **it is not recommended to use a list as a makeshift\n",
    "queue in Python**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "entertaining-degree",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eat'"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q = []\n",
    "q.append('eat')\n",
    "q.append('sleep')\n",
    "q.append('code')\n",
    "# this is slow\n",
    "q.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "injured-victoria",
   "metadata": {},
   "source": [
    "### ```collections.deque``` – Fast & Robust Queues\n",
    "\n",
    "Python’s deque objects are implemented as **doubly-linked lists**. This\n",
    "gives them excellent and consistent performance for inserting and\n",
    "deleting elements, but **poor O(n) performance for randomly accessing**\n",
    "elements in the middle of the stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "relative-homeless",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eat'"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "q = deque()\n",
    "q.append('eat')\n",
    "q.append('sleep')\n",
    "q.append('code')\n",
    "q.append('repeat')\n",
    "\n",
    "q.popleft()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "velvet-brief",
   "metadata": {},
   "source": [
    "### ```queue.Queue``` locking semantics for parallel computing "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "personal-liechtenstein",
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import Queue \n",
    "q = Queue()\n",
    "q.put('eat')\n",
    "q.put('sleep')\n",
    "q.put('code')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "encouraging-entertainment",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<queue.Queue at 0x229ea0c84c0>"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "utility-opinion",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eat'"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "moderate-natural",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'sleep'"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.get_nowait()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "divided-silicon",
   "metadata": {},
   "source": [
    "### ```multiprocessing.Queue``` – Shared Job Queues\n",
    "\n",
    "**Reference :** https://docs.python.org/3/library/multiprocessing.html#multiprocessing.Queue\n",
    "\n",
    "This is a shared job queue implementation that allows queued items\n",
    "to be processed in parallel by multiple concurrent workers. \n",
    "\n",
    "Process based parallelization is popular in CPython due to the global interpreter lock (GIL) that prevents some forms of parallel execution on a\n",
    "single interpreter process.\n",
    "\n",
    "```multiprocessing.Queue``` makes it easy to distribute work across multiple processes in order to work around the GIL limitations. This type of queue can store and transfer any pickle-able object across process boundaries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "aware-register",
   "metadata": {},
   "outputs": [],
   "source": [
    "from multiprocessing import Queue\n",
    "\n",
    "q = Queue()\n",
    "\n",
    "q.put('eat')\n",
    "q.put('sleep')\n",
    "q.put('code')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "decent-february",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<multiprocessing.queues.Queue at 0x229ea0c89a0>"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "id": "union-knife",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eat'"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "superb-aside",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'sleep'"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.get_nowait()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "powerful-water",
   "metadata": {},
   "source": [
    "___\n",
    "## 5.7 Priority Queues\n",
    "\n",
    "A priority queue is a container data structure that manages a set of\n",
    "records with totally-ordered keys (for example, a numeric weight\n",
    "value) to provide quick access to the record with the **smallest or largest\n",
    "key in the set**.\n",
    "\n",
    "You can think of a priority queue as a modified queue: instead of retrieving the next element by insertion time, **it retrieves the highest priority element**. The priority of individual elements is decided by\n",
    "the ordering applied to their keys.\n",
    "\n",
    "### Summary \n",
    "\n",
    "* Python includes several priority queue implementations for\n",
    "you to use.\n",
    "* ```queue.PriorityQueue``` stands out from the pack with a nice\n",
    "object-oriented interface and a name that clearly states its intent. It should be your preferred choice.\n",
    "* If you’d like to avoid the locking overhead of ```queue.PriorityQueue```,\n",
    "using the ```heapq``` module directly is also a good option.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "through-release",
   "metadata": {},
   "source": [
    "### ```list``` maintaining a manually small sorted queue\n",
    "\n",
    "You can use a sorted ```list```. Inserting new elements is an O(N) operation. The insertion point can be found using ```bisect.insort``` in O(log N) time.  \n",
    "\n",
    "**Reference :** https://docs.python.org/3/library/bisect.html#bisect.insort "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "happy-psychology",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(3, 'sleep'), (2, 'code'), (1, 'eat')]\n",
      "\n",
      "(1, 'eat')\n",
      "(2, 'code')\n",
      "(3, 'sleep')\n"
     ]
    }
   ],
   "source": [
    "q = []\n",
    "\n",
    "# NOTE: Remember to re-sort every time\n",
    "# a new element is inserted, or use\n",
    "# bisect.insort().\n",
    "\n",
    "q.append((2, 'code'))\n",
    "q.append((1, 'eat'))\n",
    "q.append((3, 'sleep'))\n",
    "\n",
    "q.sort(reverse=True)\n",
    "\n",
    "print(q)\n",
    "print()\n",
    "\n",
    "while q:\n",
    "    next_item = q.pop()\n",
    "    print(next_item)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "noble-clock",
   "metadata": {},
   "source": [
    "### ```heapq``` list based binary heaps\n",
    "\n",
    "This is a **binary heap implementation** usually backed by a plain list,\n",
    "and it supports insertion and extraction of the smallest element in\n",
    "O(log n) time. \n",
    "\n",
    "Since ```heapq``` technically only provides a min-heap implementation, extra steps must be taken to ensure sort stability and other\n",
    "features typically expected from a “practical” priority queue. \n",
    "\n",
    "#### References\n",
    "\n",
    "* https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes\n",
    "* https://docs.python.org/3/library/queue.html#queue.PriorityQueue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "id": "blind-gregory",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 'eat')\n",
      "(2, 'code')\n",
      "(3, 'sleep')\n"
     ]
    }
   ],
   "source": [
    "import heapq\n",
    "q = []\n",
    "# each element has a priority and the data payload\n",
    "\n",
    "heapq.heappush(q, (2, 'code'))\n",
    "heapq.heappush(q, (1, 'eat'))\n",
    "heapq.heappush(q, (3, 'sleep'))\n",
    "\n",
    "while q:\n",
    "    next_item = heapq.heappop(q)\n",
    "    print(next_item)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lined-reach",
   "metadata": {},
   "source": [
    "### ```queue.PriorityQueue``` – Beautiful Priority Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cloudy-alert",
   "metadata": {},
   "source": [
    "This priority queue implementation uses ```heapq``` internally and **shares\n",
    "the same time and space complexities**. The difference is that PriorityQueue is synchronized and provides\n",
    "locking semantics to support **multiple concurrent producers** and consumers.Depending on your use case, this might be helpful—or just slow your program down slightly. In any case, you might prefer the **class-based\n",
    "interface** provided by ```PriorityQueue``` over using the function-based\n",
    "interface provided by ```heapq```.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "negative-pharmaceutical",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 'eat')\n",
      "(2, 'code')\n",
      "(3, 'sleep')\n"
     ]
    }
   ],
   "source": [
    "from queue import PriorityQueue\n",
    "\n",
    "q = PriorityQueue()\n",
    "q.put((2, 'code'))\n",
    "q.put((1, 'eat'))\n",
    "q.put((3, 'sleep'))\n",
    "\n",
    "while not q.empty():\n",
    "    next_item = q.get()\n",
    "    print(next_item)"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}