大名鼎鼎的 objc.io 有一本书叫做 Functional Swift,只看到这个名字很容易误导人以为 Swift 可以是 Functional 的,但事实上这压根不可能,那本书更准确的名称应该是 Functional part of Swift。一个过程式语言可以拥有函数式的功能,特别是一些比较新的语言 Python Ruby 就曾经因为带有这些功能让人觉得更高级,同时也会被一些人评价说他们只不过实现了一些古老语言早就有的功能。这个评价是客观事实,早期从理论研究中诞生的编程语言大多都很函数式,局部变量和赋值这种过程式的功能仅仅是他们的一小部分。大规模应用于实践之后诞生的编程语言则完全将这一局面翻转了过来,完全是建立在局部变量和赋值之上的过程式,慢慢发展之后才开始增加一些函数式的功能。

函数式和过程式的不同根本在于选择不同的模型来模拟现实环境。在现实环境中状态(state)是客观存在的,过程式语言选择使用局部变量来模拟状态用赋值来模拟状态的改变,而函数式语言选择用流结构来模拟状态。

用局部变量和赋值来模拟状态是很容易理解的,这种模拟方式是离散的。状态本身可以看做是一个以时间为参数的函数,局部变量的值就是这个函数在不同的时间作为参数时函数所得到的值。与此相对,流结构是连续的,函数式语言模拟状态的方式并不直接处理每个时间参数下的函数值而是直接处理函数整体,使用的手段多是高阶函数。

这样就可以看出流结构是一门语言是函数式的根本,流结构的实现依赖于表达式的延时求值,没有延时求值功能的语言绝对不是函数式语言,所以 Swift 根本不是函数式语言。

带有函数式功能的过程式语言和带有赋值功能的函数式语言说到底是整个世界观的不同。将延时求值和赋值带来的变动性合理的结合起来这一目标还仅仅停留在理论研究领域。

注释和共享

八皇后问题是求在八行八列的国际象棋棋盘上放置八个皇后,令她们彼此之间不能相互被吃的所有方法。国际象棋中皇后可以顺着横竖对角线方向行进任意距离。

高阶函数是泛指那些以一个函数(或者称之为一个过程)作为参数的函数,这个问题里用到的标准库里自带的 map flatmap filter reduce

在函数式编程思路中高阶函数在建立抽象和模块化过程中起到了很重要的作用,以 map 为例它将对一个序列的操作抽象出来,使序列本身和对序列的操作分割开来,这样做的好处是方便重用这种操作,也方便更换序列所需要进行的操作,为了实现这两点在常用的命令式写法中都是要整个操作重写才能完成。

高阶函数的组合使用可以更好的体现模块化的思想,高阶函数本身是模块与模块之间的接口,例如得到一个序列中的偶数的平方的序列:

1
2
let a = Array(0...100)
let b = a.filter({$0%2 == 0}).map{$0*$0}

模块化的好处自然是替换模块整体结构不变,也就是维护方便。

函数式编程思路解决问题的一般思路都是递归,逐步将问题分解求解。在解八皇后问题过程中递归的思路是 k-1 列已经摆放好 k-1 个皇后,通过 map 得到第 k 列的所有可能解,通过 flatmap 整理解类型,最后 filter 过滤出满足条件的那些解。

reduce 函数用在 filter 的判断是否满足条件的模块中,这个例子里似乎很好的体现了在某些情况中命令式写法可以更高效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct NQueensProblem {
private let size: Int

init(boardSize: Int) {
//size start from 1
size = boardSize>0 ? boardSize : 1
}

func solutions() -> [[(Int, Int)]] {
func isSafe(solution: [(Int, Int)], atColumn column: Int) -> Bool {
let (colX, colY) = solution[column]
return solution.reduce(true, combine: { (isSafe, location) -> Bool in
let (locX, locY) = location
if locX == colX && locY == colY {
return isSafe
} else {
return isSafe &&
!(locX == colX || locY == colY || (locX+locY) == (colX+colY) || (locX-locY) == (colX-colY))
}
})
}

//column start from 0
func queenCols(column: Int) -> [[(Int, Int)]] {
if column == 0 {
return Array(0..<size).map{ [(0, $0)] }
} else {
return queenCols(column-1).map({ (partSolution) -> [[(Int, Int)]] in
return Array(0..<size).map { partSolution + [(column, $0)] }
}).flatMap({ $0 }).filter{ isSafe($0, atColumn: column) }
}
}

return queenCols(size-1)
}
}

var queen = NQueensProblem(boardSize: 8)
print(queen.solutions())

最后当n等于8时一共有92个解法

最后的最后,在 Swift 2.0 之后 flatmap 有了一个特殊用途:过滤nil

1
2
3
4
let optionalInts: [Int?] = [1, 2, nil, 4, nil, 5]
 
let ints = optionalInts.flatMap { $0 }
ints // [1, 2, 4, 5]

reference: https://www.natashatherobot.com/swift-2-flatmap/

注释和共享

这个世界上所有事物都是相对的,只有「相对」本身是绝对的

接盘侠日记

最屌文件命名

曾经有一个合作的设计师出了一套新版本界面设计稿,她新建了一个文件夹打包上传到内部 GitLab repo ,我 pull 下来看到这个文件夹

image

这是我目前看到过最屌的命名,于是我想下一个版本的设计稿文件夹她会起什么名字:「目前最最新的稿子」?「比目前最新的稿子更新的稿子」?「未来最新的稿子」?无论选择这其中的哪一种方案都会有一个共同特点,那就是下一次的起名都必须依赖于这一次的名字,以用来表明这个文件夹更新,而这种依赖是递增不可绕过的,比如说选用第一种方案那么到下下下下个版本就是「目前最最最最最最新的稿子」,以此类推这显然是一个灾难。当然实际中我们的设计师并不会这样,更常见的情况是下一次她的命名直接进入另一个次元,「稿子新」比「目前最新的稿子」更新,这样就可以区分出哪个更新,现在的使用者是清楚了可是接盘侠呢,果然光荣与伟大并不是那么得容易担当。

绝对和相对

当需要设定某种唯一标识的时候,绝对的概念能够更明确的定位。当需要描述一种关系的时候,相对的表述方法更加适合。

相对和绝对路径是一个直观的例子。

1
2
/Users/fengweizhou/Documents/dopcnblog/source/_posts/absolute-vs-relativity.md
source/_posts/absolute-vs-relativity.md

绝对路径则是由根目录开始一层一层明确写出到达目标文件的完整路径。相对路径可以直接用文件名引入同一个文件夹中同级的文件,用 ../ 代表上一级目录。显然两种不同用法在不同的环境中各有优势,在决定使用哪一种用法之前能够明确区分两种方法的不同很重要。

其他绝对和相对的例子

绝对和相对的界面构建

界面布局的相对和绝对。在这个领域「相对」有压倒性的优势,在浏览器端响应式网页应该是如今网站建设的标配,除了流量特别大的网站可能会为了特别定制将移动端网页分出去。使用 CSS 进行网页布局可以分为三个阶段:手写 CSS -> 用 Sass 写 CSS -> 用 Sass 写 Flexbox。在阶段一是使用「绝对」的方式写 CSS,这样依然可以写出「相对」的布局


HTML 文档在布局时天生就是「相对」的,父元素子元素间相对,同级元素之间的相对。但是这种相对布局的规则是由开发者提前「绝对」写死的。进入阶段二,这个阶段 Sass 为 CSS 引入了编程特性,程序员可以像用编程语言一样写 CSS ,于是写 CSS 的方式变为「相对」。

进入阶段三 Flexbox 模型将布局规则抽象为指令,开发者只要列出应该怎样布局剩下的大部分都交给了浏览器去计算,开发者写出的规则也变成「相对」的了。

iOS 设备上的界面构建技术稍落后于前端不过遵循了同样的路径。从只有一种屏幕大小的时代手写固定的 CGRect,到在 Size Class 中建立 AutoLayout 约束规则,这样编写出的约束规则依然是绝对的,最后再到使用 UIStackView 布局减少了许多需要手动设置 AutoLayout 的步骤。对比最初的手写固定 CGRect 越来越相对。

页面转换路径的相对绝对

我之前合作的产品经理同时负责产品的网页端和客户端,所以可能就是因为这个原因在客户端的设计过程中页面转换逻辑几乎是按照网页端的来,网页端的页面转换是链接跳转,类似于利用指针访问可以任意跳转,相比之下客户端的页面转换逻辑大多时候是后进先出的栈结构。再加上以前页面转换逻辑的写法相对绝对

1
2
let vc = SomeViewController()
navigationController?.pushViewController(vc, animated: true)

没少为设计方案来回讨论。后来为了为了尽可能适应这种网页端转换逻辑同时也扩大转换的自由度增加了URLTransformer 层,简单的原型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
private protocol URLTransFormer {
func canTransform(url: NSURL) -> Bool
func transform(url: NSURL) -> UIViewController
}

//======================
//transformer list start

private struct Page1Transformer: URLTransFormer {
func canTransform(url: NSURL) -> Bool {
if url.scheme == "mydomain" {
return true
}
return false
}
func transform(url: NSURL) -> UIViewController {
return SomeViewController(url: url)
}
}

//tranformer list end
//===================

struct URLTransformer {
private let transformerList = [Page1Transformer()]
func transform(url: NSURL) -> UIViewController? {
for transformer in transformerList {
if transformer.canTransform(url) {
return transformer.transform(url)
}
}
return nil
}
}

这样页面转换逻辑就变成相对的,客户端同一个按钮可以根据服务器返回的链接形式打开不同的页面。这里服务器返回的链接一定要是绝对的完整路径,因为这个链接是在做一个唯一性的标识。

描述一种相对的关系

程序运行逻辑里有许多部分是要描述一种关系,例如注册页面在用户名密码通过格式验证之后提交按钮才可用

1
2
3
4
5
6
7
8
9
10
11
12
13
import ReactiveUIKit
import ReactiveKit

……

combineLatest(usernameField.rText, passwordField.rText).map { username, password in
guard let name = username, let pass = password else {
return false
}
return name.characters.count > 7 && pass.characters.count > 7
}.bindTo(submitButton.rEnabled)

……

简单地使用用户名和密码都必须大于7位做验证条件,这个验证的 true false 和按钮 enable 状态的true false 之间是一种对应关系,如果用常用的赋值方法来每次改动这个值,可以想象条件分支会非常多,相对而言会不容易维护。这里直接描述对应关系使用的是第三方库 ReactiveKit,除了这个还有其他一些可以实现类似功能的库,不过达到的效果是类似的。

注释和共享

1. 排序过的数组遍历更快

实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
let sorted = [false, true]

for isSorted in sorted {
var datas = Array(count: 32768, repeatedValue: 0).map { (n) -> Int in
return n + Int(arc4random_uniform(UInt32(256)))
}
if isSorted {
datas.sortInPlace(<)
}
let start = NSDate()

var sum = 0
for _ in 0...100000 {
for n in datas {
if n > 128 {
sum += n
}
}
}

print("Time elapsed when \(isSorted ? "sorted":"unsorted"): \(NSDate().timeIntervalSinceDate(start))")
}

输出

1
2
Time elapsed when unsorted: 14.1824740171432
Time elapsed when sorted: 2.9244259595871

重复运行几次之后可以稳定重现这个时间差,所以这个现象存在,只是差距没有问题来源中的例子里那么大,问题来源中除了被标记为接受的答案之外还有许多高票回答,是我在SOF见过的有最多多个高票答案的问题。简单的解释造成这个问题的原因,是因为现代处理器在处理循环内的 if 判断的时候不是等待上一个 if 结束才进行下一个 if 条件判断,而是预先做判断回过头来如果错了再重来,如果对了就继续。这个例子中数组中的数据值刚好是以 if 条件划分为两部分,如果经过了排序那么预测的正确率就会大大提升,因为用前面的判断结果做为预测,而如果未经排序预测的结果几乎有一半都是错的自然大大降低运行速度。

这个问题有一个很有趣的变形,用三元运算符替换 if 分支,这样 for 循环内部变成这样

1
2
3
4
5
for _ in 0...100000 {
for n in datas {
sum += n>128 ? n : 0
}
}

数据保持同样,运行输出

1
2
Time elapsed when unsorted: 3.60081201791763
Time elapsed when sorted: 3.55997401475906

在面对分支做预测的过程中如果预测错会有很大的延迟,如果一直预测正确则运行过程可以类似并行一般快速运行。三元运算符转化为操作介于两者之间他会每次等一小下,这样不会有大的延迟发生但是比始终预测正确要慢。这或许是许多语言中包含这个唯一的三元运算符的原因之一。

问题来源
http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

2. Denormal number

实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
let floating = [false, true]

for isFloat in floating {
let x = [1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,2.0,2.1,2.2,2.3,2.4,2.5,2.6]

let z = [1.123,1.234,1.345,156.467,1.578,1.689,1.790,1.812,1.923,2.034,2.145,2.256,2.367,2.478,2.589,2.690]

var y = Array(count: 16, repeatedValue: 0.0)

for (index, n) in x.enumerate() {
y[index] = n
}

let start = NSDate()
for j in 0...9000000 {
for i in 0...15 {
y[i]*=x[i]
y[i]/=z[i]
if isFloat {
y[i]=y[i]+0.1
y[i]=y[i]-0.1
} else {
y[i]=y[i]+0
y[i]=y[i]-0
}
if j == 100000 {
print("\(y[i]) ")
}
}
}
print("Time elapsed when \(isFloat ? "floating":"unfloating"): \(NSDate().timeIntervalSinceDate(start))")
}

输出

1
2
3
4
5
6
7
8
……
9.38724727098368e-323
7.90505033345994e-323
Time elapsed when unfloating: 15.5163140296936
……
1.94289029309402e-16
1.94289029309402e-16
Time elapsed when floating: 0.695216000080109

这个例子里面造成时间差异的是 Denormal number ,Double 类型数据的范围大约是1.79769e+308 ~ 2.22507e-308,在上面的输出里如果加减 0 后面得到的数据在计算机里的表示9.38724727098368e-323是在这个类型的范围之外的,这种数据就是 Denormal number,在实际使用的过程中这种数据出现的可能很小,所以处理器对这种数据的处理会比较慢。

问题来源
http://stackoverflow.com/questions/9314534/why-does-changing-0-1f-to-0-slow-down-performance-by-10x

3. Loop interchange

实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var data1 = Array(count: 10000, repeatedValue: Array(count: 10000, repeatedValue: 0))
let start1 = NSDate()
for i in 0..<10000 {
for j in 0..<10000 {
data1[i][j] = i+j
}
}
print("Time elapsed: \(NSDate().timeIntervalSinceDate(start1))")
var data2 = Array(count: 10000, repeatedValue: Array(count: 10000, repeatedValue: 0))
let start2 = NSDate()
for j in 0..<10000 {
for i in 0..<10000 {
data2[i][j] = i+j
}
}
print("Time elapsed: \(NSDate().timeIntervalSinceDate(start2))")

输出

1
2
Time elapsed: 1.00041896104813
Time elapsed: 4.22464299201965

从这个结果来看可以初步推测 Swift 和 C 一样是 row-major order,也就是二维数组中同一行的数据顺序存储,这种存储形式在按列读写数据的时候会出现很多处理器的 cache misses 从而相对增加了操作需要的时间。

问题来源
http://stackoverflow.com/questions/9936132/why-does-the-order-of-the-loops-affect-performance-when-iterating-over-a-2d-arra

注释和共享

对于常见的过程式编程语言赋值行为和定义变量是同一种形式,都是用等号进行。对于函数式编程语言来说定义和赋值有着显著区别。

由于过程式编程更”容易”进行赋值所以经常采用在整个作用过程中使用起记录作用的状态变量,用一个获取 Fibonacci 前N 项中偶数的函数做示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func evenFibs1(n: Int) -> Array<Int> {
var result = Array<Int>()
var x = 0, y = 1, count = n
result.append(0)
while count > 2 {
(x, y) = (y, x+y)
if y%2 == 0 { result.append(y) }
count--
}
return result
}

func evenFibs2(n: Int) -> Array<Int> {
func fib(n: Int) -> Int {
var tmpArray = [0, 1]
func fib2Inside(m: Int) -> Int {
if m >= tmpArray.count {
tmpArray.append(fib2Inside(m-1) + fib2Inside(m-2))
}
return tmpArray[m]
}
return fib2Inside(n)
}
func isEven(n: Int) -> Bool {
if n%2 == 0 { return true }
else { return false }
}
return Array<Int>(0..<n).map(fib).filter(isEven)
}

方法一中使用一个局部变量作为盛放结果的容器,不断将这一变量赋值为新的值,在方法的最后返回这个值,而方法二则是直接作用于一个数组得到结果。

这两种方法对比,显然方法一的效率更好一些,方法二是在模块化的方面更显著一些,模块化意味着这个方法很容易抽象为一个对数组每个值作用然后过滤的函数,作用函数和过滤函数都可以轻易的更换,而方法一的变更就没有那么容易了。事实上方法二里面的 fib 函数为了求值效率是按照方法一的思路实现的。

因为使用赋值带来的另一个区别是,过程式编程语言中不同语句之间的顺序对于程序正确运行来说很重要,对比求阶乘的两种写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func factorial1(n: Int) -> Int {
var product = 1, counter = 1
while counter <= n {
product = counter*product
counter+=1
}
return product
}

func factorial2(n: Int) -> Int {
func iter(product product: Int, counter: Int) -> Int {
if counter > n {
return product
} else {
return iter(product: counter*product, counter: counter+1)
}
}
return iter(product: 1, counter: 1)
}

方法一中while循环里的语句是绝对不能调换位置的。说明这个问题的一个更好的例子是,下面这两种定义 x y 的方法

1
2
3
4
5
y = x * 2
x = 3

x = 3
y = x * 2

在函数式语言中两种定义方法定义出的 x y 值是一样的,而一般的过程式语言则要看第一种定义方法之前 x 的值是什么才能决定 y 的值。

注释和共享

由编程语言自带的数据结构种类有限,在解决实际问题中设计适和的复合数据类型更有利于程序的组织和迭代。复合数据的分层设计一般可以分为三层:最底层是复合数据的实现,上层是复合数据的使用方法,最上层是复合数据使用方法的应用。

在这个例子中,最底层使用数组作为数独数据的实现,在上层使用 struct 的初始化函数、subscript 中的 getter 和 setter,最后基于getter和setter实现数独求解的各个步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
enum SudokuError: ErrorType {
case initDataError
case invalidSudoku
case subscriptOutOfRange
}

struct Sudoku: CustomStringConvertible {

private var data = Array<Int>()

init(array: Array<Int>) throws {
guard array.count == 81 else { throw SudokuError.initDataError }
data = array
}

func isRangeValid(row: Int, column: Int) -> Bool {
return 0 <= row && row < 9 && 0 <= column && column < 9
}

subscript(row: Int, column: Int) -> Int {
get {
return data[row*9+column]
}
set {
data[row*9+column] = newValue
}
}

mutating func solve() throws {
var emptyCells = Array<(Int, Int)>()
for i in 0...8 {
for j in 0...8 {
if self[i, j] == 0 {
emptyCells.append((i, j))
}
}
}

var index = 0
while index < emptyCells.count {
let (a, b) = emptyCells[index]
if self[a, b] < 9 {
self[a, b]++
if isSafe(a, y: b) {
index++
}
} else {
self[a, b] = 0
index--
}
if index < 0 { throw SudokuError.invalidSudoku }
}
}

func isSafe(x: Int, y: Int) -> Bool {
return isRowSafe(x, y: y) && isColumnSafe(x, y: y) && isCellSafe(x, y: y)
}

private func isRowSafe(x: Int, y: Int) -> Bool {
for i in 0...8 {
if i != y && self[x, y] == self[x, i] { return false }
}
return true
}

private func isColumnSafe(x: Int, y: Int) -> Bool {
for i in 0...8 {
if i != x && self[x, y] == self[i, y] { return false }
}
return true
}

private func isCellSafe(x: Int, y: Int) -> Bool {
let a = x/3, b = y/3
for i in 3*a...(3*a+2) {
for j in 3*b...(3*b+2) {
if i != x && j != y && self[x, y] == self[i, j] { return false }
}
}
return true
}

var description: String {
var output = ""
for i in 0...8 {
for j in 0...8 {
output.appendContentsOf("\(self[i,j]) ")
if j == 8 {output.appendContentsOf("\n")}
}
}
return output
}
}

do {
let data = [0,9,0,4,2,0,0,7,0,
0,4,0,0,0,7,0,0,2,
0,0,7,0,0,0,1,0,6,
7,0,0,0,0,2,0,0,0,
0,0,0,6,0,5,0,0,0,
0,0,0,3,0,0,0,0,4,
4,0,1,0,0,0,5,0,0,
9,0,0,2,0,0,0,1,0,
0,6,0,0,3,9,0,2,0]
var theSudoku = try Sudoku(array: data)
try theSudoku.solve()
print(theSudoku)
} catch SudokuError.initDataError {
print("The count of init array isn't 81")
} catch SudokuError.invalidSudoku {
print("This is not a valid sudoku")
}

对比以前写过的版本,这个实现多出了 subscript 中的 getter setter 方法,增加这两个方法隔离开了解数独的过程和实现数独数据的具体细节,假如要换一种数独的实现方式,只需要修改其中的构造函数和 subscript 其他函数例如 solve() 完全不需要改动,这就是复合数据抽象的好处。

注释和共享

用过程复合数据

发布在 计算机科学

复合数据只要拥有满足一定条件的构造函数、选择函数和约束规则,甚至不需要是由基本数据复合,church 计数是一个以 lambda 表达式为唯一元素,构建数值、数值运算等编程要素的系统,在church 计数中 0 和 加1 运算分别被定义为

1
2
3
4
5
6
7
8
9
10
11
12
func zero<T>(f:(T->T)) -> T->T {
return {x in
return x}
}

func add_1<T>(n:(T->T) -> T->T) -> (T->T) -> T->T {
return {f in
return {x in
return f(n(f)(x))
}
}
}

0 是一个以函数为参数返回一个函数的过程,加1 运算是作用于类似 0 这样的过程之上返回一个新过程的函数,将 0 带入 加1 运算得到 1 的定义,带入 1 得到 2 的定义

1
2
3
4
5
6
7
8
9
10
func one<T>(f:(T->T)) -> T->T {
return {x in
return f(x)}
}

func two<T>(f:(T->T)) -> T->T {
return {x in
return f(f(x))
}
}

形式上讲 church 计数的正整数可以看做应用参数函数的过程,0 是应用 0 次直接返回原值,1 是返回应用 1 次得到的返回值,以此类推。加法的定义是先应用第一个加数次,再应用第二个加数次,乘法是应用次数之积次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func plus<T>(operand1 operand1: (T->T) -> T->T, operand2: (T->T) -> T->T) -> (T->T) -> T->T {
return {f in
return {x in
return operand2(f)(operand1(f)(x))
}
}
}

func mult<T>(operand1 operand1: (T->T) -> T->T, operand2: (T->T) -> T->T) -> (T->T) -> T->T {
return {f in
return {x in
return operand2(operand1(f))(x)
}
}
}

减法的定义先考虑简单的情况,任意给定一个过程进行减 1,从概念上讲应该是应用给定过程的减 1 次,实现方法:

我没想出来

注释和共享

构建过程抽象

发布在 计算机科学

3)将有关认识与那些在实际中和他同在的所有其他认识隔离开,这就是抽象

SICP 第一章

现存的许多威力强大的程序设计技术,都依赖于填平在「被动的」数据和「主动的」过程之间的传统划分

SICP 第一章

计算机程序是由需要被操作的「数据」和操作数据的「过程」构成。解释起来可以说是一静一动,数据所代表的静态的具体某个值,而过程则是动态的代表从一个值到另一个值的转化。和数学研究很像不光研究函数对值的作用,还研究函数本身,计算机编程过程中也不光用过程作用于数据,也可以处理过程本身就像作用于数据之上那样。

过程作为参数

通过区间折半寻找方程的一个根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
enum searchError: ErrorType {
case sameSign
}

func isCloseEnough(x x: Double, y: Double) -> Bool {
return abs(x-y) < 0.001
}

func search(function f: (Double)->Double, negPoint: Double, posPoint: Double) -> Double {
let midPoint = (negPoint+posPoint)/2
if isCloseEnough(x: negPoint, y: posPoint) {
return midPoint
} else {
if f(midPoint) < 0 {
return search(function: f, negPoint: midPoint, posPoint: posPoint)
} else {
return search(function: f, negPoint: negPoint, posPoint: midPoint)
}
}
}

func halfIntervalSearch(function f:(Double)->Double, x: Double, y: Double) throws -> Double {
let a = f(x), b = f(y)
if a > 0 && b < 0 {
return search(function: f, negPoint: y, posPoint: x)
} else if a < 0 && b > 0 {
return search(function: f, negPoint: x, posPoint: y)
} else {
throw searchError.sameSign
}
}

func f(x: Double) -> Double {
return x*x*x - 2*x - 3
}



do {
let result = try halfIntervalSearch(function: f, x: 1, y: 2)
print(result)
} catch {
print("error")
}

其中函数 f 作为参数可以换成其他形式

过程作为返回值

函数求导

1
2
3
4
5
6
7
8
9
10
func deriv(function f:(Double)->Double) -> (Double)->Double {
let dx = 0.00001
return {(x:Double)->Double in (f(x+dx)-f(x))/dx}
}

func cube(x:Double) -> Double {
return x*x*x
}

deriv(function: cube)(2)

过程的单一责任原则

过程是可以复合定义的,良好的定义应当保持各部分的解耦,例如第一个例子中对 isCloseEnough 过程的调整就可以做到完全不影响其他过程。

注释和共享

每一个计算机程序都是现实中或者精神中的某一个过程的一个模型

SICP 序

在这一层次的课程里,最基本的材料并不是特定的程序设计语言语法,不是有效计算某种功能的巧妙算法,也不是算法的数学分析或者计算的本质,而是一些能够用于控制大型软件系统的智力复杂性的技术

SICP 前言

计算机程序中对象可以大体分为两类:数据和过程。数据是那些需要去操作的东西,过程则是具体操作的指令。要求解复合过程的结果需要先得到子过程的结果,求子过程的结果需要得到子过程的子过程的结果,一次类推直到某一层子过程是最基本的表达式得到求值结果,这就是递归。

递归的简单应用,欧几里得算法求最大公约数

1
2
3
4
5
6
7
func gcd(x x: Int, y: Int) -> Int {
if y == 0 {
return x
} else {
return gcd(x: y, y: x%y)
}
}

Fibonacci 数列求值

Fibonacci 数列的定义本身就是递归的,可以很自然的写成:

1
2
3
4
5
6
7
func fib1(n: Int) -> Int {
switch n {
case 0: return 0
case 1: return 1
default: return fib1(n-1) + fib1(n-2)
}
}

这个方法在求解的过程中所需的步数随着n的增加增长阶是O(2^n),仔细观察递归过程中同样的值重复计算了很多次,于是可以优化在计算过程中把结果保留下来,这种做法被归类为 Dynamic Programming 方法,没想到的是中文翻译居然是动态规划

1
2
3
4
5
6
7
8
9
10
func fib2(n: Int) -> Int {
var tmpArray = [0, 1]
func fib2Inside(m: Int) -> Int {
if m >= tmpArray.count {
tmpArray.append(fib2Inside(m-1) + fib2Inside(m-2))
}
return tmpArray[m]
}
return fib2Inside(n)
}

在递归中有一类尾递归,可能也可以叫伪递归,是在递归的过程中保留全部状态,其实就是一种迭代,这种计算方式要快于一般的递归。如果递归解决的思路是从后往前的,那么迭代刚好相反是从前往后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func fib3(n: Int) -> Int {
func fibIter(a: Int, b: Int, count: Int) -> Int {
if count == 0 {
return b
} else {
return fibIter(a+b, b: a, count: count-1)
}
}
return fibIter(1, b: 0, count: n)
}

func fib4(n: Int) -> Int {
guard n > 1 else {
return n
}
var count = n, x = 0, y = 1
repeat {
(x, y) = (y, x+y)
count--
} while count > 1
return y
}

使用迭代的方式计算,计算步数相对于n的增长阶是O(n),如果要继续精简这个计算过程发现每次迭代的变化都是一样的,那么将两次迭代的过程合为一次,那么所需步骤数就可以减半,最后得到时间复杂度为 O(logn) 的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func fib5(n: Int) -> Int {
guard n > 1 else {
return n
}
var count = n+1, x = 0 , y = 1
if count % 2 != 0 {
(x, y) = (y, x+y)
count--
}
var countHalf = count/2
repeat {
(x, y) = (x+y, x+2*y)
countHalf--
} while countHalf > 1
return y
}

零钱组合问题

给定一个金额 N,计算有多少种不同的零钱组合方式。这个问题应用递归就没有上一个那么直观,但只需要找出分解问题并且子问题和问题本身是同一类问题的方式。将换算组合个数分为两部分,没有一种面值的组合个数加上至少有一张这种面值的组合个数

1
2
3
4
5
6
7
func cc1(amount: Int, denomination: Array<Int>) -> Int {
if amount < 0 || denomination.count == 0 { return 0 }
if amount == 0 { return 1 }
var deno = denomination
deno.removeLast()
return cc1(amount - denomination[denomination.count-1], denomination: denomination) + cc1(amount, denomination: deno)
}

在 Dynamic Programming 的思想下优化,用一个表的行列代表金额数和不同面值个数,在表中存储计算过的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func cc2(amount: Int, denomination: Array<Int>) -> Int {
var table = Array(count: amount+1, repeatedValue: Array(count: denomination.count+1, repeatedValue: -1))
var i = 0, j = 0
while j < denomination.count+1 {
table[0][j] = 1
j++
}
while i < amount+1 {
table[i][0] = 0
i++
}
func cc2Inside(amount2: Int, denomination2: Array<Int>) -> Int {
if amount2 < 0 {
return 0
}
if table[amount2][denomination2.count] == -1 {
var deno = denomination2
deno.removeLast()
table[amount2][denomination2.count] = cc2Inside(amount2-denomination2[denomination2.count-1], denomination2: denomination2) + cc2Inside(amount2, denomination2: deno)
}
return table[amount2][denomination2.count]
}
return cc2Inside(amount, denomination2: denomination)
}

这个问题也可以迭代,但是我是没能想出来,搜到的一种做法是

1
2
3
4
5
6
7
8
9
10
func cc3(amount: Int, denomination: Array<Int>) -> Int {
var table = Array(count: amount+1, repeatedValue: 0)
table[0] = 1
for(var i=0; i<denomination.count; i++) {
for(var j=denomination[i]; j<=amount; j++) {
table[j] += table[j-denomination[i]]
}
}
return table[amount]
}

显然相比之下递归的代码更容易读懂

注释和共享

有关动力的模型

发布在 其他

缘起

可能和许多人一样我也有一些曾经想要学习然而却最终没有去进行学习的目标,需要举起例子的话很容易,不过我更想弄明白的是这些例子背后共通的原因。这就引发了我对动力的思考。

什么是动力?

首先先建立一个认识模型:

一个人的精神活动由两部分组成:一是由大脑皮层控制的理性,二是由大脑内部脑干等控制的感性。

简单的对这两个组成部分进行一个解释:

理性,是一个人在后天的生活环境中通过社会环境的潜移默化和自己的主动学习培养起来的用于控制自己的一种能力,比如各种道德观念,有的时候可以称之为意识。

感性,是一个人继承自生物本能的应对外界刺激的能力,比如情绪,也可以称之为潜意识,但我理解这里所使用的潜字并不是隐藏起来的意思,而是虽然知道他的存在却不能直接操纵的意思。

理性是人可以直接操控的。例如,一个人在面领两个不同选择时会理性的选择更有利于自己的一个。而感性的控制则需要理性的间接操作。例如,你不可以直接控制自己的喜怒哀乐(情绪),但是可以通过做自己喜欢的事情激发自己的喜悦。

基于这个模型,我认为一个真正能有效驱动自己的动力应该是两方面的,它即是理性上应该做的,也是感性上想要做的。应该做反映在是否有利,想要做反映在是否能够为自己带来正面的情绪。

如果说动力就是一个目标或者因这个目标诞生的一个理由,那么一个动力一个大的目标就需要有两个子目标,才能构成一个完整的动力。一个目标是建立在外部标准之上的理性选择,比如说金钱、title;另一种目标是建立在自己的内部标准之上的是可以激发自己感性力量的,比如说是一件有趣的事。外部标准是明确的可以量化的,人人都看得懂理解得了,但内部标准恐怕往往会在别人眼里是觉得可笑的没有意义的。当我们在谈论一个目标的时候绝大多数情况下我们都是在谈论理性的目标,基于量化标准的成功,那么为什么激发自己感性力量是一个有效目标不可或缺的一部分?我认为这是因为两种力量对于人的控制理性胜在选择,感性胜在驱动,真正在起到驱动作用的其实是一个人感性的部分。在临近考试的时候你可以理性地选择挑灯夜战,但是这样的状态可以持续多久?而如果你是在做一件令你激动的事情(感性上的作用),比如打游戏刷剧,那么通宵达旦恐怕都在一瞬间。过度依赖理性的力量,你可以做出正确的事情,但是这个过程你很难去坚持,即使能够坚持在做这件事的过程中你也一定不爽;过度依赖感性的力量,你会沉迷,仅有情感性的刺激也同样是不能持续的。

动力的缺失

制定一个理性的目标是非常简单的,因为理性的目标只是一个基于明确标准的选择。但是如前面所想到的理性的目标并不能构成一个有效的完整动力,纯粹理性作用的结果就往往是你知道自己应该做什么却不想去做,悬梁刺股的刻苦可以为你带来好的结局然而你是否想过这样的结果是你真的想要的吗,功不唐捐的自我安慰真的可以替代你内心的情感需要?

在从小到大的受教育过程中,学到的大多是关于如何做出选择的知识,甚至学校老师在教育的过程中也在做着做出理性选择的表率,决定哪些是需要重视的主课哪些是一笔带过的副科。在初中的时候我曾经觉得一门副科很有趣,然而这种心态在老师那里只不过是参加相关竞赛的一个契机,最终不了了之。

理性的正确应用

前面说到真正起到驱动作用的是感性的力量,也就是说理性并不是全部也并非全能。但是这个地方特别需要注意的是这种理性并非全能的认识正是理性本身做出的,这种能够正视和承认自身缺陷的能力才是理性最强大的地方。

注释和共享

Dopcn

一名软件工程师
目前工作的主要平台是iOS


软件工程师


杭州