【 Use Python Implementation algorithm 】 Catalog
- 01 Linguistic characteristics
- 02 Native types and built-in functions
Recently joined the question brushing group organized by colleagues in the company , Will attend regularly LeetCode And so on .
As a senior Pythonist, I always use Python To achieve a variety of algorithm problems .Python It also provides some good language features 、 Built in functions and standard libraries to more efficiently and concisely write the code implementation of various algorithms .
This series of blogs is for my personal use Python Work and brush some use of the experience summary Python Some skills for implementing various algorithms .
As the first article in the series , The theme of this issue is Python Language characteristics of .
Deconstruct assignment
Swapping the values of two variables is a very common scenario , stay C and C++ In language , We need to use a temporary variable . The code will be lengthy , And there will be a small performance overhead .
int tmp = x;
int x = y;
int y = x;
utilize Python The property of deconstruction and assignment , We can use an assignment statement to exchange the values of two variables .
x, y = y, x
In the implementation of the algorithm , A common use of deconstruction assignment is to initialize multiple variables at once .
ans, total, n = 0, 0, len(lst)
Python The deconstruction assignment of can also be used in for In circulation .
points = [(1, 2), (2, 3), (3, 4)]
for x, y in points:
pass
We can also use some more complex deconstruction assignment statements .
(x, y), z = (1, 2), 3
assert (x, y, z) == (1, 2, 3)
first, *rest = list(range(5))
assert (first, rest) == (0, [1, 2, 3, 4])
List derivation
Use declarative list derivation syntax instead of imperative for loop , The code is more readable , And has a certain performance improvement （Python The interpreter has special optimizations for list derivations ）.
# 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))
generator
Defining a generator function can avoid maintaining a mutable list in many cases （ Or other containers ）, Make the code simpler .
@dataclass
class TreeNode:
val: int
left: Optional["TreeNode"] = None
right: Optional["TreeNode"] = None
# Common implementation of the preorder traversal
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
# Preorder traversal of the generator version
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))
Structural pattern matching
Structured pattern matching is Python 3.10 New features , With this feature, you can write more elegant code .
# A conceptual implementation of quicksort
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])
)
The above is what I think can effectively help to realize the algorithm Python Linguistic characteristics , If used reasonably, it can write more efficient and concise algorithms for all kinds of algorithms 、 Readable Python Code implementation .
The next blog will cover some Python The ingenious role of built-in types and built-in functions in algorithm implementation .
