用Python實現動態數組：從入門到精通

Part1聊聊Python序列類型的本質

在本部落格中，我們來聊聊探討Python的各種「序列」類，內建的三大常用資料結構—清單類別（list） 、元組類別（tuple）和字串類別（str）的本質。

不知道你發現沒有，這些類別都有一個很明顯的共性，都可以用來保存多個資料元素，最主要的功能是：每個類別都支援下標（索引）存取該序列的元素，例如使用語法 Seq[i]。其實上面每個類別都是使用 數組 這種簡單的資料結構表示。

但熟悉Python的讀者可能知道這3種資料結構又有一些不同：例如元組和字串是不能修改的，列表可以修改。

1、電腦記憶體中的陣列結構

電腦體系結構中，我們知道電腦主存由位元資訊組成，這些位元通常被歸類成更大的單元，這些單元則取決於精準的系統架構。一個典型的單元就是一個位元組，相當於8位元。

電腦系統擁有龐大數量的儲存字節，那麼如何才能找到我們的資訊存在哪個位元組呢？答案就是大家平時熟知的 儲存地址 。基於儲存位址，主記憶體中的任何位元組都能被有效的存取。實際上，每個儲存位元組都和一個作為其位址的唯一二進位數字相關聯。如下圖中，每個位元組均被指定了儲存位址：

一般來說，程式語言記錄標識符和其關聯值所儲存的位址之間的關係。例如，當我們宣告標識符 x 就有可能和記憶體中的某一值相關聯，而標識符 y就可能和其他的值相關聯。一組相關的變數能夠一個接一個地儲存在電腦記憶體的一塊連續區域內。我們將這種方式稱為 數組。

我們來看Python中的例子，一個文字字串 HELLO 是以一列有序字元的形式儲存的，假定該字串的每個Unicode字元需要兩個位元組的儲存空間。最下面的數字就是該字串的索引值。

我們可以看到，陣列可以儲存多個值而無需建構具有特定索引的多個變數來指定其中的每個項目，並且幾乎在所有程式語言（例如C、Java、C#、C ）中使用，但Python更具有優勢。 Python在建立清單時，熟悉的讀者可能知道，不需要預先定義數組或列表的大小，相反，在Python中，列表具有動態性質，我們可以不斷的往列表中添加我們想要的資料元素。接下來，讓我們來看看Python清單的知識（已經熟悉的讀者可以快速瀏覽或跳過）。

2、Python列表

Python列表的操作

• #創建列表的語法格式：

[ele1, ele2, ele3 , ele4, ...]

• 建立元組的語法格式：

#(ele1, ele2, ele3, ele4, ...)

元組比列表的記憶體空間利用率更高，因為元組是固定不變的，所以沒有必要建立擁有剩餘空間的動態數組。

我們先在Python的IDE中建立一個列表，然後大致了解一下列表部分內建操作，我們先創建了一個名為test_list的列表，然後修改（插入或刪除）元素，反轉或清空列表，具體如下：

>>> test_list = []# 创建名为test_list的空列表
>>> test_list.append("Hello")
>>> test_list.append("World")
>>> test_list
['Hello', 'World']
>>> test_list = ["Hello", "Array", 2019, "easy learning", "DataStructure"]# 重新给test_list赋值
>>> len(test_list)# 求列表的长度
5
>>> test_list[2] = 1024# 修改列表元素
>>> test_list
['Hello', 'Array', 1024, 'easy learning', 'DataStructure']
>>>
>>> test_list.insert(1, "I love")# 向列表中指定位置中插入一个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure']
>>> test_list.append(2020)# 向列表末尾增加一个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure', 2020]
>>>
>>> test_list.pop(1)# 删除指定位置的元素
'I love'
>>> test_list.remove(2020)# 删除指定元素
>>> 
>>> test_list.index('Hello')# 查找某个元素的索引值
0
>>> test_list.index('hello')# 如果查找某个元素不在列表中，返回ValueError错误
Traceback (most recent call last):
File "<pyshell#11>", line 1, in <module>
test_list.index('hello')
ValueError: 'hello' is not in list
>>> 
>>> test_list.reverse()# 反转整个列表
>>> test_list
['DataStructure', 'easy learning', 2019, 'Array', 'Hello']
>>> test_list.clear()# 清空列表
>>> test_list
[]

我們看上面的程式碼，可以看到list的相關操作－增刪改查，已經很強大了，還有一些內建方法這裡並沒有做展示，留給讀者自己去發現並體驗。

Python列表的記憶體分配背後的基礎知識

因此，讓我們透過編碼實踐以及記憶體中保存的陣列的實際大小與給定大小之間的關係來查看這種額外的空間演示。

前往Jupyter notebook進行練習。或使用自己選擇的任何編輯器或開發環境。複製下面編寫的程式碼。

# 导入sys模块能方便我们使用gestsizeof函数
import sys

# set n
n = 20
# set empty list
list = []
for i in range(n):
a = len(list)
# 调用getsizeof函数用于给出Python中存储对象的真实字节数
b = sys.getsizeof(list)
print('Length:{0:3d}; Size of bytes:{1:4d}'.format(a, b))
# Increase length by one
list.append(n)

運行程式碼，可以看到以下輸出：

#現在，隨著我們增加清單的長度，位元組也增加了。我們分析一下，Length：1

位置的元素填入列表時，當位元組數從64跳到96，增加了32個位元組。因為本實驗是在64位元機器上運行的，這顯示每個記憶體位址是64位元（即8個位元組）。增加的32個位元組即為分配的用於儲存4個物件引用的陣列大小。當增加第2個、第3個或第4個元素時，記憶體佔用並沒有改變。位元組數96能夠提供4個物件的引用。

96 = 64 8 times 4

當Length:10

时，字节数从一开始的64跳到192，能存下16个对象的引用，

192 = 64 + 8 times 16

一直到Length: 17

后又开始跳转，所以理论上264个字节数应该可以存下25个对象

264 = 64 + 8 times 25

但因为我们在代码中设置n=20，然后程序就终止了。

我们可以看到Python内置的list类足够智能，知道当需要额外的空间来分配数据时，它会为它们提供额外的大小，那么这究竟是如何被实现的呢？

好吧，答案是动态数组。说到这里，不知道大家学Python列表的时候是不是这样想的——列表很简单嘛，就是list()类、用中括号[]括起来，然后指导书籍或文档上的各类方法append、insert、pop...在各种IDE一顿操作过后，是的我觉得我学会了。

但其实背后的原理真的很不简单，比如我举个例子：A[-1]这个操作怎么实现？列表切片功能怎么实现？如何自己写pop()默认删除列表最右边的元素(popleft删除最左边简单)？...这些功能用起来爽，但真的自己实现太难了（我也还在学习中，大佬们请轻喷！）如果我们能学习并理解，肯定可以加强我们对数组这一结构的理解。

3、动态数组

什么是动态数组

动态数组是内存的连续区域，其大小随着插入新数据而动态增长。在静态数组中，我们需要在分配时指定大小。在定义数组的时候，其实计算机已经帮我们分配好了内存来存储，实际上我们不能扩展数组，因为它的大小是固定的。比如：我们分配一个大小为10的数组，则不能插入超过10个项目。

但是动态数组会在需要的时候自动调整其大小。这一点有点像我们使用的Python列表，可以存储任意数量的项目，而无需在分配时指定大小。

所以实现一个动态数组的实现的关键是——如何扩展数组？当列表list1的大小已满时，而此时有新的元素要添加进列表，我们会执行一下步骤来克服其大小限制的缺点：

1. 分配具有更大容量的新数组list2
2. 设置list2[i] = list1[i] (i=0,1,2,...，n-1)，其中n是该项目的当前编号
3. 设置list1 = list2，也就是说，list2正在作为新的数组来引用我们的新列表。
4. 然后，只要将新的元素插入（添加）到我们的列表list1即可。

接下来要思考的问题是，新数组应该多大？通常我们得做法是：新数组的大小是已满的旧数组的2倍。我们将在Python中编程实现动态数组的概念，并创建一个简单的代码，很多功能不及Python强大。

实现动态数组的Python代码

在Python中，我们利用ctypes的内置库来创建自己的动态数组类，因为ctypes模块提供对原始数组的支持，为了更快的对数组进行学习，所以对ctypes的知识可以查看官方文档进行学习。关于Python的公有方法与私有方法，我们在方法名称前使用双下划线**__**使其保持隐藏状态，代码如下：

# -*- coding: utf-8 -*-
# @Time: 2019-11-01 17:10
# @Author: yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File: DynamicArray.py
# @Software: PyCharm

import ctypes


class DynamicArray:
"""A dynamic array class akin to a simplified Python list."""

def __init__(self):
"""Create an empty array."""
self.n = 0 # count actual elements
self.capacity = 1# default array capacity
self.A = self._make_array(self.capacity)# low-level array

def is_empty(self):
""" Return True if array is empty"""
return self.n == 0

def __len__(self):
"""Return numbers of elements stored in the array."""
return self.n

def __getitem__(self, i):
"""Return element at index i."""
if not 0 <= i < self.n:
# Check it i index is in bounds of array
raise ValueError('invalid index')
return self.A[i]

def append(self, obj):
"""Add object to end of the array."""
if self.n == self.capacity:
# Double capacity if not enough room
self._resize(2 * self.capacity)
self.A[self.n] = obj# Set self.n index to obj
self.n += 1

def _resize(self, c):
"""Resize internal array to capacity c."""
B = self._make_array(c) # New bigger array
for k in range(self.n):# Reference all existing values
B[k] = self.A[k]
self.A = B# Call A the new bigger array
self.capacity = c # Reset the capacity

@staticmethod
def _make_array(c):
"""Return new array with capacity c."""
return (c * ctypes.py_object)()

def insert(self, k, value):
"""Insert value at position k."""
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

def pop(self, index=0):
"""Remove item at index (default first)."""
if index >= self.n or index < 0:
raise ValueError('invalid index')
for i in range(index, self.n-1):
self.A[i] = self.A[i+1]
self.A[self.n - 1] = None
self.n -= 1

def remove(self, value):
"""Remove the first occurrence of a value in the array."""
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
return
raise ValueError('value not found')

def _print(self):
"""Print the array."""
for i in range(self.n):
print(self.A[i], end=' ')
print()

测试动态数组Python代码

上面我们已经实现了一个动态数组的类，相信都很激动，接下来让我们来测试一下，看能不能成功呢？在同一个文件下，写的测试代码如下：

def main():
# Instantiate
mylist = DynamicArray()

# Append new element
mylist.append(10)
mylist.append(9)
mylist.append(8)
# Insert new element in given position
mylist.insert(1, 1024)
mylist.insert(2, 2019)
# Check length
print('The array length is: ', mylist.__len__())
# Print the array
print('Print the array：')
mylist._print()
# Index
print('The element at index 1 is :', mylist[1])
# Remove element
print('Remove 2019 in array:')
mylist.remove(2019)
mylist._print()
# Pop element in given position
print('Pop pos 2 in array:')
# mylist.pop()
mylist.pop(2)
mylist._print()


if __name__ == '__main__':
main()

测试结果

激动人心的时刻揭晓，测试结果如下。请结合测试代码和数组的结构进行理解，如果由疏漏，欢迎大家指出。

The array length is:5
Print the array：
10 1024 2019 9 8 
The element at index 1 is : 1024
Remove 2019 in array:
10 1024 9 8 
Pop pos 2 in array:
10 1024 8 

Part2总结

通过以上的介绍，我们知道了数组存在静态和动态类型。而在本博客中，我们着重介绍了什么是动态数组，并通过Python代码进行实现。希望你能从此以复杂的方式学会数组。总结发言，其实越是简单的操作，背后实现原理可能很复杂。

以上是用Python實現動態數組：從入門到精通的詳細內容。更多資訊請關注PHP中文網其他相關文章！