您现在的位置是：网站首页> 编程资料编程资料

基于Python实现层次性数据和闭包性质_python_

2023-05-26 335人已围观

简介 基于Python实现层次性数据和闭包性质_python_

绪论

序对可以为我们提供用于构造复合数据的基本“粘接剂”，鉴于Python中tuple中元素不可变的性质，我们通过list来实现序对，如[1, 2]。Python的PyListObject对象中实际是存放的是PyObject*指针， 所以可以将PyListObject视为vecter。这是一种盒子与指针表示方式(list内的元素表示为一个指向对象盒子的指针)。对于[1, 2]，可将其视为以下结构：

我们不仅可以用[]去组合起各种数值，也可以用它取组合起其它序对。这样，序对就是一种通用的建筑砌块，通过它可以构造所有不同种类的数据结构来。比如想组合数值1, 2, 3, 4，我们可以用[[1, 2], [3, 4]]的方式(下图左)，也可以用[[1, [2, 3]], 4](下图右)

可以构建元素本身也是序对的序对，这种能力称为[]的闭包性质。注意，这里的闭包是来自抽象代数的术语（不是Python语法中那个闭包）。抽象代数中，如果将某个运算（操作）作用于某个集合的特定元素 ，产出的仍然是该集合的元素，则称该集合元素在该运算之下封闭。我们这里说组合数据对象的操作满足闭包性质，指通过它组合起数据对象得到的结果本身还可以通过同样的操作再进行组合。

闭包性质可以使我们构建层次性的结构，这种结构由一些部分构成，而其中的各个部分又是由它们的部分构成，并且可以继续下去。下面我们介绍用序对来表示序列和树。

1.序列的表示

利用序对可以够造出的一类有用结构是序列——一批数据对象的有序汇集。利用序对表示序列的方式很多，一种最直接的表示方式为[1, [2, [3, [4, None]]]]如下图所示：

我们不妨将这种通过嵌套序对形成的序列称为链表。因为Python本身不内置链表结构，我们不妨用序对来实现链表：

class LinkedList(): def __init__(self, *items) -> None: """提供两种初始化方式:序对或多个元素 """ if isinstance(items[0], list): self.pair = items[0] else: self.pair = self._construct(*items) def _construct(self, *items): """递归地构造链表 """ if items == (): return None else: item, *rest = items return [item, self._construct(*rest)] def __repr__(self): """重写打印函数 """ 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])

这样，我们就可以方便地构造链表并将其打印输出了：

print(LinkedList(1, 2, 3, 4)) # 1-->2-->3-->4

注意，None用于表示序对的链结束。在语言设计上可能有以下争论：None应该是个普通的名字吗？None应该算是一个普通的名字吗？None应该算是一个符号吗？他应该算是一个空表吗？在Python中，解决此问题的手段是将None的类型规定为，

表操作

利用序对将元素的序列表示为链表之后，我们就可以使用常规的程序设计技术，通过获取链表的head和rest的方式完成对链表的各种操作了。如下面的过程list-ref实际参数是一个表和一个数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)) # 16

length过程则用于返回表中的项数：

def length(items): if items is None: return 0 else: return 1 + length(items.rest) print(length(LinkedList(1, 3, 5, 7))) # 4

或者写为迭代的形式(此处用尾递归的形式，即递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这样就无需保存返回值，可在常数空间内执行迭代型计算):

# 以迭代的方式计算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解释器默认是不开启尾递归优化的，需要用其他黑魔法实现，参考《Python开启尾递归优化!》

还有一种常见操作是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]，也可以通过递归实现：

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

对链表的映射

另外一个特别拥有用的操作时将某种操作应用于一个链表的所有元素，得到所有结果构成的表。下面的过程将一个链表中的所有元素按给定因子做一次缩放：

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

我们可以抽象出这一具有一般性的想法，将其中的公共模式表述为一个高阶函数(接收其它函数做为参数)。

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

这里的公共模式，其实就类似于设计模式中的模板方法，参见设计模式：模板方法。

现在我们可以用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是一种很重要的结构，不仅因为它代表了一种公共模式，而且因为它建立起了一种处理表的高层抽象（与今日的Scala何其相似！），在老版本的scale_list中，程序的递归结构将人的注意力吸引到对表中元素的逐个处理中。通过map定义的scale_list抑制了这种细节层面上的情况，强调的是从元素表到结果表的一个缩放变换。这两种定义形式之间的差异，并不在于计算机会执行不同的计算过程（其实不会），而在于我们对同一个过程的不同思考方式。 从作用上看，map帮我们建起了一层抽象屏障，将实现表转换过程的实现，与与如何提取表中元素以及组合结果的细节隔离开。

2.层次性结构

注意，由于下面由于我们会涉及更复杂的数据结构，我们统一将序列就用Python内置的列表表示。

我们下面来看元素本身也是序列的序列。比如我们可以认为[[1, 2], 3, 4]是将[1, 2]做为元素加入序列[3, 4]而得。这种表结构可以看做是树，即序列中的元素就是树的分支，而那些本身也是序列的元素就形成了树中的子树：

递归是处理树结构的一种很自然的工具，因为我们常常可以将对于树的操作归结为对它们的分支的操作，再将这种操作归结为对分支的分支的操作，如此下去，直至达到了树的叶子。如类似2.2.1中用length统计序列长度，我们通过以下代码统计树叶数目：

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与递归结合也是处理树的一种强有力抽象。类似于2.2.1中用scale_list过程对序列元素进行缩放，我们也可以设计scale_tree过程，该过程以一个因子和一棵叶子为数值的树作为参数，返回一颗具有同样形状的树，该树中的每个数值都乘以了这个因子：

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

实现scale_tree的另一种方法是将树看成子树的序列，并对它使用map。我们在这种序列上做映射，一次对各棵子树做缩放，并返回结果的表。对于基础情况，也就是当被处理的树是树叶时，就直接用因子去乘它：

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语言内置的map，当然也可以自己实现my_map，如下：

def my_map(proc, items): if items == []: return [] else: return [proc(items[0])] + my_map(proc, items[1:])

3.序列做为一种约定的界面

数据抽象可以让我们设计出不被数据表示细节纠缠的程序，使程序保持很好的弹性。在这一节里，我们将要介绍与数据结构有关的另一种强有力的设计原理——使用约定的界面。

在1.3节中我们看到，通过实现为高阶过程的程序抽象，可以让我们抓住处理数值数据的一些程序模式。而在复合数据上工作做出类似的操作，则对我们操控数据结构的方式有着深刻的依赖性。如考虑一个与2.2.2节中的count_leaves类似的过程，它以一棵树为参数，计算出那些值为奇数的叶子的平方和：

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

从表面上看，这一过程与下面的过程很不一样。下面的这个过程给定一个整数nn，对∀k⩽n∀k⩽n计算Fib(k)并筛选出其中为偶数的值，其中Fib(k)为第kk个Fibonacci数（设第0个Fibonacci数为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的整数 def next(k): if k > n: return [] else: f = fib(k) # 对每个整数计算其fib if f % 2 == 0: # 过滤结果，选出其中偶数 return [f] + next(k + 1) # 累积结果 else: return next(k+1) return next(0) print(even_fibs(5)) # [0, 2] (即[0 1 1 2 3 5]中的偶数为[0, 2])

虽然sum_odd_squares过程和even_fibs过程结构式差异非常大，但是对于两个计算的抽象描述却会揭露出它们间极大的相似性。sum_odd_squares过程：

  • 枚举

    上一篇：Python使用Pillow添加水印_python_

    下一篇：Python pickle模块实现Python对象持久化存储_python_

相关内容

点击排行

本栏推荐

猜你喜欢

-六神源码网