国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

SICP Python 描述 3.3 遞歸數據結構

libin19890520 / 3327人閱讀

摘要:遞歸列表可以使用遞歸函數最為自然地操作,就像它們的名稱和結構表示的那樣。處理遞歸列表遞歸列表結構將列表表示為首個元素和列表的剩余部分的組合。例如,我們可以使用高階遞歸函數將樹的每個葉子平方,它的結構類似于。成員測試會遞歸遍歷整個列表。

3.3 遞歸數據結構

來源:3.3 Recursive Data Structures

譯者:飛龍

協議:CC BY-NC-SA 4.0

在第二章中,我們引入了偶對的概念,作為一種將兩個對象結合為一個對象的機制。我們展示了偶對可以使用內建元素來實現。偶對的封閉性表明偶對的每個元素本身都可以為偶對。

這種封閉性允許我們實現遞歸列表的數據抽象,它是我們的第一種序列類型。遞歸列表可以使用遞歸函數最為自然地操作,就像它們的名稱和結構表示的那樣。在這一節中,我們會討論操作遞歸列表和其它遞歸結構的自定義的函數。

3.3.1 處理遞歸列表

遞歸列表結構將列表表示為首個元素和列表的剩余部分的組合。我們之前使用函數實現了遞歸列表,但是現在我們可以使用類來重新實現。下面,長度(__len__)和元素選擇(__getitem__)被重寫來展示處理遞歸列表的典型模式。

>>> 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__的定義實際上是遞歸的,雖然不是那么明顯。Python 內建函數len在自定義對象的參數上調用時會尋找叫做__len__的方法。與之類似,下標運算符會尋找叫做__getitem__的方法。于是,這些定義最后會調用對象自身。剩余部分上的遞歸調用是遞歸列表處理的普遍模式。這個遞歸列表的類定義與 Python 的內建序列和打印操作能夠合理交互。

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

創建新列表的操作能夠直接使用遞歸來表示。例如,我們可以定義extend_rlist函數,它接受兩個遞歸列表作為參數并將二者的元素組合到新列表中。

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

與之類似,在遞歸列表上映射函數展示了相似的模式:

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

過濾操作包括額外的條件語句,但是也擁有相似的遞歸結構。

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

列表操作的遞歸實現通常不需要局部賦值或者while語句。反之,遞歸列表可以作為函數調用的結果來拆分和構造。所以,它們擁有步驟數量和所需空間的線性增長度。

3.3.2 層次結構

層次結構產生于數據的封閉特性,例如,元組可以包含其它元組。考慮這個數值14的嵌套表示。

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

這個元組是個長度為 3 的序列,它的第一個元素也是一個元組。這個嵌套結構的盒子和指針的圖示表明,它可以看做擁有四個葉子的樹,每個葉子都是一個數值。

在樹中,每個子樹本身都是一棵樹。作為基本條件,任何本身不是元組的元素都是一個簡單的樹,沒有任何枝干。也就是說,所有數值都是樹,就像在偶對(1, 2)和整個結構中那樣。

遞歸是用于處理樹形結構的自然工具,因為我們通常可以將樹的操作降至枝干的操作,它會相應產生枝干的枝干的操作,以此類推,直到我們到達了樹的葉子。例如,我們可以實現count_leaves函數,它返回樹的葉子總數。

>>> 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是用于處理序列的強大工具,映射和遞歸一起為樹的操作提供了強大而通用的計算形式。例如,我們可以使用高階遞歸函數map_tree 將樹的每個葉子平方,它的結構類似于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)

內部值。上面描述的樹只在葉子上存在值。另一個通用的樹形結構表示也在樹的內部節點上存在值。我們使用類來表示這種樹。

>>> 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類可以為fib的遞歸實現表示表達式樹中計算的值。fib函數用于計算斐波那契數。下面的函數fib_tree(n)返回Tree,它將第 n 個斐波那契樹作為entry,并將所有之前計算出來的斐波那契數存入它的枝干中。

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

這個例子表明,表達式樹可以使用樹形結構編程表示。嵌套表達式和樹形數據結構的聯系,在我們這一章稍后對解釋器設計的討論中起到核心作用。

3.3.3 集合

除了列表、元組和字典之外,Python 擁有第四種容器類型,叫做set。集合字面值遵循元素以花括號閉合的數學表示。重復的元素在構造中會移除。集合是無序容器,所以打印出來的順序可能和元素在集合字面值中的順序不同。

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

Python 的集合支持多種操作,包括成員測試、長度計算和標準的交集并集操作。

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

除了unionintersection,Python 的集合還支持多種其它操作。斷言isdisjointissubsetissuperset提供了集合比較操作。集合是可變的,并且可以使用add、·removediscardpop一次修改一個元素。額外的方法提供了多元素的修改,例如clearupdate`。Python 集合文檔十分詳細并足夠易懂。

實現集合。抽象上,集合是不同對象的容器,支持成員測試、交集、并集和附加操作。向集合添加元素會返回新的集合,它包含原始集合的所有元素,如果沒有重復的話,也包含新的元素。并集和交集運算返回出現在任意一個或兩個集合中的元素構成的集合。就像任何數據抽象那樣,我們可以隨意實現任何集合表示上的任何函數,只要它們提供這種行為。

在這章的剩余部分,我們會考慮三個實現集合的不同方式,它們在表示上不同。我們會通過分析集合操作的增長度,刻畫這些不同表示的效率。我們也會使用這一章之前的RlistTree類,它們可以編寫用于集合元素操作的簡單而優雅的遞歸解決方案。

作為無序序列的集合。一種集合的表示方式是看做沒有出現多于一次的元素的序列??占煽招蛄衼肀硎尽3蓡T測試會遞歸遍歷整個列表。

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

這個set_contains 的實現需要Θ(n)的時間來測試元素的成員性,其中n是集合s的大小。使用這個線性時間的成員測試函數,我們可以將元素添加到集合中,也是線性時間。

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

那么問題來了,我們應該在設計表示時關注效率。計算兩個集合set1set2的交集需要成員測試,但是這次每個set1的元素必須測試set2中的成員性,對于兩個大小為n的集合,這會產生步驟數量的平方增長度Θ(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))

在計算兩個集合的并集時,我們必須小心避免兩次包含任意一個元素。union_set 函數也需要線性數量的成員測試,同樣會產生包含Θ(n^2)步驟的過程。

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

作為有序元組的集合。一種加速我們的集合操作的方式是修改表示,使集合元素遞增排列。為了這樣做,我們需要一些比較兩個對象的方式,使我們能判斷哪個更大。Python 中,許多不同對象類型都可以使用<>運算符比較,但是我們會專注于這個例子中的數值。我們會通過將元素遞增排列來表示數值集合。

有序的一個優點會在set_contains體現:在檢查對象是否存在時,我們不再需要掃描整個集合。如果我們到達了大于要尋找的元素的集合元素,我們就知道這個元素不在集合中:

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

這節省了多少步呢?最壞的情況中,我們所尋找的元素可能是集合中最大的元素,所以步驟數量和無序表示相同。另一方面,如果我們尋找許多不同大小的元素,我們可以預料到有時我們可以在列表開頭的位置停止搜索,其它情況下我們仍舊需要檢測整個列表。平均上我們應該需要檢測集合中一半的元素。所以,步驟數量的平均值應該是n/2。這還是Θ(n)的增長度,但是它確實會在平均上為我們節省之前實現的一半步驟數量。

我們可以通過重新實現intersect_set獲取更加可觀的速度提升。在無序表示中,這個操作需要Θ(n^2)的步驟,因為我們對set1的每個元素執行set2上的完整掃描。但是使用有序的實現,我們可以使用更加機智的方式。我們同時迭代兩個集合,跟蹤set1中的元素e1set2中的元素e2。當e1e2相等時,我們在交集中添加該元素。

但是,假設e1小于e2,由于e2set2的剩余元素更小,我們可以立即推斷出e1不會出現在set2剩余部分的任何位置,因此也不會出現在交集中。所以,我們不再需要考慮e1,我們將它丟棄并來到set1的下一個元素。當e2 < e1時,我們可以使用相似的邏輯來步進set2中的元素。下面是這個函數:

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

為了估計這個過程所需的步驟數量,觀察每一步我們都縮小了至少集合的一個元素的大小。所以,所需的步驟數量最多為set1set2的大小之和,而不是無序表示所需的大小之積。這是Θ(n)而不是Θ(n^2)的增長度 -- 即使集合大小適中,它也是一個相當可觀的加速。例如,兩個大小為100的集合的交集需要 200步,而不是無序表示的 10000 步。

表示為有序序列的集合的添加和并集操作也以線性時間計算。這些實現都留做練習。

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

樹形表示的優點是:假設我們打算檢查v是否在集合中。我們通過將ventry比較開始。如果v小于它,我們就知道了我們只需要搜索left子樹。如果v大于它,我們只需要搜索right子樹?,F在如果樹是“平衡”的,每個這些子樹都約為整個的一半大小。所以,每一步中我們都可以將大小為n的樹的搜索問題降至搜索大小為n/2的子樹。由于樹的大小在每一步減半,我們應該預料到,用戶搜索樹的步驟以Θ(log n)增長。比起之前的表示,它的速度對于大型集合有可觀的提升。set_contains 函數利用了樹形集合的有序結構:

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

向集合添加元素與之類似,并且也需要Θ(log n)的增長度。為了添加值v,我們將ventry比較,來決定v應該添加到right還是left分支,以及是否已經將v添加到了合適的分支上。我們將這個新構造的分支與原始的entry和其它分支組合。如果v等于entry,我們就可以返回這個節點。如果我們被要求將v添加到空的樹中,我們會生成一個Tree,它包含v作為entry,并且leftright都是空的分支。下面是這個函數:

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

搜索該樹可以以對數步驟數量執行,我們這個敘述基于樹是“平衡”的假設。也就是說,樹的左子樹和右子樹都擁有相同數量的相應元素,使每個子樹含有母樹一半的元素。但是我們如何確定,我們構造的樹就是平衡的呢?即使我們以一顆平衡樹開始,使用adjoin_set添加元素也會產生不平衡的結果。由于新添加的元素位置取決于如何將元素與集合中的已有元素比較,我們可以預測,如果我們“隨機”添加元素到樹中,樹在平均上就會趨向于平衡。

但是這不是一個保證。例如,如果我們以空集開始,并向序列中添加 1 到 7,我們就會在最后得到很不平衡的樹,其中所有左子樹都是空的,所以它與簡單的有序列表相比并沒有什么優勢。一種解決這個問題的方式是定義一種操作,它將任意的樹轉換為具有相同元素的平衡樹。我們可以在每個adjoin_set操作之后執行這個轉換來保證我們的集合是平衡的。

交集和并集操作可以在樹形集合上以線性時間執行,通過將它們轉換為有序的列表,并轉換回來。細節留做練習。

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

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/38156.html

相關文章

  • SICP Python 描述 第三章 計算機程序的構造和解釋 3.1 引言

    摘要:為通用語言設計解釋器的想法可能令人畏懼。但是,典型的解釋器擁有簡潔的通用結構兩個可變的遞歸函數,第一個求解環境中的表達式,第二個在參數上調用函數。這一章接下來的兩節專注于遞歸函數和數據結構,它們是理解解釋器設計的基礎。 3.1 引言 來源:3.1 Introduction 譯者:飛龍 協議:CC BY-NC-SA 4.0 第一章和第二章描述了編程的兩個基本元素:數據和函數之間的...

    v1 評論0 收藏0
  • SICP Python 描述 3.2 函數和所生成的過程

    摘要:函數和所生成的過程來源譯者飛龍協議函數是計算過程的局部演化模式。在這一章中,我們會檢測一些用于簡單函數所生成過程的通用模型。也就是說,遞歸函數的執行過程可能需要再次調用這個函數。 3.2 函數和所生成的過程 來源:3.2 Functions and the Processes They Generate 譯者:飛龍 協議:CC BY-NC-SA 4.0 函數是計算過程的局部演化...

    lolomaco 評論0 收藏0
  • SICP Python 描述 1.5 控制

    摘要:函數體由表達式組成。我們說頭部控制語句組。于是,函數體內的賦值語句不會影響全局幀。包含了多種假值,包括和布爾值。布爾值表示了邏輯表達式中的真值。執行測試以及返回布爾值的函數通常以開頭,并不帶下劃線例如等等。返回值之后會和預期結果進行比對。 1.5 控制 來源:1.5 Control 譯者:飛龍 協議:CC BY-NC-SA 4.0 我們現在可以定義的函數能力有限,因為我們還不知...

    mingzhong 評論0 收藏0
  • SICP Python 描述 2.3 序列

    摘要:序列不是特定的抽象數據類型,而是不同類型共有的一組行為。不像抽象數據類型,我們并沒有闡述如何構造序列。這兩個選擇器和一個構造器,以及一個常量共同實現了抽象數據類型的遞歸列表。 2.3 序列 來源:2.3 Sequences 譯者:飛龍 協議:CC BY-NC-SA 4.0 序列是數據值的順序容器。不像偶對只有兩個元素,序列可以擁有任意(但是有限)個有序元素。 序列在計算機科學中...

    AlexTuan 評論0 收藏0
  • SICP Python 描述 3.5 組合語言的解釋器

    摘要:計算器語言解釋器的核心是叫做的遞歸函數,它會求解樹形表達式對象。到目前為止,我們在描述求值過程中所引用的表達式樹,還是概念上的實體。解析器實際上由兩個組件組成,詞法分析器和語法分析器。標記序列由叫做的詞法分析器產生,并被叫做語法分析器使用。 3.5 組合語言的解釋器 來源:3.5 Interpreters for Languages with Combination 譯者:飛龍 ...

    sanyang 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<