Code_Unit_5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第5章 基于数组的序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码段5-1 在Python中，探究列表长度和底层大小关系的试验"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length:   0; Size in bytes:   56\n",
      "Length:   1; Size in bytes:   88\n",
      "Length:   2; Size in bytes:   88\n",
      "Length:   3; Size in bytes:   88\n",
      "Length:   4; Size in bytes:   88\n",
      "Length:   5; Size in bytes:  120\n",
      "Length:   6; Size in bytes:  120\n",
      "Length:   7; Size in bytes:  120\n",
      "Length:   8; Size in bytes:  120\n",
      "Length:   9; Size in bytes:  184\n",
      "Length:  10; Size in bytes:  184\n",
      "Length:  11; Size in bytes:  184\n",
      "Length:  12; Size in bytes:  184\n",
      "Length:  13; Size in bytes:  184\n",
      "Length:  14; Size in bytes:  184\n",
      "Length:  15; Size in bytes:  184\n",
      "Length:  16; Size in bytes:  184\n",
      "Length:  17; Size in bytes:  256\n",
      "Length:  18; Size in bytes:  256\n",
      "Length:  19; Size in bytes:  256\n",
      "Length:  20; Size in bytes:  256\n",
      "Length:  21; Size in bytes:  256\n",
      "Length:  22; Size in bytes:  256\n",
      "Length:  23; Size in bytes:  256\n",
      "Length:  24; Size in bytes:  256\n",
      "Length:  25; Size in bytes:  256\n",
      "Length:  26; Size in bytes:  336\n",
      "Length:  27; Size in bytes:  336\n",
      "Length:  28; Size in bytes:  336\n",
      "Length:  29; Size in bytes:  336\n",
      "Length:  30; Size in bytes:  336\n",
      "Length:  31; Size in bytes:  336\n",
      "Length:  32; Size in bytes:  336\n",
      "Length:  33; Size in bytes:  336\n",
      "Length:  34; Size in bytes:  336\n",
      "Length:  35; Size in bytes:  336\n",
      "Length:  36; Size in bytes:  424\n",
      "Length:  37; Size in bytes:  424\n",
      "Length:  38; Size in bytes:  424\n",
      "Length:  39; Size in bytes:  424\n",
      "Length:  40; Size in bytes:  424\n",
      "Length:  41; Size in bytes:  424\n",
      "Length:  42; Size in bytes:  424\n",
      "Length:  43; Size in bytes:  424\n",
      "Length:  44; Size in bytes:  424\n",
      "Length:  45; Size in bytes:  424\n",
      "Length:  46; Size in bytes:  424\n",
      "Length:  47; Size in bytes:  520\n",
      "Length:  48; Size in bytes:  520\n",
      "Length:  49; Size in bytes:  520\n",
      "Length:  50; Size in bytes:  520\n",
      "Length:  51; Size in bytes:  520\n",
      "Length:  52; Size in bytes:  520\n",
      "Length:  53; Size in bytes:  520\n",
      "Length:  54; Size in bytes:  520\n",
      "Length:  55; Size in bytes:  520\n",
      "Length:  56; Size in bytes:  520\n",
      "Length:  57; Size in bytes:  520\n",
      "Length:  58; Size in bytes:  520\n",
      "Length:  59; Size in bytes:  632\n",
      "Length:  60; Size in bytes:  632\n",
      "Length:  61; Size in bytes:  632\n",
      "Length:  62; Size in bytes:  632\n",
      "Length:  63; Size in bytes:  632\n",
      "Length:  64; Size in bytes:  632\n",
      "Length:  65; Size in bytes:  632\n",
      "Length:  66; Size in bytes:  632\n",
      "Length:  67; Size in bytes:  632\n",
      "Length:  68; Size in bytes:  632\n",
      "Length:  69; Size in bytes:  632\n",
      "Length:  70; Size in bytes:  632\n",
      "Length:  71; Size in bytes:  632\n",
      "Length:  72; Size in bytes:  632\n",
      "Length:  73; Size in bytes:  760\n",
      "Length:  74; Size in bytes:  760\n",
      "Length:  75; Size in bytes:  760\n",
      "Length:  76; Size in bytes:  760\n",
      "Length:  77; Size in bytes:  760\n",
      "Length:  78; Size in bytes:  760\n",
      "Length:  79; Size in bytes:  760\n",
      "Length:  80; Size in bytes:  760\n",
      "Length:  81; Size in bytes:  760\n",
      "Length:  82; Size in bytes:  760\n",
      "Length:  83; Size in bytes:  760\n",
      "Length:  84; Size in bytes:  760\n",
      "Length:  85; Size in bytes:  760\n",
      "Length:  86; Size in bytes:  760\n",
      "Length:  87; Size in bytes:  760\n",
      "Length:  88; Size in bytes:  760\n",
      "Length:  89; Size in bytes:  904\n",
      "Length:  90; Size in bytes:  904\n",
      "Length:  91; Size in bytes:  904\n",
      "Length:  92; Size in bytes:  904\n",
      "Length:  93; Size in bytes:  904\n",
      "Length:  94; Size in bytes:  904\n",
      "Length:  95; Size in bytes:  904\n",
      "Length:  96; Size in bytes:  904\n",
      "Length:  97; Size in bytes:  904\n",
      "Length:  98; Size in bytes:  904\n",
      "Length:  99; Size in bytes:  904\n"
     ]
    }
   ],
   "source": [
    "import sys                     # provides getsizeof function\n",
    "data = []\n",
    "n = 100\n",
    "for k in range(n):             # NOTE: must fix choice of n\n",
    "    a = len(data)              # number of elements\n",
    "    b = sys.getsizeof(data)    # actual size in bytes\n",
    "    print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a, b))\n",
    "    data.append(None)          # increse length by one"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码段5-3 使用ctypes模块提供的原始数组实现DynamicArray类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ctypes     # provides low-level arrays\n",
    "\n",
    "class DynamicArray:\n",
    "    \"\"\"A dynamic array class to a simplified Python list.\"\"\"\n",
    "    \n",
    "    def __init__(self):\n",
    "        \"\"\"Create an empty array.\"\"\"\n",
    "        self._n = 0                                   # count actual elements\n",
    "        self._capacity = 1                            # default array capacity\n",
    "        self._A = self._make_array(self._capacity)    # low-level array\n",
    "    \n",
    "    def __len__(self):\n",
    "        \"\"\"Return number of elements stored in the array.\"\"\"\n",
    "        return self._n\n",
    "    \n",
    "    def __getitem__(self, k):\n",
    "        \"\"\"Return element at index k.\"\"\"\n",
    "        if not 0 <= k < self._n:\n",
    "            raise IndexError('invalid index')\n",
    "        return self._A[k]                             # retrieve from array\n",
    "    \n",
    "    def append(self, obj):\n",
    "        \"\"\"Add object to end of the array.\"\"\"\n",
    "        if self._n == self._capacity:                 # not enough room\n",
    "            self._resize(2 * self._capacity)          # so double capacity\n",
    "        self._A[self._n] = obj\n",
    "        self._n += 1\n",
    "    \n",
    "    def _resize(self, c):                             # nonpublic utitity\n",
    "        \"\"\"Resize internal array to capacity c.\"\"\"\n",
    "        B = self._make_array(c)                       # new bigger array\n",
    "        for k in range(self._n):                      # for each existing value\n",
    "            B[k] = self._A[k]\n",
    "        self._A = B                                   # use the bigger array\n",
    "        self._capacity = c\n",
    "    \n",
    "    def _make_array(self, c):                         # nonpublic utitity\n",
    "        \"\"\"Return new array with capacity c.\"\"\"\n",
    "        return (c*ctypes.py_object)()       \n",
    "    # see ctypes documention"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "temp = [i for i in range(10, 2, -1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 9, 8, 7, 6, 5, 4, 3]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "temp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码段5-4 测量Python列表类增添操作的摊销花费"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import time          # import time function from time module\n",
    "def compute_average(n):\n",
    "    \"\"\"Perform n append to an empty list and return average time elapsed.\"\"\"\n",
    "    data = []\n",
    "    start = time()             # record the start time (in seconds)\n",
    "    for k in range(n):\n",
    "        data.append(None)\n",
    "    end = time()               # record the end time (in seconds)\n",
    "    return (end-start) / n     # compute average per operation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码段5-5 DynamicArray类insert方法的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert(self, k, value):\n",
    "    \"\"\"Insert value ad index k, shifting subsequent values rightward.\"\"\"\n",
    "    # (for simplicity, we assumw 0 <= k <= n in this version)\n",
    "    if self._n == self._capacity:           # not enough room\n",
    "        self._resize(2 * self._capacity)    # so double capacity\n",
    "    for j in range(self._n, k, -1):         # shift rightmost first\n",
    "        self._A[j] = self._A[j-1]\n",
    "    self._A[k] = value                      # store newest element\n",
    "    self._n += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码段5-6 对DynamicArray类的remove方法的一种实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def remove(self, value):\n",
    "    \"\"\"Remove first occurrent of value (or raise ValueError).\"\"\"\n",
    "    for k in range(self._n):\n",
    "        if self._A[k] == value:    # found a match!\n",
    "            for j in range(k, self._n - 1):    # shift others to fill gap\n",
    "                self._A[j] = self._A[j+1]\n",
    "            self._A[self._n-1] = None    # help garbage collection\n",
    "            self._n -= 1                 # we have one less item\n",
    "            return                       # exit immediately\n",
    "    raise ValueError('value not found')  # only reached if no match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "for i in range(10, 0, -1):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码段5-7 一个简单GameEntry类的Python代码。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GameEntry:\n",
    "    \"\"\"Represents one entry of a list of high scores.\"\"\"\n",
    "    def __init__(self, name, score):\n",
    "        self.__name = name\n",
    "        self._score = score\n",
    "    \n",
    "    def get_name(self):\n",
    "        return self._name\n",
    "    \n",
    "    def get_score(self):\n",
    "        return self._score\n",
    "    \n",
    "    def __str__(self):\n",
    "        return '({0}, {1})'.format(self._name, self._score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码段5-9 在列表中执行插入排序的Python代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(A):\n",
    "    \"\"\"Sort list of comparable elements into nondecreasing order.\"\"\"\n",
    "    for k in range(1, len(A)):           # from 1 to n-1\n",
    "        cur = A[k]                       # current element to be inserted\n",
    "        j = k                            # find current index j for current\n",
    "        while j > 0 and A[j-1] > cur:    # element A[j-1] must be after current\n",
    "            A[j] = A[j-1]\n",
    "            j -= 1\n",
    "        A[j] = cur                       # cur is now in the right place"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构造多维数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构造c行r列的二维数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = 10\n",
    "r = 10\n",
    "data = [[0] * c for j in range(r)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]\n"
     ]
    }
   ],
   "source": [
    "print(data)"
   ]
  },
  {
   "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.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}