sugar/ 十一月 18, 2019/ python设计模式/ 0 comments

编写优秀代码的一个要素是避免冗余。在面向对象编程中,方法和函数是我们用来避免编写冗余代码的重要工具。

sorted()这样的函数属于理想的案例。现实中,我们没法始终写出100%通用的代码。许多算法都有一些(但并非全部)通用步骤。广度优先搜索(Breadth-First Search,BFS)和深度优先搜索(Depth-First Search,DFS)是其中不错的例子,这两个流行的算法应用于图搜索问题。起初,我们提出独立实现两个算法。函数bfs()和dfs()在start和end之间存在一条路径时返回一个元组(True, path);如果路径不存在,则返回(False, path)(此时,path为空)。

# coding: utf-8


def bfs(graph, start, end):
    path = []
    visited = [start]
    while visited:
        current = visited.pop(0)
        if current not in path:
            path.append(current)
            if current == end:
                print(path)
                return (True, path)
            # 两个顶点不相连,则跳过
            if current not in graph:
                continue
        visited = visited + graph[current]
    return (False, path)


def dfs(graph, start, end):
    path = []
    visited = [start]
    while visited:
        current = visited.pop(0)
        if current not in path:
            path.append(current)
            if current == end:
                print(path)
                return (True, path)
            # 两个顶点不相连,则跳过
            if current not in graph:
                continue
        visited = graph[current] + visited
    return (False, path)


def main():
    graph = {
        'Frankfurt': ['Mannheim', 'Wurzburg', 'Kassel'],
        'Mannheim': ['Karlsruhe'],
        'Karlsruhe': ['Augsburg'],
        'Augsburg': ['Munchen'],
        'Wurzburg': ['Erfurt', 'Nurnberg'],
        'Nurnberg': ['Stuttgart', 'Munchen'],
        'Kassel': ['Munchen'],
        'Erfurt': [],
        'Stuttgart': [],
        'Munchen': []
    }

    bfs_path = bfs(graph, 'Frankfurt', 'Nurnberg')
    dfs_path = dfs(graph, 'Frankfurt', 'Nurnberg')
    print('bfs Frankfurt-Nurnberg: {}'.format(bfs_path[1] if bfs_path[0] else 'Not found'))
    print('dfs Frankfurt-Nurnberg: {}'.format(dfs_path[1] if dfs_path[0] else 'Not found'))

    bfs_nopath = bfs(graph, 'Wurzburg', 'Kassel')
    print('bfs Wurzburg-Kassel: {}'.format(bfs_nopath[1] if bfs_nopath[0] else 'Not found'))
    dfs_nopath = dfs(graph, 'Wurzburg', 'Kassel')
    print('dfs Wurzburg-Kassel: {}'.format(dfs_nopath[1] if dfs_nopath[0] else 'Not found'))

if __name__ == '__main__':
    main()

现实生活的例子

工人的日程,特别是对于同一个公司的工人而言,非常接近于模板设计模式。所有工人都遵从或多或少相同的例行流程,但例行流程的某些特定部分区别又很大。情况如下图所示。

应用案例

模板设计模式旨在消除代码重复。如果我们发现结构相近的(多个)算法中有重复代码,则可以把算法的不变(通用)部分留在一个模板方法/函数中,把易变(不同)的部分移到动作/钩子方法/函数中。
页码标注是一个不错的模板模式应用案例。一个页码标注算法可以分为一个抽象(不变的)部分和一个具体(易变的)部分。不变的部分关注的是最大行号/页号这部分内容。易变的部分则包含用于显示某个已分页特定页面的页眉和页脚的功能。
所有应用框架都利用了某种形式的模板模式。在使用框架来创建图形化应用时,通常是继承自一个类,并实现自定义行为。然而,在执行自定义行为之前,通常会调用一个模板方法,该方法实现了应用中一定相同的部分,比如绘制屏幕、处理事件循环、调整窗口大小并居中,等等。

实现

from cowpy import cow


def dots_style(msg):
    msg = msg.capitalize()
    msg = '.' * 10 + msg + '.' * 10
    return msg


def admire_style(msg):
    msg = msg.upper()
    return '!'.join(msg)


def cow_style(msg):
    msg = cow.milk_random_cow(msg)
    return msg


def generate_banner(msg, style=dots_style):
    print('-- start of banner --')
    print(style(msg))
    print('-- end of banner --\n\n')


def main():
    msg = 'happy coding'
    [generate_banner(msg, style) for style in (dots_style, admire_style, cow_style)]

if __name__ == '__main__':
    main()

在实现结构相近的算法时,可以使用模板模式来消除冗余代码。具体实现方式是使用动作/钩子方法/函数来完成代码重复的消除,它们是Python中的一等公民。

使用模板模式来重构BFS和DFS算法的代码。

# coding: utf-8


def traverse(graph, start, end, action):
    path = []
    visited = [start]
    while visited:
        current = visited.pop(0)
        if current not in path:
            path.append(current)
            if current == end:
                return (True, path)
            # 两个顶点不相连,则跳过
            if current not in graph:
                continue
        visited = action(visited, graph[current])
    return (False, path)


def extend_bfs_path(visited, current):
    return visited + current


def extend_dfs_path(visited, current):
    return current + visited


def main():
    graph = {
        'Frankfurt': ['Mannheim', 'Wurzburg', 'Kassel'],
        'Mannheim': ['Karlsruhe'],
        'Karlsruhe': ['Augsburg'],
        'Augsburg': ['Munchen'],
        'Wurzburg': ['Erfurt', 'Nurnberg'],
        'Nurnberg': ['Stuttgart', 'Munchen'],
        'Kassel': ['Munchen'],
        'Erfurt': [],
        'Stuttgart': [],
        'Munchen': []
    }

    bfs_path = traverse(graph, 'Frankfurt', 'Nurnberg', extend_bfs_path)
    dfs_path = traverse(graph, 'Frankfurt', 'Nurnberg', extend_dfs_path)
    print('bfs Frankfurt-Nurnberg: {}'.format(bfs_path[1] if bfs_path[0] else 'Not found'))
    print('dfs Frankfurt-Nurnberg: {}'.format(dfs_path[1] if dfs_path[0] else 'Not found'))

    bfs_nopath = traverse(graph, 'Wurzburg', 'Kassel', extend_bfs_path)
    print('bfs Wurzburg-Kassel: {}'.format(bfs_nopath[1] if bfs_nopath[0] else 'Not found'))
    dfs_nopath = traverse(graph, 'Wurzburg', 'Kassel', extend_dfs_path)
    print('dfs Wurzburg-Kassel: {}'.format(dfs_nopath[1] if dfs_nopath[0] else 'Not found'))

if __name__ == '__main__':
    main()
Share this Post

说点什么

avatar
  Subscribe  
提醒