ARTS-2018-12-09

Algorithm

Merge Two Sorted Lists

合并两个有序链表。思路很简单，创建一个空链表，然后对比两个链表的表头，哪个小，就把哪个添加到创建的链表上。因为两个链表的长度未必是相等的，所以注意处理一些空逻辑。

// 链表节点
nextListNode := &ListNode{}
// 纪录链表头
result := nextListNode

for l1 != nil && l2 != nil {
    if (l1.Val <= l2.Val) {
        nextListNode.Next = l1
        l1 = l1.Next
    } else {
        nextListNode.Next = l2
        l2 = l2.Next
    }
    // 链表的下一个节点
    nextListNode = nextListNode.Next
}

Remove Duplicates from Sorted Array

移除数组中相等的元素。这个题目比较坑爹，我开始以为是要返回一个新数组，后面才看懂题目的检测方式是根据你返回的数值，遍历指定长度的原数组，只要输出和结果能匹配上就好。所以原数组的长度可以保持不变，只要遍历输出的结果是对的就好了。

所以正确的解题方式就是，把不重复的元素依次放到原数组的前排就好了。

// 有效元素指针，第一个元素肯定是有效元素
i := 0

// 原数组元素指针
for j := 1; j < len(nums); j++ {
    // 和前面元素比较，如果不相等，则当前元素有效，依次放在前面的有效元素后面
    if (nums[i] != nums[j]) {
        i++
        nums[i] = nums[j]
    }
}

// 数组长度为指针位置+1
return i + 1

Remove Element

从数组中移除制定的值。这个和 Remove Duplicates from Sorted Array 一样，直接把不相等的元素放到原数组的前排就好了。

// 有效元素指针
i := 0

for j := 0; j < len(nums); j++ {
    if (nums[j] != val) {
        nums[i] = nums[j]
        // 将非重复元素移到前面后，指针已经提前移动到下一个位置了
        i++
    }
}

return i

Review

PHP 7.3.0 Released

PHP 现在更新得很勤快，版本号突突的刷。除了 PHP7 这个大版本更新带来了大幅度的性能提升外，后续更新都是在稳定性上发力，这次更新突然提到了很久没动静的 GC，我的印象中，好像从 5.3 优化了之后再也没出现在 ChangeLog 上，所以这次看看更新了啥。

本身由于 FPM “请求->初始化->执行->销毁” 这样的执行流程导致了，只要 Zend 内核稳定，就不会有内存泄漏问题，毕竟最后都会被销毁回收，所以 PHP 的 GC 只是在执行流程中，提高内内存的利用率，处于这样的定位， GC 算法设计得比较简单。

早期这样较高“性价比”的取舍是没问题的，但是随着现代软件项目越来越大以及 composer 的广泛使用，这样的 GC 算法显然已经跟不上潮流了。典型的就是 composer 在安装依赖的时候会关闭 GC ，避免性能问题。好的 GC 对 Laravel、Symfony 这样重型的全栈框架提升是很明显的，对 PHP 的 deamon 服务，也是大有裨益。

GC improvement 是这次更新在 github 上的提交。

这次到底优化了个啥呢？

这次 GC 的算法还是没变：依然有个 roots 的列表，当它达到 10000 的时候开始执行垃圾回收。

但是这里有个问题，就是可能因为软件项目足够复杂，正常运转就会有大量正常的变量被创建，被回收的很少，所以 roots 的长度一直接近 GC 启动的阈值，导致 GC 被频繁的触发，造成性能问题。

所以这次优化的是 GC 的触发时机。当一次 GC 执行完只回收了少量的变量后，下次 GC 触发的时候，会加大 roots 的容量，提高 GC 触发阈值，当然也不是无脑加大，遵循“快启动、慢慢涨”逻辑，容量上限 1G。

具体逻辑扩容逻辑在这里，很简单清晰，此次改进的结果是对越复杂的项目，性能提升越明显。

// Very, very, very many objects GC | OLD | NEW disabled | 1.32s | 1.50s enabled | 12.75s | 2.32s

// Very many objects GC | OLD | NEW disabled | 0.87s | 0.87s enabled | 1.48s | 0.94s

// Less many objects GC | OLD | NEW disabled | 1.65s | 1.62s enabled | 1.75s | 1.62s

Tip

Iterator 和 Generator

PHP 中迭代器和生成器是2种类型，经常被混淆。

Iterator 迭代器，是一个提供被迭代能力的接口。

Generator 生成器 ，则是建立在迭代器的基础之上，可以叫做迭代生成器，因为它就是一个不可 new 的类，同时继承 Iterator，且多了一个send() 与生成器通信，它是通过yield关键字来实现的。

简而言之，就是你实现迭代器之后，你就能拥有了被迭代的能力。但是如果你使用yield，每次被调用的时候都会返回一个 Generator 对象，因为本身它实现了 Iterator 所以它能被迭代，当前的迭代值就是yield的返回值。但是得注意到当你迭代 Generator 对象的时候，下一个值是什么并不是已经生成好放在那里等你来调用，而是“临时”生成。对于那些巨大的遍历对象，这样可能很好的节省内存。

下面这个例子就能很好的说明。

function gen_one_to_three() {
    for ($i = 1; $i <= 3; $i++) {
        yield $i;
    }
}

foreach (gen_one_to_three() as $value) {
    echo "$value\n";
}

$list = [1,2,3];
foreach ($list as $value) {
    echo "$value\n";
}

同时生成器会提供一个交互功能或者可以将它当作“协程”来使用，使得它在某些场景下会有亮眼的表现。

Share

php-ffi

FFI PHP extension (Foreign Function Interface)，这个拓展很厉害啊，能直接通过 PHP 调用 C 的函数，并支持 C 的数据结构语法，这样访问一些 C 类库就不只有封装 PHP 拓展这一种方式来实现了，直接调用相应的 C 函数，多方便。

有趣的使用场景，就是通过 PHP 来调用 tensorflow 的类库来进行深度学习的了解，比如这个项目。

当然会有更多场景，目前鸟哥已经 fork 了这个项目，看来这个项目前景可期。