{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 2 — An Array of Sequences\n",
    "\n",
    "**Sections with code snippets in this chapter:**\n",
    "\n",
    "* [List Comprehensions and Generator Expressions](#List-Comprehensions-and-Generator-Expressions)\n",
    "* [Slicing](#Slicing)\n",
    "* [Building Lists of Lists](#Building-Lists-of-Lists)\n",
    "* [Augmented Assignment with Sequences](#Augmented-Assignment-with-Sequences)\n",
    "* [list.sort and the sorted Built-In Function](#list.sort-and-the-sorted-Built-In-Function)\n",
    "* [Managing Ordered Sequences with bisect](#Managing-Ordered-Sequences-with-bisect)\n",
    "* [Arrays](#Arrays)\n",
    "* [Memory Views](#Memory-Views)\n",
    "* [NumPy and SciPy](#NumPy-and-SciPy)\n",
    "* [Deques and Other Queues](#Deques-and-Other-Queues)\n",
    "* [Soapbox](#Soapbox)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List Comprehensions and Generator Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-1. Build a list of Unicode codepoints from a string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[36, 162, 163, 165, 8364, 164]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "symbols = '$¢£¥€¤'\n",
    "codes = []\n",
    "\n",
    "for symbol in symbols:\n",
    "    codes.append(ord(symbol))\n",
    "\n",
    "codes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-2. Build a list of Unicode codepoints from a string, take 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[36, 162, 163, 165, 8364, 164]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "symbols = '$¢£¥€¤'\n",
    "\n",
    "codes = [ord(symbol) for symbol in symbols]\n",
    "\n",
    "codes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Box: Listcomps No Longer Leak Their Variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ABC'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = 'ABC'\n",
    "codes = [ord(x) for x in x]\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[65, 66, 67]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "codes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-3. The same list built by a listcomp and a map/filter composition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[162, 163, 165, 8364, 164]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "symbols = '$¢£¥€¤'\n",
    "beyond_ascii = [ord(s) for s in symbols if ord(s) > 127]\n",
    "beyond_ascii"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[162, 163, 165, 8364, 164]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "beyond_ascii = list(filter(lambda c: c > 127, map(ord, symbols)))\n",
    "beyond_ascii"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-4. Cartesian product using a list comprehension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('black', 'S'),\n",
       " ('black', 'M'),\n",
       " ('black', 'L'),\n",
       " ('white', 'S'),\n",
       " ('white', 'M'),\n",
       " ('white', 'L')]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "colors = ['black', 'white']\n",
    "sizes = ['S', 'M', 'L']\n",
    "tshirts = [(color, size) for color in colors for size in sizes]\n",
    "tshirts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('black', 'S')\n",
      "('black', 'M')\n",
      "('black', 'L')\n",
      "('white', 'S')\n",
      "('white', 'M')\n",
      "('white', 'L')\n"
     ]
    }
   ],
   "source": [
    "for color in colors:\n",
    "    for size in sizes:\n",
    "        print((color, size))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('black', 'S'),\n",
       " ('black', 'M'),\n",
       " ('black', 'L'),\n",
       " ('white', 'S'),\n",
       " ('white', 'M'),\n",
       " ('white', 'L')]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shirts = [(color, size) for size in sizes\n",
    "                        for color in colors]\n",
    "tshirts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-5. Initializing a tuple and an array from a generator expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(36, 162, 163, 165, 8364, 164)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "symbols = '$¢£¥€¤'\n",
    "tuple(ord(symbol) for symbol in symbols)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array('I', [36, 162, 163, 165, 8364, 164])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import array\n",
    "array.array('I', (ord(symbol) for symbol in symbols))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-6. Cartesian product in a generator expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "black S\n",
      "black M\n",
      "black L\n",
      "white S\n",
      "white M\n",
      "white L\n"
     ]
    }
   ],
   "source": [
    "colors = ['black', 'white']\n",
    "sizes = ['S', 'M', 'L']\n",
    "\n",
    "for tshirt in ('%s %s' % (c, s) for c in colors for s in sizes):\n",
    "    print(tshirt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Slicing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Why Slices and Range Exclude the Last Item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [10, 20, 30, 40, 50, 60]\n",
    "\n",
    "l[:2]  # split at 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[30, 40, 50, 60]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20, 30]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l[:3]  # split at 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[40, 50, 60]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l[3:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Slice Objects"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bye'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'bicycle'\n",
    "s[::3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'elcycib'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eccb'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s[::-2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-9. Line items from a flat-file invoice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    $17.50   imoroni PiBrella                  \n",
      "     $4.95   mm Tactile Switch x20             \n",
      "    $28.00   anavise Jr. - PV-201              \n",
      "    $34.95   iTFT Mini Kit 320x240             \n",
      " \n"
     ]
    }
   ],
   "source": [
    "invoice = \"\"\"\n",
    "0.....6.................................40........52...55........\n",
    "1909 Pimoroni PiBrella                      $17.50    3    $52.50\n",
    "1489 6mm Tactile Switch x20                  $4.95    2    $9.90\n",
    "1510 Panavise Jr. - PV-201                  $28.00    1    $28.00\n",
    "1601 PiTFT Mini Kit 320x240                 $34.95    1    $34.95\n",
    "\"\"\"\n",
    "\n",
    "SKU = slice(0, 6)\n",
    "DESCRIPTION = slice(6, 40)\n",
    "UNIT_PRICE = slice(40, 52)\n",
    "QUANTITY = slice(52, 55)\n",
    "ITEM_TOTAL = slice(55, None)\n",
    "\n",
    "line_items = invoice.split('\\n')[2:]\n",
    "\n",
    "for item in line_items:\n",
    "    print(item[UNIT_PRICE], item[DESCRIPTION])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Assigning to Slices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = list(range(10))\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 20, 30, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l[2:5] = [20, 30]\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 20, 30, 5, 8, 9]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "del l[5:7]\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 20, 11, 5, 22, 9]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l[3::2] = [11, 22]\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By design, this example raises an exception::"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TypeError('can only assign an iterable')\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    l[2:5] = 100\n",
    "except TypeError as e:\n",
    "    print(repr(e))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 100, 22, 9]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l[2:5] = [100]\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using + and * with Sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1, 2, 3]\n",
    "l * 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'abcdabcdabcdabcdabcd'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5 * 'abcd'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Building Lists of Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-10. A list with three lists of length 3 can represent a tic-tac-toe board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "board = [['_'] * 3 for i in range(3)]\n",
    "board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['_', '_', '_'], ['_', '_', 'X'], ['_', '_', '_']]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "board[1][2] = 'X'\n",
    "board"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-11. A list with three references to the same list is useless"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weird_board = [['_'] * 3] * 3\n",
    "weird_board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['_', '_', 'O'], ['_', '_', 'O'], ['_', '_', 'O']]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weird_board[1][2] = 'O'\n",
    "weird_board"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Explanation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "board = []\n",
    "for i in range(3):\n",
    "    row = ['_'] * 3\n",
    "    board.append(row)\n",
    "board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['_', '_', '_'], ['_', '_', '_'], ['X', '_', '_']]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "board[2][0] = 'X'\n",
    "board"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Augmented Assignment with Sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [1, 2, 3]\n",
    "idl = id(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4414271936"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# NBVAL_IGNORE_OUTPUT\n",
    "idl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 1, 2, 3]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l *= 2\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "id(l) == idl  # same list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = (1, 2, 3)\n",
    "idt = id(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4414275328"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# NBVAL_IGNORE_OUTPUT\n",
    "idt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t *= 2\n",
    "id(t) == idt # new tuple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A += Assignment Puzzler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TypeError(\"'tuple' object does not support item assignment\")\n"
     ]
    }
   ],
   "source": [
    "t = (1, 2, [30, 40])\n",
    "try:\n",
    "    t[2] += [50, 60]\n",
    "except TypeError as e:\n",
    "    print(repr(e))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 2, [30, 40, 50, 60])"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-14. Bytecode for the expression s[a] += b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  1           0 LOAD_NAME                0 (s)\n",
      "              2 LOAD_NAME                1 (a)\n",
      "              4 DUP_TOP_TWO\n",
      "              6 BINARY_SUBSCR\n",
      "              8 LOAD_NAME                2 (b)\n",
      "             10 INPLACE_ADD\n",
      "             12 ROT_THREE\n",
      "             14 STORE_SUBSCR\n",
      "             16 LOAD_CONST               0 (None)\n",
      "             18 RETURN_VALUE\n"
     ]
    }
   ],
   "source": [
    "import dis\n",
    "\n",
    "dis.dis('s[a] += b')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## list.sort and the sorted Built-In Function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['apple', 'banana', 'grape', 'raspberry']"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fruits = ['grape', 'raspberry', 'apple', 'banana']\n",
    "sorted(fruits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['grape', 'raspberry', 'apple', 'banana']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fruits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['raspberry', 'grape', 'banana', 'apple']"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(fruits, reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['grape', 'apple', 'banana', 'raspberry']"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(fruits, key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['raspberry', 'banana', 'grape', 'apple']"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(fruits, key=len, reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['grape', 'raspberry', 'apple', 'banana']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fruits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['apple', 'banana', 'grape', 'raspberry']"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fruits.sort()\n",
    "fruits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Managing Ordered Sequences with bisect"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-15. bisect finds insertion points for items in a sorted sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DEMO: bisect_right\n",
      "haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30\n",
      "31 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |31\n",
      "30 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |30\n",
      "29 @ 13      |  |  |  |  |  |  |  |  |  |  |  |  |29\n",
      "23 @ 11      |  |  |  |  |  |  |  |  |  |  |23\n",
      "22 @  9      |  |  |  |  |  |  |  |  |22\n",
      "10 @  5      |  |  |  |  |10\n",
      " 8 @  5      |  |  |  |  |8 \n",
      " 5 @  3      |  |  |5 \n",
      " 2 @  1      |2 \n",
      " 1 @  1      |1 \n",
      " 0 @  0    0 \n"
     ]
    }
   ],
   "source": [
    "# BEGIN BISECT_DEMO\n",
    "import bisect\n",
    "import sys\n",
    "\n",
    "HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]\n",
    "NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]\n",
    "\n",
    "ROW_FMT = '{0:2d} @ {1:2d}    {2}{0:<2d}'\n",
    "\n",
    "def demo(haystack, needles, bisect_fn):\n",
    "    print('DEMO:', bisect_fn.__name__)  # <1>\n",
    "    print('haystack ->', ' '.join('%2d' % n for n in haystack))\n",
    "    for needle in reversed(needles):\n",
    "        position = bisect_fn(haystack, needle)  # <2>\n",
    "        offset = position * '  |'  # <3>\n",
    "        print(ROW_FMT.format(needle, position, offset))  # <4>\n",
    "\n",
    "demo(HAYSTACK, NEEDLES, bisect.bisect)  # <5>\n",
    "# END BISECT_DEMO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DEMO: bisect_left\n",
      "haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30\n",
      "31 @ 14      |  |  |  |  |  |  |  |  |  |  |  |  |  |31\n",
      "30 @ 13      |  |  |  |  |  |  |  |  |  |  |  |  |30\n",
      "29 @ 12      |  |  |  |  |  |  |  |  |  |  |  |29\n",
      "23 @  9      |  |  |  |  |  |  |  |  |23\n",
      "22 @  9      |  |  |  |  |  |  |  |  |22\n",
      "10 @  5      |  |  |  |  |10\n",
      " 8 @  4      |  |  |  |8 \n",
      " 5 @  2      |  |5 \n",
      " 2 @  1      |2 \n",
      " 1 @  0    1 \n",
      " 0 @  0    0 \n"
     ]
    }
   ],
   "source": [
    "demo(HAYSTACK, NEEDLES, bisect.bisect_left)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-16. Given a test score, grade returns the corresponding letter grade"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['F', 'D', 'D', 'C', 'C', 'B', 'B', 'A', 'A']"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):\n",
    "    i = bisect.bisect(breakpoints, score)\n",
    "    return grades[i]\n",
    "\n",
    "[grade(score) for score in [55, 60, 65, 70, 75, 80, 85, 90, 95]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-17. bisect_left maps a score of 60 to grade F, not D as in Example 2-16."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['F', 'F', 'D', 'D', 'C', 'C', 'B', 'B', 'A']"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):\n",
    "    i = bisect.bisect_left(breakpoints, score)\n",
    "    return grades[i]\n",
    "\n",
    "[grade(score) for score in [55, 60, 65, 70, 75, 80, 85, 90, 95]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-18. Insort keeps a sorted sequence always sorted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "insert 10 -> [10]\n",
      "insert  0 -> [0, 10]\n",
      "insert  6 -> [0, 6, 10]\n",
      "insert  8 -> [0, 6, 8, 10]\n",
      "insert  7 -> [0, 6, 7, 8, 10]\n",
      "insert  2 -> [0, 2, 6, 7, 8, 10]\n",
      "insert 10 -> [0, 2, 6, 7, 8, 10, 10]\n"
     ]
    }
   ],
   "source": [
    "import bisect\n",
    "import random\n",
    "\n",
    "SIZE = 7\n",
    "\n",
    "random.seed(1729)\n",
    "\n",
    "my_list = []\n",
    "\n",
    "for i in range(SIZE):\n",
    "    new_item = random.randrange(SIZE*2)\n",
    "    bisect.insort(my_list, new_item)\n",
    "    print(f'insert {new_item:2d} -> {my_list}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## When a List Is Not the Answer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-19. Creating, saving, and loading a large array of floats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5963321947530882"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from array import array\n",
    "from random import random\n",
    "\n",
    "floats = array('d', (random() for i in range(10**7)))\n",
    "floats[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('floats.bin', 'wb') as fp:\n",
    "    floats.tofile(fp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5963321947530882"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "floats2 = array('d')\n",
    "\n",
    "with open('floats.bin', 'rb') as fp:\n",
    "    floats2.fromfile(fp, 10**7)\n",
    "\n",
    "floats2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "floats2 == floats"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Memory Views"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-20. Changing the value of an array item by poking one of its bytes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = array('h', [-2, -1, 0, 1, 2])\n",
    "memv = memoryview(numbers)\n",
    "len(memv)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "memv[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[254, 255, 255, 255, 0, 0, 1, 0, 2, 0]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "memv_oct = memv.cast('B')\n",
    "memv_oct.tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array('h', [-2, -1, 1024, 1, 2])"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "memv_oct[5] = 4\n",
    "numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### NumPy and SciPy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-21. Basic operations with rows and columns in a numpy.ndarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11])"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "a = np.arange(12)\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "numpy.ndarray"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(12,)"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0,  1,  2,  3],\n",
       "       [ 4,  5,  6,  7],\n",
       "       [ 8,  9, 10, 11]])"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.shape = 3, 4\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 8,  9, 10, 11])"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a[2, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 5, 9])"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a[:, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0,  4,  8],\n",
       "       [ 1,  5,  9],\n",
       "       [ 2,  6, 10],\n",
       "       [ 3,  7, 11]])"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.transpose()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-22. Loading, saving, and vectorized operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('floats-1M-lines.txt', 'wt') as fp:\n",
    "    for _ in range(1_000_000):\n",
    "        fp.write(f'{random()}\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "floats = np.loadtxt('floats-1M-lines.txt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.29150425, 0.33893554, 0.08112756])"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "floats[-3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.14575213, 0.16946777, 0.04056378])"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "floats *= .5\n",
    "floats[-3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from time import perf_counter as pc\n",
    "\n",
    "t0 = pc()\n",
    "floats /= 3\n",
    "(pc() - t0) < 0.01"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.save('floats-1M', floats)\n",
    "floats2 = np.load('floats-1M.npy', 'r+')\n",
    "floats2 *= 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "memmap([0.29150425, 0.33893554, 0.08112756])"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "floats2[-3:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Deques and Other Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2-22. Working with a deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "\n",
    "dq = collections.deque(range(10), maxlen=10)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6])"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.rotate(3)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.rotate(-4)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9])"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.appendleft(-1)\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33])"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.extend([11, 22, 33])\n",
    "dq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([40, 30, 20, 10, 3, 4, 5, 6, 7, 8])"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dq.extendleft([10, 20, 30, 40])\n",
    "dq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Soapbox"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mixed bag lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [28, 14, '28', 5, '9', '1', 0, 6, '23', 19]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TypeError(\"'<' not supported between instances of 'str' and 'int'\")\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    sorted(l)\n",
    "except TypeError as e:\n",
    "    print(repr(e))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Key is Brilliant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, '1', 5, 6, '9', 14, 19, '23', 28, '28']"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [28, 14, '28', 5, '9', '1', 0, 6, '23', 19]\n",
    "\n",
    "sorted(l, key=int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, '1', 14, 19, '23', 28, '28', 5, 6, '9']"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(l, key=str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}