3.3 遞歸數(shù)據(jù)結(jié)構(gòu)

來(lái)源：3.3 Recursive Data Structures

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

在第二章中，我們引入了偶對(duì)的概念，作為一種將兩個(gè)對(duì)象結(jié)合為一個(gè)對(duì)象的機(jī)制。我們展示了偶對(duì)可以使用內(nèi)建元素來(lái)實(shí)現(xiàn)。偶對(duì)的封閉性表明偶對(duì)的每個(gè)元素本身都可以為偶對(duì)。

這種封閉性允許我們實(shí)現(xiàn)遞歸列表的數(shù)據(jù)抽象，它是我們的第一種序列類(lèi)型。遞歸列表可以使用遞歸函數(shù)最為自然地操作，就像它們的名稱(chēng)和結(jié)構(gòu)表示的那樣。在這一節(jié)中，我們會(huì)討論操作遞歸列表和其它遞歸結(jié)構(gòu)的自定義的函數(shù)。

3.3.1 處理遞歸列表

遞歸列表結(jié)構(gòu)將列表表示為首個(gè)元素和列表的剩余部分的組合。我們之前使用函數(shù)實(shí)現(xiàn)了遞歸列表，但是現(xiàn)在我們可以使用類(lèi)來(lái)重新實(shí)現(xiàn)。下面，長(zhǎng)度（__len__）和元素選擇（__getitem__）被重寫(xiě)來(lái)展示處理遞歸列表的典型模式。

>>> class Rlist(object):
        """A recursive list consisting of a first element and the rest."""
        class EmptyList(object):
            def __len__(self):
                return 0
        empty = EmptyList()
        def __init__(self, first, rest=empty):
            self.first = first
            self.rest = rest
        def __repr__(self):
            args = repr(self.first)
            if self.rest is not Rlist.empty:
                args += ', {0}'.format(repr(self.rest))
            return 'Rlist({0})'.format(args)
        def __len__(self):
            return 1 + len(self.rest)
        def __getitem__(self, i):
            if i == 0:
                return self.first
            return self.rest[i-1]

__len__和__getitem__的定義實(shí)際上是遞歸的，雖然不是那么明顯。Python 內(nèi)建函數(shù)len在自定義對(duì)象的參數(shù)上調(diào)用時(shí)會(huì)尋找叫做__len__的方法。與之類(lèi)似，下標(biāo)運(yùn)算符會(huì)尋找叫做__getitem__的方法。于是，這些定義最后會(huì)調(diào)用對(duì)象自身。剩余部分上的遞歸調(diào)用是遞歸列表處理的普遍模式。這個(gè)遞歸列表的類(lèi)定義與 Python 的內(nèi)建序列和打印操作能夠合理交互。

>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> s.rest
Rlist(2, Rlist(3))
>>> len(s)
3
>>> s[1]
2

創(chuàng)建新列表的操作能夠直接使用遞歸來(lái)表示。例如，我們可以定義extend_rlist函數(shù)，它接受兩個(gè)遞歸列表作為參數(shù)并將二者的元素組合到新列表中。

>>> def extend_rlist(s1, s2):
        if s1 is Rlist.empty:
            return s2
        return Rlist(s1.first, extend_rlist(s1.rest, s2))
>>> extend_rlist(s.rest, s)
Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3)))))

與之類(lèi)似，在遞歸列表上映射函數(shù)展示了相似的模式：

>>> def map_rlist(s, fn):
        if s is Rlist.empty:
            return s
        return Rlist(fn(s.first), map_rlist(s.rest, fn))
>>> map_rlist(s, square)
Rlist(1, Rlist(4, Rlist(9)))

過(guò)濾操作包括額外的條件語(yǔ)句，但是也擁有相似的遞歸結(jié)構(gòu)。

>>> def filter_rlist(s, fn):
        if s is Rlist.empty:
            return s
        rest = filter_rlist(s.rest, fn)
        if fn(s.first):
            return Rlist(s.first, rest)
        return rest
>>> filter_rlist(s, lambda x: x % 2 == 1)
Rlist(1, Rlist(3))

列表操作的遞歸實(shí)現(xiàn)通常不需要局部賦值或者while語(yǔ)句。反之，遞歸列表可以作為函數(shù)調(diào)用的結(jié)果來(lái)拆分和構(gòu)造。所以，它們擁有步驟數(shù)量和所需空間的線性增長(zhǎng)度。

3.3.2 層次結(jié)構(gòu)

層次結(jié)構(gòu)產(chǎn)生于數(shù)據(jù)的封閉特性，例如，元組可以包含其它元組?？紤]這個(gè)數(shù)值1到4的嵌套表示。

>>> ((1, 2), 3, 4)
((1, 2), 3, 4)

這個(gè)元組是個(gè)長(zhǎng)度為 3 的序列，它的第一個(gè)元素也是一個(gè)元組。這個(gè)嵌套結(jié)構(gòu)的盒子和指針的圖示表明，它可以看做擁有四個(gè)葉子的樹(shù)，每個(gè)葉子都是一個(gè)數(shù)值。

在樹(shù)中，每個(gè)子樹(shù)本身都是一棵樹(shù)。作為基本條件，任何本身不是元組的元素都是一個(gè)簡(jiǎn)單的樹(shù)，沒(méi)有任何枝干。也就是說(shuō)，所有數(shù)值都是樹(shù)，就像在偶對(duì)(1, 2)和整個(gè)結(jié)構(gòu)中那樣。

遞歸是用于處理樹(shù)形結(jié)構(gòu)的自然工具，因?yàn)槲覀兺ǔ？梢詫?shù)的操作降至枝干的操作，它會(huì)相應(yīng)產(chǎn)生枝干的枝干的操作，以此類(lèi)推，直到我們到達(dá)了樹(shù)的葉子。例如，我們可以實(shí)現(xiàn)count_leaves函數(shù)，它返回樹(shù)的葉子總數(shù)。

>>> t = ((1, 2), 3, 4)
>>> count_leaves(t)
4
>>> big_tree = ((t, t), 5)
>>> big_tree
((((1, 2), 3, 4), ((1, 2), 3, 4)), 5)
>>> count_leaves(big_tree)
9

正如map是用于處理序列的強(qiáng)大工具，映射和遞歸一起為樹(shù)的操作提供了強(qiáng)大而通用的計(jì)算形式。例如，我們可以使用高階遞歸函數(shù)map_tree將樹(shù)的每個(gè)葉子平方，它的結(jié)構(gòu)類(lèi)似于count_leaves。

>>> def map_tree(tree, fn):
        if type(tree) != tuple:
            return fn(tree)
        return tuple(map_tree(branch, fn) for branch in tree)
>>> map_tree(big_tree, square)
((((1, 4), 9, 16), ((1, 4), 9, 16)), 25)

內(nèi)部值。上面描述的樹(shù)只在葉子上存在值。另一個(gè)通用的樹(shù)形結(jié)構(gòu)表示也在樹(shù)的內(nèi)部節(jié)點(diǎn)上存在值。我們使用類(lèi)來(lái)表示這種樹(shù)。

>>> class Tree(object):
        def __init__(self, entry, left=None, right=None):
            self.entry = entry
            self.left = left
            self.right = right
        def __repr__(self):
            args = repr(self.entry)
            if self.left or self.right:
                args += ', {0}, {1}'.format(repr(self.left), repr(self.right))
            return 'Tree({0})'.format(args)

例如，Tree類(lèi)可以為fib的遞歸實(shí)現(xiàn)表示表達(dá)式樹(shù)中計(jì)算的值。fib函數(shù)用于計(jì)算斐波那契數(shù)。下面的函數(shù)fib_tree(n)返回Tree，它將第 n 個(gè)斐波那契樹(shù)作為entry，并將所有之前計(jì)算出來(lái)的斐波那契數(shù)存入它的枝干中。

>>> def fib_tree(n):
        """Return a Tree that represents a recursive Fibonacci calculation."""
        if n == 1:
            return Tree(0)
        if n == 2:
            return Tree(1)
        left = fib_tree(n-2)
        right = fib_tree(n-1)
        return Tree(left.entry + right.entry, left, right)
>>> fib_tree(5)
Tree(3, Tree(1, Tree(0), Tree(1)), Tree(2, Tree(1), Tree(1, Tree(0), Tree(1))))

這個(gè)例子表明，表達(dá)式樹(shù)可以使用樹(shù)形結(jié)構(gòu)編程表示。嵌套表達(dá)式和樹(shù)形數(shù)據(jù)結(jié)構(gòu)的聯(lián)系，在我們這一章稍后對(duì)解釋器設(shè)計(jì)的討論中起到核心作用。

3.3.3 集合

除了列表、元組和字典之外，Python 擁有第四種容器類(lèi)型，叫做set。集合字面值遵循元素以花括號(hào)閉合的數(shù)學(xué)表示。重復(fù)的元素在構(gòu)造中會(huì)移除。集合是無(wú)序容器，所以打印出來(lái)的順序可能和元素在集合字面值中的順序不同。

>>> s = {3, 2, 1, 4, 4}
>>> s
{1, 2, 3, 4}

Python 的集合支持多種操作，包括成員測(cè)試、長(zhǎng)度計(jì)算和標(biāo)準(zhǔn)的交集并集操作。

>>> 3 in s
True
>>> len(s)
4
>>> s.union({1, 5})
{1, 2, 3, 4, 5}
>>> s.intersection({6, 5, 4, 3})
{3, 4}

除了union和intersection，Python 的集合還支持多種其它操作。斷言isdisjoint、issubset和issuperset提供了集合比較操作。集合是可變的，并且可以使用add、·remove、discard和pop一次修改一個(gè)元素。額外的方法提供了多元素的修改，例如clear和update`。Python 集合文檔十分詳細(xì)并足夠易懂。

實(shí)現(xiàn)集合。抽象上，集合是不同對(duì)象的容器，支持成員測(cè)試、交集、并集和附加操作。向集合添加元素會(huì)返回新的集合，它包含原始集合的所有元素，如果沒(méi)有重復(fù)的話，也包含新的元素。并集和交集運(yùn)算返回出現(xiàn)在任意一個(gè)或兩個(gè)集合中的元素構(gòu)成的集合。就像任何數(shù)據(jù)抽象那樣，我們可以隨意實(shí)現(xiàn)任何集合表示上的任何函數(shù)，只要它們提供這種行為。

在這章的剩余部分，我們會(huì)考慮三個(gè)實(shí)現(xiàn)集合的不同方式，它們?cè)诒硎旧喜煌?。我們?huì)通過(guò)分析集合操作的增長(zhǎng)度，刻畫(huà)這些不同表示的效率。我們也會(huì)使用這一章之前的Rlist和Tree類(lèi)，它們可以編寫(xiě)用于集合元素操作的簡(jiǎn)單而優(yōu)雅的遞歸解決方案。

作為無(wú)序序列的集合。一種集合的表示方式是看做沒(méi)有出現(xiàn)多于一次的元素的序列。空集由空序列來(lái)表示。成員測(cè)試會(huì)遞歸遍歷整個(gè)列表。

>>> def empty(s):
        return s is Rlist.empty
>>> def set_contains(s, v):
        """Return True if and only if set s contains v."""
        if empty(s):
            return False
        elif s.first == v:
            return True
        return set_contains(s.rest, v)
>>> s = Rlist(1, Rlist(2, Rlist(3)))
>>> set_contains(s, 2)
True
>>> set_contains(s, 5)
False

這個(gè)set_contains的實(shí)現(xiàn)需要Θ(n)的時(shí)間來(lái)測(cè)試元素的成員性，其中n是集合s的大小。使用這個(gè)線性時(shí)間的成員測(cè)試函數(shù)，我們可以將元素添加到集合中，也是線性時(shí)間。

>>> def adjoin_set(s, v):
        """Return a set containing all elements of s and element v."""
        if set_contains(s, v):
            return s
        return Rlist(v, s)
>>> t = adjoin_set(s, 4)
>>> t
Rlist(4, Rlist(1, Rlist(2, Rlist(3))))

那么問(wèn)題來(lái)了，我們應(yīng)該在設(shè)計(jì)表示時(shí)關(guān)注效率。計(jì)算兩個(gè)集合set1和set2的交集需要成員測(cè)試，但是這次每個(gè)set1的元素必須測(cè)試set2中的成員性，對(duì)于兩個(gè)大小為n的集合，這會(huì)產(chǎn)生步驟數(shù)量的平方增長(zhǎng)度Θ(n^2)。

>>> def intersect_set(set1, set2):
        """Return a set containing all elements common to set1 and set2."""
        return filter_rlist(set1, lambda v: set_contains(set2, v))
>>> intersect_set(t, map_rlist(s, square))
Rlist(4, Rlist(1))

在計(jì)算兩個(gè)集合的并集時(shí)，我們必須小心避免兩次包含任意一個(gè)元素。union_set函數(shù)也需要線性數(shù)量的成員測(cè)試，同樣會(huì)產(chǎn)生包含Θ(n^2)步驟的過(guò)程。

>>> def union_set(set1, set2):
        """Return a set containing all elements either in set1 or set2."""
        set1_not_set2 = filter_rlist(set1, lambda v: not set_contains(set2, v))
        return extend_rlist(set1_not_set2, set2)
>>> union_set(t, s)
Rlist(4, Rlist(1, Rlist(2, Rlist(3))))

作為有序元組的集合。一種加速我們的集合操作的方式是修改表示，使集合元素遞增排列。為了這樣做，我們需要一些比較兩個(gè)對(duì)象的方式，使我們能判斷哪個(gè)更大。Python 中，許多不同對(duì)象類(lèi)型都可以使用<和>運(yùn)算符比較，但是我們會(huì)專(zhuān)注于這個(gè)例子中的數(shù)值。我們會(huì)通過(guò)將元素遞增排列來(lái)表示數(shù)值集合。

有序的一個(gè)優(yōu)點(diǎn)會(huì)在set_contains體現(xiàn)：在檢查對(duì)象是否存在時(shí)，我們不再需要掃描整個(gè)集合。如果我們到達(dá)了大于要尋找的元素的集合元素，我們就知道這個(gè)元素不在集合中：

>>> def set_contains(s, v):
        if empty(s) or s.first > v:
            return False
        elif s.first == v:
            return True
        return set_contains(s.rest, v)
>>> set_contains(s, 0)
False

這節(jié)省了多少步呢？最壞的情況中，我們所尋找的元素可能是集合中最大的元素，所以步驟數(shù)量和無(wú)序表示相同。另一方面，如果我們尋找許多不同大小的元素，我們可以預(yù)料到有時(shí)我們可以在列表開(kāi)頭的位置停止搜索，其它情況下我們?nèi)耘f需要檢測(cè)整個(gè)列表。平均上我們應(yīng)該需要檢測(cè)集合中一半的元素。所以，步驟數(shù)量的平均值應(yīng)該是n/2。這還是Θ(n)的增長(zhǎng)度，但是它確實(shí)會(huì)在平均上為我們節(jié)省之前實(shí)現(xiàn)的一半步驟數(shù)量。

我們可以通過(guò)重新實(shí)現(xiàn)intersect_set獲取更加可觀的速度提升。在無(wú)序表示中，這個(gè)操作需要Θ(n^2)的步驟，因?yàn)槲覀儗?duì)set1的每個(gè)元素執(zhí)行set2上的完整掃描。但是使用有序的實(shí)現(xiàn)，我們可以使用更加機(jī)智的方式。我們同時(shí)迭代兩個(gè)集合，跟蹤set1中的元素e1和set2中的元素e2。當(dāng)e1和e2相等時(shí)，我們?cè)诮患刑砑釉撛亍?/p>

但是，假設(shè)e1小于e2，由于e2比set2的剩余元素更小，我們可以立即推斷出e1不會(huì)出現(xiàn)在set2剩余部分的任何位置，因此也不會(huì)出現(xiàn)在交集中。所以，我們不再需要考慮e1，我們將它丟棄并來(lái)到set1的下一個(gè)元素。當(dāng)e2 < e1時(shí)，我們可以使用相似的邏輯來(lái)步進(jìn)set2中的元素。下面是這個(gè)函數(shù)：

>>> def intersect_set(set1, set2):
        if empty(set1) or empty(set2):
            return Rlist.empty
        e1, e2 = set1.first, set2.first
        if e1 == e2:
            return Rlist(e1, intersect_set(set1.rest, set2.rest))
        elif e1 < e2:
            return intersect_set(set1.rest, set2)
        elif e2 < e1:
            return intersect_set(set1, set2.rest)
>>> intersect_set(s, s.rest)
Rlist(2, Rlist(3))

為了估計(jì)這個(gè)過(guò)程所需的步驟數(shù)量，觀察每一步我們都縮小了至少集合的一個(gè)元素的大小。所以，所需的步驟數(shù)量最多為set1和set2的大小之和，而不是無(wú)序表示所需的大小之積。這是Θ(n)而不是Θ(n^2)的增長(zhǎng)度 -- 即使集合大小適中，它也是一個(gè)相當(dāng)可觀的加速。例如，兩個(gè)大小為100的集合的交集需要 200步，而不是無(wú)序表示的 10000 步。

表示為有序序列的集合的添加和并集操作也以線性時(shí)間計(jì)算。這些實(shí)現(xiàn)都留做練習(xí)。

作為二叉樹(shù)的集合。我們可以比有序列表表示做得更好，通過(guò)將幾個(gè)元素重新以樹(shù)的形式排列。我們使用之前引入的Tree類(lèi)。樹(shù)根的entry持有集合的一個(gè)元素。left分支的元素包括所有小于樹(shù)根元素的元素。right分支的元素包括所有大于樹(shù)根元素的元素。下面的圖展示了一些樹(shù)，它們表示集合{1, 3, 5, 7, 9, 11}。相同的集合可能會(huì)以不同形式的樹(shù)來(lái)表示。有效表示所需的唯一條件就是所有left子樹(shù)的元素應(yīng)該小于entry，并且所有right子樹(shù)的元素應(yīng)該大于它。

樹(shù)形表示的優(yōu)點(diǎn)是：假設(shè)我們打算檢查v是否在集合中。我們通過(guò)將v于entry比較開(kāi)始。如果v小于它，我們就知道了我們只需要搜索left子樹(shù)。如果v大于它，我們只需要搜索right子樹(shù)。現(xiàn)在如果樹(shù)是“平衡”的，每個(gè)這些子樹(shù)都約為整個(gè)的一半大小。所以，每一步中我們都可以將大小為n的樹(shù)的搜索問(wèn)題降至搜索大小為n/2的子樹(shù)。由于樹(shù)的大小在每一步減半，我們應(yīng)該預(yù)料到，用戶搜索樹(shù)的步驟以Θ(log n)增長(zhǎng)。比起之前的表示，它的速度對(duì)于大型集合有可觀的提升。set_contains函數(shù)利用了樹(shù)形集合的有序結(jié)構(gòu)：

>>> def set_contains(s, v):
        if s is None:
            return False
        elif s.entry == v:
            return True
        elif s.entry < v:
            return set_contains(s.right, v)
        elif s.entry > v:
            return set_contains(s.left, v)

向集合添加元素與之類(lèi)似，并且也需要Θ(log n)的增長(zhǎng)度。為了添加值v，我們將v與entry比較，來(lái)決定v應(yīng)該添加到right還是left分支，以及是否已經(jīng)將v添加到了合適的分支上。我們將這個(gè)新構(gòu)造的分支與原始的entry和其它分支組合。如果v等于entry，我們就可以返回這個(gè)節(jié)點(diǎn)。如果我們被要求將v添加到空的樹(shù)中，我們會(huì)生成一個(gè)Tree，它包含v作為entry，并且left和right都是空的分支。下面是這個(gè)函數(shù)：

>>> def adjoin_set(s, v):
        if s is None:
            return Tree(v)
        if s.entry == v:
            return s
        if s.entry < v:
            return Tree(s.entry, s.left, adjoin_set(s.right, v))
        if s.entry > v:
            return Tree(s.entry, adjoin_set(s.left, v), s.right)

>>> adjoin_set(adjoin_set(adjoin_set(None, 2), 3), 1)
Tree(2, Tree(1), Tree(3))

搜索該樹(shù)可以以對(duì)數(shù)步驟數(shù)量執(zhí)行，我們這個(gè)敘述基于樹(shù)是“平衡”的假設(shè)。也就是說(shuō)，樹(shù)的左子樹(shù)和右子樹(shù)都擁有相同數(shù)量的相應(yīng)元素，使每個(gè)子樹(shù)含有母樹(shù)一半的元素。但是我們?nèi)绾未_定，我們構(gòu)造的樹(shù)就是平衡的呢？即使我們以一顆平衡樹(shù)開(kāi)始，使用adjoin_set添加元素也會(huì)產(chǎn)生不平衡的結(jié)果。由于新添加的元素位置取決于如何將元素與集合中的已有元素比較，我們可以預(yù)測(cè)，如果我們“隨機(jī)”添加元素到樹(shù)中，樹(shù)在平均上就會(huì)趨向于平衡。

但是這不是一個(gè)保證。例如，如果我們以空集開(kāi)始，并向序列中添加 1 到 7，我們就會(huì)在最后得到很不平衡的樹(shù)，其中所有左子樹(shù)都是空的，所以它與簡(jiǎn)單的有序列表相比并沒(méi)有什么優(yōu)勢(shì)。一種解決這個(gè)問(wèn)題的方式是定義一種操作，它將任意的樹(shù)轉(zhuǎn)換為具有相同元素的平衡樹(shù)。我們可以在每個(gè)adjoin_set操作之后執(zhí)行這個(gè)轉(zhuǎn)換來(lái)保證我們的集合是平衡的。

交集和并集操作可以在樹(shù)形集合上以線性時(shí)間執(zhí)行，通過(guò)將它們轉(zhuǎn)換為有序的列表，并轉(zhuǎn)換回來(lái)。細(xì)節(jié)留做練習(xí)。

Python 集合實(shí)現(xiàn)。Python 內(nèi)建的set類(lèi)型并沒(méi)有使用上述任意一種表示。反之，Python 使用了一種實(shí)現(xiàn)，它的成員測(cè)試和添加操作是（近似）常量時(shí)間的，基于一種叫做哈希（散列）的機(jī)制，這是其它課程的話題。內(nèi)建的 Python 集合不能包含可變的數(shù)據(jù)類(lèi)型，例如列表、字典或者其它集合。為了能夠嵌套集合，Python 也提供了一種內(nèi)建的不可變frozenset類(lèi)，除了可變操作和運(yùn)算符之外，它擁有和set相同的方法。