ARTS #44

Algorithm

规则如下：

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution

我实现的方案：

Runtime：32 ms，快过 97.84%。

Memory：14 MB，低于 5.55%。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        cache = {}
        def dp(i, j) -> bool:
            if (i, j) not in cache:
                if len(p) == j:
                    ans = i == len(s)
                else:
                    match = i < len(s) and (p[j] == '.' or p[j] == s[i])

                    if len(p) >= j + 2 and p[j + 1] == "*":
                        ans = dp(i, j+2) or match and dp(i + 1, j)
                    else:
                        ans = match and dp(i + 1, j + 1)
                cache[(i, j)] = ans
            return cache[(i, j)]

        return dp(0, 0)

优化后和 Solution 完全相同的 dp + 剪枝实现。

另一个实现方式：

class Solution(object):
    def isMatch(self, s: str, p: str) -> bool:
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[-1][-1] = True
        for i in range(len(s), -1, -1):
            for j in range(len(p)-1, -1, -1):
                match = i < len(s) and (p[j] == '.' or p[j] == s[i])

                if j+1 < len(p) and p[j+1] == "*":
                    dp[i][j] = dp[i][j+2] or match and dp[i+1][j]
                else:
                    dp[i][j] = match and dp[i+1][j+1]
        return dp[0][0]

Review

Garbage collection in Python: things you need to know

Python 中的内存管理策略：

通过私有堆（private heaps）维护所有的 Python 对象和数据结构，这个区域只有 Python 解释器能访问
通过内置的 memory manager 管理这个堆，它为 Python 对象进行必需的内存分配工作
使用了一个内置的 GC，用于回收内存

而这篇文章主要是讲述 Python 使用 GC 的背景/目的，要解决什么样的问题以及如何解决的。

为什么要使用 GC？

Python 在内存管理上主要是依靠引用计数算法，引用计数的优势是即时，当对象不再需要时很容易回收内存。但是它有一个问题，就是无法解决因为循环引用而造成的内存泄漏。

GC 与循环引用有什么不同？

GC 不是实时的，而是周期性的执行，GC 执行时需要“暂停”程序的运行。

GC 是如何发现循环引用的？

类似于“标记-清除”算法，不过在标记的过程中实际做的是测试，也就是遍历所有的容器对象，并将它们对其他容器对象的引用计数全部减1，整个过程结束后，将引用计数为0且没有任何活动对象指向它的对象标记为不可达。

更多信息请参阅：

GC 在 Python 中是如何工作的？

Python 将容器对象分为了三代：

0代，新生代对象，生命周期短
1代，0代对象经过一定的 GC 次数后仍然存活，晋升为1代
2代，1代对象经过一定的 GC 次数后仍然存活，晋升为2代

每代都有一个独立的计数器和阀值（threshold），计数器存储对象数量，当计数器超过阀值时启动 GC；如果同时有多代超出了阀值，GC 会选择最老的代，这是因为最老的代也会收集比它年轻的代。

分代的回收的好处是提升垃圾回收的效率，因为无论哪种语言，对于变量在内存中的创建/销毁总有频繁和不频繁的，比如全局变量和自动变量。引入分代回收机制可以针对频繁的“代”做更多的检测，不频繁的“代”少做，避免对全部对象做检测，以此来提高回收效率。

Tip

lambda 和 function 的区别：

lambda 可以认为是只包含一个表达式的匿名函数
lambda 可以很方便的使用在 dict/list 这样的数据结构中
最关键的，lambda 是 inplace 的，这一点在设计上与函数完全不同

今天是个特别的日子，我们能够享受岁月静好，是因为有人替我们负重前行。