ARTS-3

RTS-3 第三周

Review an introduction of to principles of Functional Programming

函数式编程规约简介

标题如是，这是一篇关于函数式编程的入门级别的简介文章。作者同样提供了一篇基于JavaScript的解说。

回顾

长时间使用面向对象的编程语言工作和学习后，是时候用几个步骤来回顾一下系统复杂度了。

复杂性是软件难遇理解和维护的全部原因。

函数式编程是什么

函数式编程是一种编程范式，一种构建计算机程序和元素的风格，它将计算视为数学上函数，并避免了状态变化和可变数据。-- wiki 

纯函数

纯函数是函数式编程中第一个重要概念，那么。 #### 纯函数是什么

纯函数首先是一个函数，它具有两个基本特征： 1. 多次执行，给定相同的参数必然得到相同的结果。 2. 执行中，不会带来可以观察到的副作用状态改变。

纯函数的优势

纯函数易于测试，它的特征决定了对于这类程序的测试简单有效。

不变性

不变性是函数式编程的又一重要特性，很直观。数据一旦创建就永不可更改。 对于多年沉浸面向对象变成的程序员易于理解，就是所有的数据都是const数据，同时感到不可思议。

如文中提到的，一旦数据创建后不可变，那么，像非函数式语言中的for each 循环该如何实现呢？ 在函数式编程范式中，循环使用递归来实现。这里不展开讲述。

引用透明性

基本上，如果一个函数对相同的输入始终产生相同的结果，那么它就是引用透明的。

pure functions + immutable data = referential transparency

在这个前提下, 许多类似 (+3(+ 5 8)) 一类的表达式, 就会直接优化为它的常量结果, 因为他们总是不变的。

函数式一等公民

函数式编程范式中, 函数不止作为函数, 它也被视为一个值, 当做一个数据来用。(个人认为类似于C语言中的函数, 实际上函数指针也可以这么用, 只是在语言和语法层面是体现的不明显)

高阶函数

什么是高阶函数

高阶函数首先要是一个函数, 其次, 得满足两个特点至少其中之一: 1. 参数列表中至少含有一个函数类型的形参。 2. 它的返回值是一个函数。

When we talk about higher-order functions, we mean a function that either: 1.takes one or more functions as arguments, or
2.returns a function as its result

未尽之言

以上可能我自己也摸不着头脑,但是我已经把大意总结了一下, 剩下的未尽之言都是作者写了一些琐碎处的细节, 举例子贴代码来阐明的自己的观点, 这个我不好总结, 总之, 大意如此, 这是一篇函数式编程的入门文章, 浅显易懂, 深入浅出, 从未接触过函数式编程语言的我读后收益匪浅, 确实的开阔了眼界和思维。

Algorithm: First Bad Version

引言

本周就做了两道leetcode题目, 要分享的这个题目来源于Leetcode的Weekly Digest, 它试一次邮件推送。 easy难度, 给我个easy的题目,大概是leetcode都认为我比较水。

原始邮件:

Hi earneet,

We have an easy question that we thought you might be interested in solving:

First Bad Version
Solved 211443 times
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of...

First Bad Version

Description

278. First Bad Version
Easy

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

假设我是一个项目管理, 正在领导一个开发团队做一个新产品, 不幸的是我的项目出了问题, 但不知道是哪个版本, 我的版本号管理是从1开始的自增升序, 我有个验证api isBadVersion(version)来验证当前版本是好的还是坏的, 问: 通过最少次的验证来找到第一个坏掉的版本, 应该怎么做。

思路

这是一个数组的查找问题, 从一堆版本号构成的数组[1,2,3,4 ... n]中,找到第一个符合要求的索引。 这个情况非常熟悉了, 如果这个数组是关于索引有规律的, 那么我们可以通过哈希计算获得位置, 如果是有顺序的,也可以通过二分查找来加快搜索。 乍一看, 这个数组符合第二个情况, 但是, 版本号并不是我们直接要找的目标值,它需要经过一次api调用的转换来达到目标数组。

好在, 这个题目还有个隐含的条件, 在某一个出错版本, 也就是我们的目标之前的所有版本, 都是正确的, 在这个版本之后, 都是错误的, 我可以映射好版本结果为0,而坏版本结果为1,那么原数组就被转换为了 [0, ... m, 1 ... n] 其中 m >= 0 且 m <= n。 至此已经完成了升序数组的转换。

这个题目与一般查找稍有差异, 它当中存在了大量的重复元素(它本来就只有两种元素), 我需要找到目标元素的第一次出现的位置。这里,基本可以确定是二分法查找没错了, 继续分析如何进行二分。

1. middle位置的结果为0。 此种情况下, 数组部分应为如 [...,0, 0, 0, 1, 1 ...], 粗体位置为middle,红色元素分别为left和right, 这种情况下, 应把left指针右移。使 left从当前middle的下一个元素迭代。
2. middle位置的结果为1。 此种情况下, 数组部分应为[...,0, 0,1, 1, 1, 1 ...], 粗体位置为middle,红色元素分别为left和right, 这种情况下, 应当将right指针左移,从当前middle元素位置开始迭代。

如此, 二分的迭代规则已经明确了, 剩下的问题就是代码实现了。

Answer

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        register int min = 1;
        while (min <= n) {
          register int middle = min + (n-min)/2;
          if (isBadVersion(middle)){
            n = middle - 1;
          } else {
            min = middle + 1;
          }
        }
        return min > n ? min : n;
    }
};

当我写这个篇文的时候才发现, 可能以上代码虽然被AC了, 但是可能是错误的, 简略先记一下我发现的问题, 后面会更正本文。

为了更快速地迭代,我在指针移动时, 指针略过已经试过的当前middle元素, 如果是左移,则使 right = middle - 1, 若为右移, 则使 left = middle + 1, 若如此做, 一个尴尬的问题就来了, 这样可能恰好错过了目标解, 就如 [...,0, 0, 0, 1, 1, 1, 1 ...] 这种情况, right指针左移时, 下次的位置应为左侧第二个0, 现在, 目标解已经脱出了我们的 left和right指针范围!!

以上这段, 使我写本文时才发现, 夜深了, 先记在这里, 明后天想明白了之后再更正。

Tip 尽早失败,短流程优先

引言

本次分享的尽早失败是我在乐天派工作的时候, 项目组杨老师传授给我的经验,在后面的工作中屡试不爽, 特作一个分享, 完整的技巧不止于此, 在本篇中, 只分享其中的一个小点, 在条件语句中优先失败。这个技巧在很多的IDE中应该都会有提示, 但是项目代码里还是常见不遵循这个的代码, 我并不是说不这么写一定不好, 但是个人还是倾向于尽早失败, 让代码结构更加清晰。

尽早失败

不管新手还是老鸟, 在项目中总会看到如下面这样的代码

function () {
    // do something pre
    if (checkcondition1) {
        // do something 1
        if (checkcondition2) {
            // do something 2
            if (checkcondition3) {
                // do something3
            }
        }
    }
    return result;
}

甚至是在循环结构里出现如上代码

function () {
    // do something pre
    if (checkcondition0){
        for () {
            if (checkcondition1) {
                // do something 1
                if (checkcondition2) {
                    // do something 2
                    if (checkcondition3) {
                        // do something3
                    }
                }
            }
        }
    }
    return result;
}

如果感觉第一个代码还可以接受, 那么, 第二个代码的缩进层级就让人感到可怕, 但是这样的代码确确实实的在项目里出现了。

这里我针对第二个代码, 做一个"尽早失败"的风格修改。

function () {
    // do something pre
    if (not checkcondition0)
        return;
    for () {
        if (not checkcondition1) 
            continue;
        // do something 1
        if (not checkcondition2) 
            continue;
        // do something 2
        if (not checkcondition3)
            continue;
        // do something3
    }
    return result;
}

这个写法, 使的原先代码尾部一连串难以搞懂层级的}不见了, 缩进层级由6层, 缩减到了3层, 整个代码都条理了。

这就是杨老师传授的所谓的"尽早失败"技巧的其中一个应用, 在编写条件分支时,尽量不使用但条件的 if (true) dosomething 这样的分支, 而是使用 if (not true) return; dosometing 这样的分支, 这样会大大的减少代码的缩进层级。

短流程优先

还是不管新手还是老鸟, 在项目中总会看到如下面这样的代码

if (condition) {
    // do operation 1
    // do operation 2
    if (condition2) {
        // do operation 3
    } else {
        // do operation 4
    }
    // do operation 5
} else {
    // log a message 
    return;
}

更夸张一点的真实代码我就不贴出来了, 我自己亲身经历过的是, 一个 if 分支内写了整整两屏的代码, 然后else 分支内就打了一句错误日志, 向另一个系统发送了一条协议。

这种情况下, 单单使用上面说的尽早失败进行修改虽然也可以, 但是牵扯到了其他分支内也有有用操作, 貌似还是差点意思。所以, 这里倾向于"短流程优先", 即写为:

if (not condition) {
    // log a message 
    return;
} 
// do operation 1
// do operation 2
if (condition2) {
    // do operation 3
} else {
    // do operation 4
}
// do operation 5

将流程最短, 最简洁的代码写在最前面, 这样条件分支会更清晰, 剩下最后的就只有一个复杂的情况, 代码阅读者会一下子厘清前面的分支情况, 然后慢慢分析最后的"一坨屎", 否则, 可能一开始就被这一坨搞乱了, 导致即使后面分支简洁, 也因为需要记忆前面一坨, 导致思维变累。

杨老师传授加上我自己琢磨的针对这个的技巧不止如上, 本篇先分享这一些, 后面再分享时将剩下一些总结一下补充来。

Share

引言

本来预计的分享又又又又又未能完成。

本次的分享源于我打算做的一个东西, 我之前有一块某米品牌的安卓平板, 由于我已经更新换代了设备,这个旧设备已经很久不用, 所以我打算把它改为一个便携显示器用来接ps4玩游戏, 所以ps4主机是比较封闭的, 输出我能够接入的只有hdmi接口, 要么我选择采购昂贵的视频采集卡来做,要么我只好研究下hdmi传输标准, 看看能不能做个硬件来做一下信号转换, 把hdmi信号编解码, 通过usb或者wifi传输给平板, 再在平板上解码输出, 于是,我翻阅了不少hdmi资料, 特分享一则讲的比较浅显的前辈的文。 ### 内容 HDMI协议

Flag

我个人做java开发比较多, 之前就想写一篇文来讲明白jvm中synchonize和volatile的实现,但是各种原因一直未能成行, 再次立一个Flag, 在劳动节前ARTS中, share分享部分我要分享我的这篇文, 我一定要在期限内完成。