基于Python實現(xiàn)層次性數(shù)據(jù)和閉包性質(zhì)
緒論
序?qū)梢詾槲覀兲峁┯糜跇?gòu)造復合數(shù)據(jù)的基本“粘接劑”，鑒于Python中tuple中元素不可變的性質(zhì)，我們通過list來實現(xiàn)序?qū)Γ?code>[1, 2]。Python的PyListObject對象中實際是存放的是PyObject*指針， 所以可以將PyListObject視為vecter<PyObject*>。這是一種盒子與指針表示方式(list內(nèi)的元素表示為一個指向?qū)ο蠛凶拥闹羔?。對于[1, 2]，可將其視為以下結(jié)構(gòu)：
我們不僅可以用[]去組合起各種數(shù)值，也可以用它取組合起其它序?qū)?。這樣，序?qū)褪且环N通用的建筑砌塊，通過它可以構(gòu)造所有不同種類的數(shù)據(jù)結(jié)構(gòu)來。比如想組合數(shù)值1, 2, 3, 4，我們可以用[[1, 2], [3, 4]]的方式(下圖左)，也可以用[[1, [2, 3]], 4](下圖右)
可以構(gòu)建元素本身也是序?qū)Φ男驅(qū)Γ@種能力稱為[]的閉包性質(zhì)。注意，這里的閉包是來自抽象代數(shù)的術語（不是Python語法中那個閉包）。抽象代數(shù)中，如果將某個運算（操作）作用于某個集合的特定元素 ，產(chǎn)出的仍然是該集合的元素，則稱該集合元素在該運算之下封閉。我們這里說組合數(shù)據(jù)對象的操作滿足閉包性質(zhì)，指通過它組合起數(shù)據(jù)對象得到的結(jié)果本身還可以通過同樣的操作再進行組合。
閉包性質(zhì)可以使我們構(gòu)建層次性的結(jié)構(gòu)，這種結(jié)構(gòu)由一些部分構(gòu)成，而其中的各個部分又是由它們的部分構(gòu)成，并且可以繼續(xù)下去。下面我們介紹用序?qū)肀硎?strong>序列和樹。
1.序列的表示
利用序?qū)梢詨蛟斐龅囊活愑杏媒Y(jié)構(gòu)是序列——一批數(shù)據(jù)對象的有序匯集。利用序?qū)Ρ硎拘蛄械姆绞胶芏啵环N最直接的表示方式為[1, [2, [3, [4, None]]]]如下圖所示：
我們不妨將這種通過嵌套序?qū)π纬傻男蛄蟹Q為鏈表。因為Python本身不內(nèi)置鏈表結(jié)構(gòu)，我們不妨用序?qū)韺崿F(xiàn)鏈表：
class LinkedList():
def __init__(self, *items) -> None:
"""提供兩種初始化方式:序?qū)蚨鄠€元素
"""
if isinstance(items[0], list):
self.pair = items[0]
else:
self.pair = self._construct(*items)
def _construct(self, *items):
"""遞歸地構(gòu)造鏈表
"""
if items == ():
return None
else:
item, *rest = items
return [item, self._construct(*rest)]
def __repr__(self):
"""重寫打印函數(shù)
"""
return "-->".join(map(str, self._flatten(self.pair)))
def _flatten(self, pair):
"""遍歷鏈表，返回其一維展開
"""
if pair is None:
return []
else:
return [pair[0]] + self._flatten(pair[1])
@property
def head(self):
"""獲取鏈表頭部元素
"""
return self.pair[0]
@property
def rest(self):
"""獲取鏈表頭部元素之外的元素，并以鏈表形式返回
"""
if self.pair[1] is None:
return None
else:
return LinkedList(self.pair[1])這樣，我們就可以方便地構(gòu)造鏈表并將其打印輸出了：
print(LinkedList(1, 2, 3, 4)) # 1-->2-->3-->4
注意，None用于表示序?qū)Φ逆溄Y(jié)束。在語言設計上可能有以下爭論：None應該是個普通的名字嗎？None應該算是一個普通的名字嗎？None應該算是一個符號嗎？他應該算是一個空表嗎？在Python中，解決此問題的手段是將None的類型規(guī)定為<class 'NoneType'>，
表操作
利用序?qū)⒃氐男蛄斜硎緸殒湵碇?，我們就可以使用常?guī)的程序設計技術，通過獲取鏈表的head和rest的方式完成對鏈表的各種操作了。如下面的過程list-ref實際參數(shù)是一個表和一個數(shù)n，它返回這個表中的第n項：
def list_ref(items, n):
if n == 0:
return items.head
else:
return list_ref(items.rest, n-1)
print(list_ref(LinkedList(1, 4, 9, 16, 25), 3)) # 16length過程則用于返回表中的項數(shù)：
def length(items):
if items is None:
return 0
else:
return 1 + length(items.rest)
print(length(LinkedList(1, 3, 5, 7))) # 4
或者寫為迭代的形式(此處用尾遞歸的形式，即遞歸調(diào)用是整個函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達式的一部分時，這樣就無需保存返回值，可在常數(shù)空間內(nèi)執(zhí)行迭代型計算):
# 以迭代的方式計算lengths(尾遞歸)
def length(items):
def length_iter(a, count):
if a is None:
return count
else:
return length_iter(a.rest, count + 1)
return length_iter(items, 0)
print(length(LinkedList(1, 3, 5, 7))) # 4
當然， Python解釋器默認是不開啟尾遞歸優(yōu)化的，需要用其他黑魔法實現(xiàn)，參考《Python開啟尾遞歸優(yōu)化!》
還有一種常見操作是append，如對odds：[1, 3, 5, 7]、squares:[1, 4, 9, 16, 25]、append(odds, squares) 得[1 3 5 7 1 4 9 16 25]，append(squares, odds)得[1 4 9 16 25 1 3 5 7]，也可以通過遞歸實現(xiàn)：
def append(lk_list1, lk_list2):
if lk_list1 is None:
return lk_list2.pair
else:
return [lk_list1.head, append(lk_list1.rest, lk_list2)]
odds = LinkedList(1, 3, 5, 7)
squares = LinkedList(1, 4, 9, 16, 25)
print(LinkedList(append(odds, squares))) # 1-->3-->5-->7-->1-->4-->9-->16-->25
print(LinkedList(append(squares, odds))) # 1-->4-->9-->16-->25-->1-->3-->5-->7
對鏈表的映射
另外一個特別擁有用的操作時將某種操作應用于一個鏈表的所有元素，得到所有結(jié)果構(gòu)成的表。下面的過程將一個鏈表中的所有元素按給定因子做一次縮放：
def scale_list(items, factor):
if items is None:
return None
else:
return [items.head * factor, scale_list(items.rest, factor)]
print(LinkedList(scale_list(LinkedList(1, 2, 3, 4, 5), 10)))
# 10-->20-->30-->40-->50
我們可以抽象出這一具有一般性的想法，將其中的公共模式表述為一個高階函數(shù)(接收其它函數(shù)做為參數(shù))。
def my_map(proc, items):
if items is None:
return None
else:
return [proc(items.head), my_map(proc, items.rest)]
print(LinkedList(my_map(abs, LinkedList(-10, 2.5, -11.6, 17))))
# 10-->2.5-->11.6-->17
print(LinkedList(my_map(lambda x: x**2, LinkedList(1, 2, 3, 4, 5))))
# 1-->4-->9-->16-->25
這里的公共模式，其實就類似于設計模式中的模板方法，參見設計模式：模板方法。
現(xiàn)在我們可以用map給scale_list一個新定義：
def scale_list(items, factor):
return LinkedList(my_map(lambda x: x*factor, items))
print(scale_list(LinkedList(1, 2, 3, 4, 5), 10))
# 10-->20-->30-->40-->50
map是一種很重要的結(jié)構(gòu)，不僅因為它代表了一種公共模式，而且因為它建立起了一種處理表的高層抽象（與今日的Scala何其相似?。?，在老版本的scale_list中，程序的遞歸結(jié)構(gòu)將人的注意力吸引到對表中元素的逐個處理中。通過map定義的scale_list抑制了這種細節(jié)層面上的情況，強調(diào)的是從元素表到結(jié)果表的一個縮放變換。這兩種定義形式之間的差異，并不在于計算機會執(zhí)行不同的計算過程（其實不會），而在于我們對同一個過程的不同思考方式。 從作用上看，map幫我們建起了一層抽象屏障，將實現(xiàn)表轉(zhuǎn)換過程的實現(xiàn)，與與如何提取表中元素以及組合結(jié)果的細節(jié)隔離開。
2.層次性結(jié)構(gòu)
注意，由于下面由于我們會涉及更復雜的數(shù)據(jù)結(jié)構(gòu)，我們統(tǒng)一將序列就用Python內(nèi)置的列表表示。
我們下面來看元素本身也是序列的序列。比如我們可以認為[[1, 2], 3, 4]是將[1, 2]做為元素加入序列[3, 4]而得。這種表結(jié)構(gòu)可以看做是樹，即序列中的元素就是樹的分支，而那些本身也是序列的元素就形成了樹中的子樹：
遞歸是處理樹結(jié)構(gòu)的一種很自然的工具，因為我們常常可以將對于樹的操作歸結(jié)為對它們的分支的操作，再將這種操作歸結(jié)為對分支的分支的操作，如此下去，直至達到了樹的葉子。如類似2.2.1中用length統(tǒng)計序列長度，我們通過以下代碼統(tǒng)計樹葉數(shù)目：
def count_leaves(tree):
if not tree:
return 0
elif isinstance(tree, int):
return 1
else:
return count_leaves(tree[0]) + count_leaves(tree[1:])
tree = [[1, 2], 3, 4]
print(count_leaves(tree)) # 4
對樹的映射
map是處理序列的一種強有力抽象，與此類似，map與遞歸結(jié)合也是處理樹的一種強有力抽象。類似于2.2.1中用scale_list過程對序列元素進行縮放，我們也可以設計scale_tree過程，該過程以一個因子和一棵葉子為數(shù)值的樹作為參數(shù)，返回一顆具有同樣形狀的樹，該樹中的每個數(shù)值都乘以了這個因子：
def scale_tree(tree, factor):
if not tree:
return []
if isinstance(tree, int):
return tree * factor
else:
return [scale_tree(tree[0], factor)] + scale_tree(tree[1:], factor)
tree = [1, [2, [3, 4], 5], [6, 7]]
print(scale_tree(tree, 10))
# [10, [20, [30, 40], 50], [60, 70]]
實現(xiàn)scale_tree的另一種方法是將樹看成子樹的序列，并對它使用map。我們在這種序列上做映射，一次對各棵子樹做縮放，并返回結(jié)果的表。對于基礎情況，也就是當被處理的樹是樹葉時，就直接用因子去乘它：
def scale_tree(tree, factor):
return list(map(lambda sub_tree: scale_tree(sub_tree, factor)
if isinstance(sub_tree, list)
else sub_tree * factor, tree))
tree = [1, [2, [3, 4], 5], [6, 7]]
print(scale_tree(tree, 10))
# [10, [20, [30, 40], 50], [60, 70]]
此處的map我們直接采用Python語言內(nèi)置的map，當然也可以自己實現(xiàn)my_map，如下：
def my_map(proc, items):
if items == []:
return []
else:
return [proc(items[0])] + my_map(proc, items[1:])
3.序列做為一種約定的界面
數(shù)據(jù)抽象可以讓我們設計出不被數(shù)據(jù)表示細節(jié)糾纏的程序，使程序保持很好的彈性。在這一節(jié)里，我們將要介紹與數(shù)據(jù)結(jié)構(gòu)有關的另一種強有力的設計原理——使用約定的界面。
在1.3節(jié)中我們看到，通過實現(xiàn)為高階過程的程序抽象，可以讓我們抓住處理數(shù)值數(shù)據(jù)的一些程序模式。而在復合數(shù)據(jù)上工作做出類似的操作，則對我們操控數(shù)據(jù)結(jié)構(gòu)的方式有著深刻的依賴性。如考慮一個與2.2.2節(jié)中的count_leaves類似的過程，它以一棵樹為參數(shù)，計算出那些值為奇數(shù)的葉子的平方和：
def sum_odd_squares(tree):
if not tree:
return 0
elif isinstance(tree, int):
if tree % 2 == 1:
return tree**2
else:
return 0
else:
return sum_odd_squares(tree[0]) + sum_odd_squares(tree[1:])
從表面上看，這一過程與下面的過程很不一樣。下面的這個過程給定一個整數(shù)nn，對∀k?n∀k?n計算Fib(k)并篩選出其中為偶數(shù)的值，其中Fib(k)為第kk個Fibonacci數(shù)（設第0個Fibonacci數(shù)為0）：
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
該過程表示如下：
def even_fibs(n): # 枚舉從0到n的整數(shù)
def next(k):
if k > n:
return []
else:
f = fib(k) # 對每個整數(shù)計算其fib
if f % 2 == 0: # 過濾結(jié)果，選出其中偶數(shù)
return [f] + next(k + 1) # 累積結(jié)果
else:
return next(k+1)
return next(0)
print(even_fibs(5)) # [0, 2] (即[0 1 1 2 3 5]中的偶數(shù)為[0, 2])
雖然sum_odd_squares過程和even_fibs過程結(jié)構(gòu)式差異非常大，但是對于兩個計算的抽象描述卻會揭露出它們間極大的相似性。sum_odd_squares過程：
- 枚舉出一棵樹的樹葉
- 過濾它們，選出其中的奇數(shù)
- 對選出的每一個數(shù)求平方
- 用+累積起得到的結(jié)果
而 sum_odd_squares過程：
- 枚舉從00到nn的整數(shù)
- 對每個整數(shù)計算相應的Fibonacci數(shù)
- 過濾它們，選出其中的偶數(shù)
- 用
connect累計得到的結(jié)果
注意，connect函數(shù)用于對將兩個數(shù)值對象連接為列表或?qū)?shù)值對象加入一個列表，定義如下：
def con(x, y):
# y規(guī)定為int，x可以為int或list
if isinstance(x, int):
return [x] + [y]
else:
return x + [y]
信號工程師可能會發(fā)現(xiàn)，這種過程其實可以描述為信號流過一系列的級聯(lián)處理步驟，每個步驟實現(xiàn)程序方案中的一部分。如下圖所示：
遺憾的是，上面兩個過程的定義并沒有展現(xiàn)這種信號流結(jié)構(gòu)。具體地說，我們的兩個過程將enumerate工作散布在程序中各處，并將它與map、filter和reduce混在一起。如果我們能夠重新組織這一程序，使信號流結(jié)構(gòu)明顯表現(xiàn)在寫出的過程中，將會大大提高代碼的清晰性。
其中map、filter、reduce算子可以采用Python內(nèi)置函數(shù)，也可以自己實現(xiàn)。自己實現(xiàn)的話可以這樣寫：
def my_map(proc, sequence):
if not sequence:
return []
else:
return [proc(sequence[0])] + my_map(proc, sequence[1:])
print(my_map(lambda x: x**2, [1, 2, 3, 4, 5]))
# [1, 4, 9, 16, 25]
def my_filter(predicate, sequence):
if not sequence:
return []
elif predicate(sequence[0]):
return [sequence[0]] + my_filter(predicate, sequence[1:])
else:
return my_filter(predicate, sequence[1:])
print(my_filter(lambda x: x % 2, [1, 2, 3, 4, 5]))
# [1, 3, 5]
# print(list(accumulate([1,2,3])))
def my_reduce(op, sequence):
if sequence[-1] and not sequence[:-1]:
return sequence[-1]
else:
return op(my_reduce(op, sequence[:-1]), sequence[-1])
print(my_reduce(add, [1, 2, 3, 4, 5])) # 15
print(my_reduce(mul, [1, 2, 3, 4, 5])) # 120
print(my_reduce(con, [1, 2, 3, 4, 5])) # [1, 2, 3, 4, 5]
為了簡便起見，我們下面map、filter、reduce算子統(tǒng)一采用Python內(nèi)置函數(shù)。
除了這三個算子之外，我們還需要枚舉(enumerate)出需要處理的數(shù)據(jù)序列。對于even-fibs，我們需要生成一個給定區(qū)間里的整數(shù)序列：
def enumerate_interval(low, high):
if low > high:
return []
else:
return [low] + enumerate_interval(low + 1, high)
print(enumerate_interval(2, 7)) # [2, 3, 4, 5, 6, 7]
對于sum_odd_squares，則需要枚舉出一棵樹的所有樹葉：
# 枚舉一棵樹所有的樹葉：
def enumerate_tree(tree):
if not tree:
return []
elif isinstance(tree, int):
return [tree]
else:
return enumerate_tree(tree[0]) + enumerate_tree(tree[1:])
print(enumerate_tree([1, [2, [3, 4], 5]])) # [1, 2, 3, 4, 5]
現(xiàn)在，我們就可以像上面的信號流圖那樣重新構(gòu)造sum_odd_squares和even-fibs了。
sum_odd_squares的構(gòu)造方法如下：
def sum_odd_squares(tree):
return reduce(add,
map(lambda x: x**2,
filter(lambda x: x % 2,
enumerate_tree(tree))))
print(sum_odd_squares([1, 2, 3, 4, 5])) # 35
even-fibs的構(gòu)造方法如下：
def even_fibs(n):
return reduce(con,
filter(lambda x: not x % 2,
map(fib,
enumerate_interval(0, n))))
print(even_fibs(5)) #[0, 2]
將程序表示為一些針對序列的操作，這樣做的價值就愛在于能幫助我們得到模塊化的程序設計。而在工程設計中，模塊化結(jié)構(gòu)是控制復雜性的一種威力強大的策略。如同信號處理中設計者從標準的過濾器和變換裝置中選出一些東西來級聯(lián)，從而構(gòu)造出各種系統(tǒng)。同樣地，序列操作也形成了一個可以混合和匹配使用的標準程序元素庫。
如我們在另一個產(chǎn)生前n+1n+1個Fibonacci數(shù)的平方的程序里，就可以使用取自過程sum_odd_squares和even-fibs的片段：
def list_fib_squares(n):
return reduce(con,
map(lambda x: x**2,
map(fib,
enumerate_interval(0, n))))
print(list_fib_squares(5)) # [0, 1, 1, 4, 9, 25]
也可以重新安排有關的各個片段，將它們用在產(chǎn)生一個序列中所有奇數(shù)的平方之乘積的程序里：
def product_of_squares_of_odd_elements_sequence(sequence):
return reduce(mul,
map(lambda x: x**2,
filter(lambda x: x % 2, sequence)))
print(product_of_squares_of_odd_elements_sequence([1, 2, 3, 4, 5])) # [0, 1, 1, 4, 9, 25]
我們同樣可以采用序列操作的方式，重新去形式化各種常規(guī)的數(shù)據(jù)處理應用。假定有一個人事記錄的序列，現(xiàn)在希望找出其中薪水最高的程序員的工資。假定有一個salary返回記錄中的工資，謂詞函數(shù)is_programmer檢查某個記錄是不是程序員，此時我們就可以寫：
def salary_of_hightest_paid_programmer(records):
return reduce(max,
map(salary,
filter(is_programmer, records)))
在這里，用表實現(xiàn)的序列被做為一種方便的界面，我們可以利用這種界面去組合起各種處理模塊。
到此這篇關于基于Python實現(xiàn)層次性數(shù)據(jù)和閉包性質(zhì)的文章就介紹到這了,更多相關Python層次性數(shù)據(jù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Python實現(xiàn)隊列的方法,實例分析了Python實現(xiàn)隊列的相關技巧,需要的朋友可以參考下2015-05-05
Python中的復雜數(shù)據(jù)類型（list、tuple）
這篇文章介紹了Python中的復雜數(shù)據(jù)類型（list、tuple），文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-05-05
這篇文章主要為大家詳細介紹了Python Tkinter實現(xiàn)簡易計算器功能，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
今天小編就為大家分享一篇python生成lmdb格式的文件實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-11-11
深入淺析python 協(xié)程與go協(xié)程的區(qū)別
這篇文章主要介紹了python 協(xié)程與go協(xié)程的區(qū)別 ，本文給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2019-05-05
本文介紹了如何使用Python從零開始訓練自己的AI模型,包括確定問題和數(shù)據(jù)集、數(shù)據(jù)預處理、構(gòu)建模型、訓練模型、評估和調(diào)優(yōu)模型以及部署和應用模型等步驟2025-02-02
當今互聯(lián)網(wǎng)時代,數(shù)據(jù)處理已經(jīng)成為了一個非常重要的任務,而MySQL作為一款開源的關系型數(shù)據(jù)庫,被廣泛應用于各種場景,本篇博客將介紹如何使用Python操作MySQL的各種功能,以及一些高級用法,需要的朋友可以參考下2023-11-11
通過python調(diào)用adb命令對App進行性能測試方式
這篇文章主要介紹了通過python調(diào)用adb命令對App進行性能測試方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-04-04
使用python-docx庫修改docx文檔格式的兩種方法：第一種是通過自定義函數(shù)設置段落和字體樣式，第二種是預設Word中的樣式后通過代碼替換文檔整體樣式。這兩種方式各有優(yōu)缺點，第一種方法更靈活，而第二種方法可以更全面地保留格式細節(jié)2024-09-09
這篇文章主要為大家介紹了python使用UDP實現(xiàn)客戶端和服務器對話示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03