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 了这个项目,看来这个项目前景可期。

本文由程小白创作,本文可自由转载、引用,但需署名作者且注明文章出处。

原文地址:https://www.chengxiaobai.cn/arts/20181209.html