Part1聊聊Python序列類型的本質(zhì)

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

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

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

1、電腦記憶體中的陣列結(jié)構(gòu)

電腦體系結(jié)構(gòu)中，我們知道電腦主存由位元資訊組成，這些位元通常被歸類成更大的單元，這些單元?jiǎng)t取決於精準(zhǔn)的系統(tǒng)架構(gòu)。一個(gè)典型的單元就是一個(gè)位元組，相當(dāng)於8位元。

電腦系統(tǒng)擁有龐大數(shù)量的儲(chǔ)存字節(jié)，那麼如何才能找到我們的資訊存在哪個(gè)位元組呢？答案就是大家平時(shí)熟知的?儲(chǔ)存地址?。基於儲(chǔ)存位址，主記憶體中的任何位元組都能被有效的存取。實(shí)際上，每個(gè)儲(chǔ)存位元組都和一個(gè)作為其位址的唯一二進(jìn)位數(shù)字相關(guān)聯(lián)。如下圖中，每個(gè)位元組均被指定了儲(chǔ)存位址：

一般來說，程式語言記錄標(biāo)識(shí)符和其關(guān)聯(lián)值所儲(chǔ)存的位址之間的關(guān)係。例如，當(dāng)我們宣告標(biāo)識(shí)符 x 就有可能和記憶體中的某一值相關(guān)聯(lián)，而標(biāo)識(shí)符 y就可能和其他的值相關(guān)聯(lián)。一組相關(guān)的變數(shù)能夠一個(gè)接一個(gè)地儲(chǔ)存在電腦記憶體的一塊連續(xù)區(qū)域內(nèi)。我們將這種方式稱為?數(shù)組。

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

我們可以看到，陣列可以儲(chǔ)存多個(gè)值而無需建構(gòu)具有特定索引的多個(gè)變數(shù)來指定其中的每個(gè)項(xiàng)目，並且?guī)缀踉谒谐淌秸Z言（例如C、Java、C#、C ）中使用，但Python更具有優(yōu)勢。 Python在建立清單時(shí)，熟悉的讀者可能知道，不需要預(yù)先定義數(shù)組或列表的大小，相反，在Python中，列表具有動(dòng)態(tài)性質(zhì)，我們可以不斷的往列表中添加我們想要的資料元素。接下來，讓我們來看看Python清單的知識(shí)（已經(jīng)熟悉的讀者可以快速瀏覽或跳過）。

2、Python列表

Python列表的操作

• #創(chuàng)建列表的語法格式：

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

• 建立元組的語法格式：

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

元組比列表的記憶體空間利用率更高，因?yàn)樵M是固定不變的，所以沒有必要建立擁有剩餘空間的動(dòng)態(tài)數(shù)組。

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

>>> test_list = []# 創(chuàng)建名為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")# 向列表中指定位置中插入一個(gè)元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure']
>>> test_list.append(2020)# 向列表末尾增加一個(gè)元素
>>> 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')# 查找某個(gè)元素的索引值
0
>>> test_list.index('hello')# 如果查找某個(gè)元素不在列表中，返回ValueError錯(cuò)誤
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()# 反轉(zhuǎn)整個(gè)列表
>>> test_list
['DataStructure', 'easy learning', 2019, 'Array', 'Hello']
>>> test_list.clear()# 清空列表
>>> test_list
[]

我們看上面的程式碼，可以看到list的相關(guān)操作－增刪改查，已經(jīng)很強(qiáng)大了，還有一些內(nèi)建方法這裡並沒有做展示，留給讀者自己去發(fā)現(xiàn)並體驗(yàn)。

Python列表的記憶體分配背後的基礎(chǔ)知識(shí)

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

前往Jupyter notebook進(jìn)行練習(xí)?；蚴褂米约哼x擇的任何編輯器或開發(fā)環(huán)境。複製下面編寫的程式碼。

# 導(dǎo)入sys模塊能方便我們使用gestsizeof函數(shù)
import sys

# set n
n = 20
# set empty list
list = []
for i in range(n):
a = len(list)
# 調(diào)用getsizeof函數(shù)用于給出Python中存儲(chǔ)對(duì)象的真實(shí)字節(jié)數(shù)
b = sys.getsizeof(list)
print('Length:{0:3d}; Size of bytes:{1:4d}'.format(a, b))
# Increase length by one
list.append(n)

運(yùn)行程式碼，可以看到以下輸出：

#現(xiàn)在，隨著我們?cè)黾忧鍐蔚拈L度，位元組也增加了。我們分析一下，Length：1

位置的元素填入列表時(shí)，當(dāng)位元組數(shù)從64跳到96，增加了32個(gè)位元組。因?yàn)楸緦?shí)驗(yàn)是在64位元機(jī)器上運(yùn)行的，這顯示每個(gè)記憶體位址是64位元（即8個(gè)位元組）。增加的32個(gè)位元組即為分配的用於儲(chǔ)存4個(gè)物件引用的陣列大小。當(dāng)增加第2個(gè)、第3個(gè)或第4個(gè)元素時(shí)，記憶體佔(zhàn)用並沒有改變。位元組數(shù)96能夠提供4個(gè)物件的引用。

96 = 64 8 times 4

當(dāng)Length:10

時(shí)，字節(jié)數(shù)從一開始的64跳到192，能存下16個(gè)對(duì)象的引用，

192 = 64 + 8 times 16

一直到Length: 17

后又開始跳轉(zhuǎn)，所以理論上264個(gè)字節(jié)數(shù)應(yīng)該可以存下25個(gè)對(duì)象

264 = 64 + 8 times 25

但因?yàn)槲覀冊(cè)诖a中設(shè)置n=20，然后程序就終止了。

我們可以看到Python內(nèi)置的list類足夠智能，知道當(dāng)需要額外的空間來分配數(shù)據(jù)時(shí)，它會(huì)為它們提供額外的大小，那么這究竟是如何被實(shí)現(xiàn)的呢？

好吧，答案是動(dòng)態(tài)數(shù)組。說到這里，不知道大家學(xué)Python列表的時(shí)候是不是這樣想的——列表很簡單嘛，就是list()類、用中括號(hào)[]括起來，然后指導(dǎo)書籍或文檔上的各類方法append、insert、pop...在各種IDE一頓操作過后，是的我覺得我學(xué)會(huì)了。

但其實(shí)背后的原理真的很不簡單，比如我舉個(gè)例子：A[-1]這個(gè)操作怎么實(shí)現(xiàn)？列表切片功能怎么實(shí)現(xiàn)？如何自己寫pop()默認(rèn)刪除列表最右邊的元素(popleft刪除最左邊簡單)？...這些功能用起來爽，但真的自己實(shí)現(xiàn)太難了（我也還在學(xué)習(xí)中，大佬們請(qǐng)輕噴！）如果我們能學(xué)習(xí)并理解，肯定可以加強(qiáng)我們對(duì)數(shù)組這一結(jié)構(gòu)的理解。

3、動(dòng)態(tài)數(shù)組

什么是動(dòng)態(tài)數(shù)組

動(dòng)態(tài)數(shù)組是內(nèi)存的連續(xù)區(qū)域，其大小隨著插入新數(shù)據(jù)而動(dòng)態(tài)增長。在靜態(tài)數(shù)組中，我們需要在分配時(shí)指定大小。在定義數(shù)組的時(shí)候，其實(shí)計(jì)算機(jī)已經(jīng)幫我們分配好了內(nèi)存來存儲(chǔ)，實(shí)際上我們不能擴(kuò)展數(shù)組，因?yàn)樗拇笮∈枪潭ǖ?。比如：我們分配一個(gè)大小為10的數(shù)組，則不能插入超過10個(gè)項(xiàng)目。

但是動(dòng)態(tài)數(shù)組會(huì)在需要的時(shí)候自動(dòng)調(diào)整其大小。這一點(diǎn)有點(diǎn)像我們使用的Python列表，可以存儲(chǔ)任意數(shù)量的項(xiàng)目，而無需在分配時(shí)指定大小。

所以實(shí)現(xiàn)一個(gè)動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)的關(guān)鍵是——如何擴(kuò)展數(shù)組？當(dāng)列表list1的大小已滿時(shí)，而此時(shí)有新的元素要添加進(jìn)列表，我們會(huì)執(zhí)行一下步驟來克服其大小限制的缺點(diǎn)：

1. 分配具有更大容量的新數(shù)組list2
2. 設(shè)置list2[i] = list1[i] (i=0,1,2,...，n-1)，其中n是該項(xiàng)目的當(dāng)前編號(hào)
3. 設(shè)置list1 = list2，也就是說，list2正在作為新的數(shù)組來引用我們的新列表。
4. 然后，只要將新的元素插入（添加）到我們的列表list1即可。

接下來要思考的問題是，新數(shù)組應(yīng)該多大？通常我們得做法是：新數(shù)組的大小是已滿的舊數(shù)組的2倍。我們將在Python中編程實(shí)現(xiàn)動(dòng)態(tài)數(shù)組的概念，并創(chuàng)建一個(gè)簡單的代碼，很多功能不及Python強(qiáng)大。

實(shí)現(xiàn)動(dòng)態(tài)數(shù)組的Python代碼

在Python中，我們利用ctypes的內(nèi)置庫來創(chuàng)建自己的動(dòng)態(tài)數(shù)組類，因?yàn)閏types模塊提供對(duì)原始數(shù)組的支持，為了更快的對(duì)數(shù)組進(jìn)行學(xué)習(xí)，所以對(duì)ctypes的知識(shí)可以查看官方文檔進(jìn)行學(xué)習(xí)。關(guān)于Python的公有方法與私有方法，我們?cè)诜椒Q前使用雙下劃線**__**使其保持隱藏狀態(tài)，代碼如下：

# -*- 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()

測試動(dòng)態(tài)數(shù)組Python代碼

上面我們已經(jīng)實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)數(shù)組的類，相信都很激動(dòng)，接下來讓我們來測試一下，看能不能成功呢？在同一個(gè)文件下，寫的測試代碼如下：

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()

測試結(jié)果

激動(dòng)人心的時(shí)刻揭曉，測試結(jié)果如下。請(qǐng)結(jié)合測試代碼和數(shù)組的結(jié)構(gòu)進(jìn)行理解，如果由疏漏，歡迎大家指出。

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總結(jié)

通過以上的介紹，我們知道了數(shù)組存在靜態(tài)和動(dòng)態(tài)類型。而在本博客中，我們著重介紹了什么是動(dòng)態(tài)數(shù)組，并通過Python代碼進(jìn)行實(shí)現(xiàn)。希望你能從此以復(fù)雜的方式學(xué)會(huì)數(shù)組?？偨Y(jié)發(fā)言，其實(shí)越是簡單的操作，背后實(shí)現(xiàn)原理可能很復(fù)雜。

以上是用Python實(shí)現(xiàn)動(dòng)態(tài)數(shù)組：從入門到精通的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！