ARTS #10

Algorithm

规则如下：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution

我实现的方案：

Runtime：88 ms，快过 96.25%。

Memory：13.6 MB，低于 23.68%。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        filled = '#' + '#'.join(s) + '#'
        filled_length = len(filled)

        max_right = 0
        max_right_index = 0

        max_index = 0
        nums = [0] * filled_length

        for index in range(0, filled_length):
            skip = False

            if index < max_right:
                length = nums[2 * max_right_index - index]
                if length + index > max_right:
                    nums[index] = max_right - index
                else:
                    nums[index] = length
                    skip = length + index < max_right

            if not skip:
                while index - nums[index] - 1 >= 0 and index + nums[index] + 1 < filled_length:
                    if filled[index - nums[index] - 1] != filled[index + nums[index] + 1]:
                        break

                    nums[index] += 1

                max_right = index + nums[index]
                max_right_index = index

            max_index = max_index if nums[max_index] >= nums[index] else index

        low = (max_index - nums[max_index]) // 2
        high = (max_index + nums[max_index]) // 2
        return s[low:high]

Review

Achieving concurrency in Go
详细描述了并发和并行的区别，还着重比较了 Thread 和 Goroutine 的差异：

Goroutine 被堵塞的时机：

等待网络、文件等
sleeping
channel 接受或者发送会造成堵塞的情况
一些 sync 操作，如调用：
- runtime.gosched，goruntine 将主动放弃 CPU（runnable 状态），一般是在执行长时间任务时又想让其它 goroutine 也得到执行机会时调用
- runtime.park，goruntine 将进入 waiting 状态，需要用 runtime.ready 手动唤醒，一般是要等待某个具体的条件

该文总结的不错，不过缺少关于 Stack 如何伸缩的说明，我另找了几篇作为参考：

Contiguous stacks in Go

Go: How Does the Goroutine Stack Size Evolve?

关于 Stack 的一些总结：

Stack 初始大小：2Kb，这个数值被调整过两次，分别是：
- Go 1.2: stack 从 4Kb 增加到 8Kb
- Go 1.4: stack 从 8Kb 减少到 2Kb
Stack 能动态调整大小，当空间不够时，通过 runtime.morestack_noctxt -> newstack 将大小扩充1倍，具体的：
- 创建一个新的 Stack
- 把所有数据拷贝从旧的 Stack 拷贝到新的 Stack
- 重新调整每一个复制的指针指向新的 Stack 中的地址
- 销毁旧的 Stack
GC 执行完垃圾回收后，将判断 Stack 所使用的空间是否为原大小的 \(\frac{1}{4}\)，满足条件则将大小收缩为 \(\frac{1}{2}\)

目前的实现称为 Contiguous Stack(Go 版本为 1.12)，而在 1.3 以前采用的是 Segmented Stack。

之所以要取代 Segmented Stack，是因为它有 hot split 问题：

Current split stack mechanism has a “hot split” problem — if the stack is almost full, a call will force a new stack chunk to be allocated. When that call returns, the new stack chunk is freed. If the same call happens repeatedly in a tight loop, the overhead of the alloc/free causes significant overhead

如下这个例子：

func main() {
    for {
        big()
    }
}

func big() {
    var x [8180]byte
    // do something with x

    return
}

调用 big() 将导致一个新的 segment 被创建，然后在 return 时销毁，因为调用发生在循环中，所以创建-销毁也会反复执行，这样重复创建、销毁的开销会变得很大。对关注性能的 Go 来说这是不能容忍的，过去的解决方案就是在 1.2 版本中将 Stack 大小增加到 8Kb，而在实现了 Contiguous Stack 后就降为了 2Kb。

Tip

Jekyll

Jekyll 的 post_url tag 能为指定的 post 生成正确的 link，这样就不用硬写死了：

[传送门](/software/2019/08/03/The-most-important-skill-a-programmer-can-learn.html)
=>
[传送门]({% post_url 2019-08-03-The most important skill a programmer can learn %})

JavaScript

Array.from(iterable or arrayLike, ?mapFn, ?thisArg) 这个函数很有意思，iterable 可以接收 arrayLike，这意味着只需要提供一个有 length 的任意对象，就能快速创建一个固定长度的数组，比如：

Array.from({ length: 5 })
// (5) [undefined, undefined, undefined, undefined, undefined]

Array.from({ length: 5 }).forEach((v, i) => console.log(i) )
/*
0
1
2
3
4
*/

第三个参数是一个 this 指针，用于在 mapFn 里访问 this：

Array.from({ length: 5 }, function(x) {
  console.log(this); // String {"This is a test"}
  return x;
}, "This is a test");

Python

Python 变量都是 Block 作用域，分为三种：global、local、nonlocal。

未定义 local 变量时将使用 global 变量
不能同时使用同名的 local、global 变量，需要显式指定以避免含糊不清的语义
使用 nonlocal 时一定要确保能在外围作用域里找到变量，只能用于在嵌套方法中引用外围变量
global 引用不到时，会定义该变量

反例一

def f(): 
	print(s) # UnboundLocalError: local variable 's' referenced before assignment
	s = "I love London!"
	print(s)

s = "I love Paris!"
f()

# 第二行的 s 试图在定义本地变量前访问；如果去掉第三行赋值语句，s 将使用 global 变量

反例二

def f():
    s = "I am globally not known"
    print(s) 

f()
print(s) # name 's' is not defined

# 不能访问出了作用域的本地变量 s

反例三

def f():
    nonlocal x # no binding for nonlocal 'x' found
    print(x)
    
x = 3
f()

# x 是 global 变量，不能通过 nonlocal 引用

反例四

def f():
    def g():
        nonlocal x # no binding for nonlocal 'x' found
        x = 43
    print("Before calling g: " + str(x))
    print("Calling g now:")
    g()
    print("After calling g: " + str(x))
    
x = 3
f()
print("x in main: " + str(x))

# 外围方法 f 中未定义 local 变量 x

更多论述及例子参见：Global, Local and nonlocal Variables

最长回文子串是一个很经典的问题，这周刚好随机到了，我想就趁此机会多记录些关于这个算法背后的设计推导。

放到这周的 Share 里，传送门