写点什么

【使用 Python 实现算法】01 语言特性

作者:★忆先★
  • 2022 年 6 月 27 日
  • 本文字数:1511 字

    阅读完需:约 5 分钟

【使用 Python 实现算法】目录




最近加入了公司同事组织的刷题群,会定期参加 LeetCode 等平台的算法比赛。


作为一个资深 Pythonist,我一向是使用 Python 来实现各种算法题目的。Python 本身也提供了一些不错的语言特性、内置函数和标准库来更高效简洁的编写各类算法的代码实现。


本系列博客是我根据个人使用 Python 工作和刷题的经验总结的一些使用 Python 实现各类算法的一些技巧。


作为系列博客的第一篇文章,本期的主题是 Python 的语言特性。

解构赋值

交换两个变量的值是一个很常见的场景,在 C 和 C++语言中,我们需要使用一个临时变量。代码会比较冗长,并且会有微小的性能开销。


int tmp = x;int x = y;int y = x;
复制代码


利用 Python 的解构赋值特性,我们可以使用一个赋值语句交换两个变量的值。


x, y = y, x
复制代码


在算法实现中,解构赋值的一个常见用法是一次初始化多个变量。


ans, total, n = 0, 0, len(lst)
复制代码


Python 的解构赋值同样可以用在 for 循环中。


points = [(1, 2), (2, 3), (3, 4)]for x, y in points:    pass
复制代码


我们也可以使用一些更复杂的解构赋值语句。


(x, y), z = (1, 2), 3assert (x, y, z) == (1, 2, 3)
first, *rest = list(range(5))assert (first, rest) == (0, [1, 2, 3, 4])
复制代码

列表推导式

使用声明式的列表推导式语法替代命令式的 for 循环,代码的可读性更强,并且有一定的性能提升(Python 解释器对列表推导式有专门的优化)。


# find first num in list nums which test(a) is True
def first(nums: list[int], test: Callable[[int], bool]) -> int: for num in nums: if test(num): return num

def first(nums: list[int], test: Callable[[int], bool]) -> int: return next(num for num in nums if test(num))
复制代码

生成器

定义一个生成器函数在很多情况下可以避免维护一个可变的列表(或其他容器),使得代码更简洁。


@dataclassclass TreeNode:    val: int    left: Optional["TreeNode"] = None    right: Optional["TreeNode"] = None
# 普通实现的先序遍历def preorder(root: TreeNode | None) -> list[int]: ans = []
def dfs(root: TreeNode | None) -> None: if not root: return ans.append(root.val) dfs(root.left) dfs(root.right)
dfs(root)
return ans
# 生成器版本的先序遍历def preorder(root: TreeNode | None) -> list[int]: def dfs(root: TreeNode | None) -> Generator[int, None, None]: if not root: return yield root.val yield from dfs(root.left) yield from dfs(root.right)
return list(dfs(root))
复制代码

结构化模式匹配

结构化模式匹配是 Python 3.10 的新特性,利用好这个特性可以写出更优雅的代码。


# 快速排序的一个概念性实现def quicksort(arr: list[int]) -> list[int]:    match arr:        case first,:            return [first]        case first, second:            return [first, second] if first <= second else [second, first]        case first, *rest:            return (                quicksort([num for num in rest if num <= first])                + [first]                + quicksort([num for num in rest if num > first])            )
复制代码


以上是一些我认为可以有效帮助到算法实现的 Python 语言特性,合理利用的话可以为各类算法编写出更高效简洁、可读性强的 Python 代码实现。


下一篇博客将介绍一些 Python 的内置类型和内置函数在算法实现中的巧妙作用。

发布于: 刚刚阅读数: 3
用户头像

★忆先★

关注

还未添加个人签名 2018.11.12 加入

Python后端开发

评论

发布
暂无评论
【使用Python实现算法】01 语言特性_Python_★忆先★_InfoQ写作社区