一组相关变量能够一个接一个地存储在计算机存储器的一块连续区域内，我们将这样的表示法称为数组。对于大多数计算机系统，Python内部用16位表示每个Unicode字符，即2个字节。因此，一个6个字符的字符串 ，将会被存储在存储器的连续12个字节中。
虽然该字符串需要12个字节的存储空间，但我们仍把它描述为6字符数组。
Python使用数组内部存储机制，来表示一列或者元组实例。在最低层，存储的是一块连续的内存地址序列，这些地址指向一组元素序列。虽然单个元素的相对大小可能不同，但每个元素存储地址的位数是固定的。在这种情况下，Python可以通过索引值以常量时间访问元素列表或元组。

Python中的紧凑数组

在本小节的介绍中，我们强调字符串使用字符数组表示的（而不是用数组的引用)。我们将会谈到更直接的表示方式——紧凑数组，因为数组存储的是位，这些位表示原始数据。
Python提供了几种用于创建不同类型的紧凑数组的方法。
紧凑数组主要是通过一个名为array的模块提供支撑。该模块定义了一个类(也命名位array)，该类提供了紧凑存储原始数据类型的数组的方法。
array类的公共接口通常和python的list(列表)一致。然而，该类的构造函数需要以类型代码(type code)作为第一个参数，即一个字符，该字符表明要存入数组的数据类型。举一个实际的例子，类型代码'i'表明这是一个（有符号的）整型数组，通常表示每个元素至少16位，如：

primes = array('i',[2,3,5,7,11,13,17,19])

array模块不支持存储用户自定义数据类型的紧凑数组。这种结构的紧凑数组可以用一个名为ctypes的底层模块来创建。

动态数组和摊销

使用ctypes模块提供的原始数组实现动态数组类

import ctypes
class DynamicArray:
    def __init__(self):
        self._n = 0
        self._capacity = 1
        self._A = self._make_array(self._capacity)
        
    def __len__(self):
        return self._n
    
    def __getitem__(self, k):
        if not 0 <= k < self._n:
            raise IndexError('invalid index')
        
        return self._A[k]
    
    def append(self,obj):
        if self._n == self._capacity:
            self._resize(2*self._capacity)
            
        self._A[self._n] = obj
        self._n += 1
        
    def _resize(self,c):
        B = self._make_array(c)
        for k in range(self._n):
            B[k] = self._A[k]
            
        self._A = B
        self._capacity = c
    
    def _make_array(self,c):
        return (c*ctypes.py_object)()

动态数组的摊销分析

在此小节，我们对动态数组相关操作的运行时间做具体分析。
命题5-1：设S是一个由具有初始大小的动态数组实现的数组，实现策略为：当数组已满时，将此数组扩大为原来的两倍。S最初为空，对S连续执行n个增添操作的运行时间为O(n)。

Python序列类型的效率

列表类的nonmutating行为是由元组类所支持的。我们注意到元组比列表的内存利用率更高，因为元组是固定不变的，所以没必要创建拥有剩余空间的动态数组。

# DynamicArray 类insert 方法的实现
    def insert(self,k,value):
        if self._n == self._capacity:
            self._resize(2*self._capacity)
        for j in range(self._n,k,-1):
            self._A[j] = self._A[j-1]
        self._A[k] = value
        self._n += 1

循环过程中将索引n-1的引用复制到索引n内，将索引n-2的引用复制到索引n-1内，如此往复，知道将索引k的引用复制到索引k+1中。插入索引k内需要的总摊销时间为O(n-k+1)

# DynamicArray 类insert 方法的实现
    def remove(self,value):
        for k in range(self._n):
            if self._A[k] == value:
                for j in range(k,self._n,-1):
                    self._A[j] == self._A[j+1]
                self._A[self._n-1] = None
                self._n -= 1
        raise ValueError('value not found')

Python的字符串类

在Python中，字符串是非常重要的。

# 组成字符串
document = 'dfgsgggggggfwserwsfsfsfws'
temp = []
for c in document:
    if c.isalpha():
        temp.append(c)
letters = ''.join(temp)

该方法能确保运行时间为O(n)。首先，我们注意到连续n次append调用共需要O(n)的运行时间，其运行时间可以根据此操作的摊销花费定义的出。
我们用列表推导式语法来创建临时表，而不是重复调用append方法，能够进一步提高实际执行速度。方案如下：

letters = ''.join([c for c in document if c.isalpha()])

使用基于数组的序列

为游戏储存高分

class GameEntry:
    def __init__(self,name,score):
        self._name = name
        self._score = score

    def get_name(self):
        return self._name

    def get_score(self):
        return self._score

    def __str__(self):
        return '({0},{1})'.format(self._name,self._sore)

class Scoreboard:
    def __init__(self,capacity=10):
        self._board = [None]*capacity
        self._n = 0

    def __getitem__(self, k):
        return self._board[k]

    def __str__(self):
        return '\n'.join(str(self._board[j])for j in range(self._n))

    def add(self,entry):
        score = entry.get_score()
        good = self._n < len(self._board)or score > self._board[-1].get_score()
        if good:
            if self._n < len(self._board):
                self._n += 1

            j = self._n -1
            while j >0 and self._board[j-1].get_score() < score:
                self._board[j] = self._board[j-1]
                j -= 1
            self._board[j] = entry

插入排序算法

def insertion_sort(A):
    for k in range(1,len(A)):
        cur = A[k]
        j = k
        while j > 0 and A[j-1] > cur:
            A[j] = A[j-1]
            j -= 1
        A[j] = cur