TRA

TRA-1

TRA 是简化版的 ARTS, 周期是两周一次。其中

  • T 是 Tip, 总结和归纳日常中遇到的知识点.
  • R 是 Receive, 新知识的输入(技术、理财、哲学、文化等)都算在内.
  • A 是 Algorithm, 算法小练习.

Tip: 同步 UIView animation 和 CALayer animation

问题来源

自己在开发一个需求的过程中遇到了这样的问题:

之前有实现好有一个内部通过 CAShaperLayer 绘制 path 的封装好的 UIView. 现在要在这个 view 上实现一个动画效果: 同时动画方式改变这个 view 的 frame/transform 和内部的 path.

1
2
3
4
5
6
7
class MyView: UIView {
  private let pathLayer = CAShapeLayer()
  
  func setPath(_ path: CGPath?) {
    pathLayer.path = path
  }
}

最开始的尝试方式:

  • 针对 view 的 位置动画, 使用 UIView.animate(withDuration:animations:).
  • 针对 layer 的 path 动画, 手动创建 CABasicAnimation, 并 add 到 layer 上. 之所以用 explicit animation, 是因为:
    虽然 CAShaperLayer 的 path 是标记成 animatable 的, 但是和 layer 的其他属性(例如 bounds 等)不同, 直接设置 path 是不会产生 implicit animation 的. 这两点都在文档中有明确标明.
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
class MyView: UIView {
  private let pathLayer = CAShapeLayer()
  
  func setPath(_ path: CGPath?) {
    let animation = CABasicAnimation(keyPath: "path")
    animation.fromValue = pathLayer.presentationLayer!.path
    animation.toValue = path
    animation.duration = 0.2
    pathLayer.add(animation, forKey: "animatedPath")
    pathLayer.path = path
  }
} 

/// 动画调用
extension MyView {
  func performAnimation() {
    UIView.animate(withDuration: 0.2) {
      self.frame = // new frame
      self.transform = // new transform
      
      // option 1: setPath 写在 animation block 里
      self.setPath(/* new path */)
    }
    // option 2: setPath 写在 animation block 外
    self.setPath(/* new path */)
  }
}

然而仅仅这么做会导致 view 和 layer 的 animation 无法同时作用

  • 有时候是出现了启动的时间差
  • 有时候是一个 animation 吃掉了另一个 animation, UI 上出现突变而不是 2 个动画同时进行

解决办法

考虑到 UIView.animate() 本质上就是依靠

  • UIView 设置自己成为 self.layer 的 delegate, 并且
  • 在 animation block 调用期间, 针对不同的 property 变化通过 CALayerDelegate 中的 action(for:forKey:) 提供 implicit animation

来实现的. 而既然 UIView.animate() 可以把一系列 animation 同时启动, 我们只需要也用类似的方式, 在同样的时刻提供 path 动画即可. 而想要参与 layer 的 implicit animation 的自定义过程, 有多种途径, 例如:

  • 实现自定义的 layer subclass, 重写 defaultAction(forKey:)
  • 给单独的 layer 增加 delegate, 重写 action(for:forKey:)
  • 实现自定义的 view subclass, 指定 layerClass, 并重写 action(for:forKey:)

等. 以下以单独增加 delegate 为例子.

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
class MyView: UIView {
  private let pathLayer = CAShapeLayer()

  private class CustomLayerDelegate: NSObject, CALayerDelegate {
    func action(for layer: CALayer, forKey event: String) -> CAAction? {
      guard event == "path" else { return nil }
      
      let animation = CABasicAnimation(keyPath: event)
      animation.fromValue = layer.presentationLayer!.path
      animation.toValue = path
      animation.duration = 0.2
      return animation
    }
  }
  private let pathLayerDelegate = CustomLayerDelegate()

  init(frame: CGRect) {
    super.init(frame: frame)
    pathLayer.delegate = pathLayerDelegate
  }

  func setPath(_ path: CGPath?) {
    pathLayer.path = path
  }
}

/// 动画调用
extension MyView {
  func performAnimation() {
    UIView.animate(withDuration: 0.2) {
      self.frame = // new frame
      self.transform = // new transform
      self.setPath(/* new path */)
    }
  }
}

这样每次在 UIView.animate() 的 animation block 中如果更改了 layer 的 path, 就会自动产生一个 implicit animation, 并且能和其他 view animation 并行产生作用.

Receive: Swift Concurrency

关于 Swift 中新的并发编程特性的讨论已经在官方 forums 持续好多年了, 我个人也一直抱有浓厚的兴趣. 上周, Swift core team 终于正式以 1 篇 road map 和 4 篇 proposal 初稿隆重为各位 Swift 爱好者铺展开将会持续未来多个版本的道路. 虽然这些文档仍在积极讨论中, 和终稿相比想必会有很大的不同, 但我坚信, 相关的思想和观念将是一名优秀 Swifter 以后绕不开的宝库.

对于 iOS 开发者而言, 异步编程是再熟悉不过了, 平时日常开发中即使不涉及到多线程通信的问题, 也至少懂得"繁琐操作不应该 block 主线程"的道理. 而这次 Swift team 带来的 proposal 不但能免去我们开发者平时遇到的一些烦恼, 也能在更高的 level 上系统化地解决并发编程中的一些基本问题.

这里无法详述所有细节, 仅将相关 proposal 的主旨摘录于下:

  • Async/await 为语言引入了一种新的 function: async function (包括 method).
    • Async function 与普通 function 是两个世界, 无法互相调用, 只能在各自的 context 中调用.
      • 声明方式 func asyncFunction(_ input: Int) async -> Int .
      • 调用方式 let result = await asyncFunction(10).
    • Async function 调用后, 只能异步地返回.
      • 从语法角度, 可以认为 async function 是带 callback block 的普通 function 的语法糖.
      • 从语义角度, async 是协程 (coroutine) 的应用: 在 async context 下每次 await, 都产生了断点, 当前协程中断, 直到被调用的 async function 异步完成时, 才会把返回值提供给 caller, caller 协程接着上次断点继续执行.
    • Async function 可以极大简化普通 function 中因为大量使用 callback block 造成的书写问题, 例如:
      • 回调地狱——深层的 callback 嵌套.
      • 数据流容易丢失——使用 callback 时编译器无法保证, 被调方法能一致地返回.
      • try catch 机制无法用于 callback 方法.
  • Async/await 只是引入了最基本的异步语法, 但日常应用需要有更高级的抽象. Structured concurrency 在语言层面增加了许多机制.
    • 虽然 async function 异步执行, 但和普通 function 一样, 在执行过程中, 它与它内部所有 await 的操作也形成自然的树状"父子"结构, 系统可以保证所有子任务不会无故超越父任务的生命期.
      • 支持协作式的 cancellation: 任何子任务被 cancel, 父任务会同步自动进入 cancel 状态, 其他执行中的子任务也可以主动获取到 cancel 信息.
      • 在一个任务中需要多个子任务并发处理的情况下:
        • 可以通过 async let binding 可以并发执行多个 async function, 并在同一的地方 await 多个任务的完成.
        • 也可以通过 Task.Nursery 动态方式开始和结束任意数量的子任务.
    • 在每一个 async function,中 都可以通过系统提供的 Task 类型, 实现许多并发机制.
      • 如上所说, Task.Nursery 可以动态并行开启子任务.
      • 使用 Task.isCancelled() 等方法, 得知当前 task 是否被标记 cancelled.
      • 使用 Task.withDeadline() 和 Task.currentDeadline().remaining 可以开启有时限的任务和检测时限是否已达.
    • Task 还可以联系 async 和 non-async 世界:
      • Task.runDetached() 允许我们从普通的非 async 代码进入一个 async context, 从而可以调用 async function.
      • Task.withUnsafeContinuation() 允许从一个 async context 中临时转移到 non-async context, 执行我们的基于普通 callback block 的代码, 并等待回调.
  • 上面 2 个 protocol 解决了并发编程中的一些效率问题, 而 Actors 可以帮忙解决更困难和危险的问题——如何保证并发下的运行安全. 例如 data race, deadlock.
    • 引入了一种新的 type 类别: actor class.
      • 每一个 actor class 的实例对象, 背后都有一个 “queue” , 语言制定了一些列规则来保证所有该对象的方法默认都只能在该 queue 上执行, 并且当前 actor 的 value semantics 成员都不会被其他 actor 不安全地访问. 从而部分解决了 data race 问题.
        • 要访问的是 stored property 时, 只有当编译器能确保以下条件时, 才允许访问: 或者能保证该 property 是 immutable, 或者能保证访问只发生在 self 上.
        • 要访问的是 non-async 方法时, 只允许在该 method 在 self 上调用, 不允许在别的对象上调用.
        • 要访问的是 async 方法时, 没有限制. 而由于调用者只能异步等待返回, 因此解决了死锁问题.
        • 当然针对不同情况, proposal 也提供了一些手段让开发者帮编译器作强制指定.
      • 对于全局方法, 虽然不在 actor class 内, 但可以给其标记属于某个 global actor, 所有的访问都等价于在这个 actor singleton 上执行.
    • 官方 forums 的 proposal 只针对 value semantics 的类型提供了检查, 而对其他类型的支持将会在以后加入. 这等于在以后版本加强了语言限制, 会导致现在 valid 的 code 以后某个版本不 valid.
      • 社区中针对这一问题, 许多大佬 (比如 Christ Lattner, Dave Abrahams) 提出了另一种策略: Protocol-based Actor Isolation.
      • 这个 proposal 里建议一开始就限制允许在不同 actor 接口间传递的数据的类型, 并允许标准库和开发者有办法让自己的类型满足要求.
  • 最后, Swift 当前的首要用户必然是 ObjC 开发者, 而为 Swift 特性和 ObjC 交互也始终是首要任务之一. 因此将 async/await 甚至 actor 和 ObjC 打通也必然极有意义. Concurrency Interoperability with Objective-C 就给这一块补上了许多支持.
    • ObjC 中编写的基于 callback block 的方法, 在 bridge 到 Swift 时, 除了原有的 API, 符合条件时还会额外生成一个 async API.
    • Swift 中编写的 async API, 用 @objc 暴露给 ObjC 时, 会自动转换成 callback block 形式.
    • Swift 中编写的 actor class, 其 @objc 方法暴露给 ObjC 调用时, 会自动执行在对应 actor 的 “queue” 上.

Algorithm: Substring with Concatenation of All Words

题目

来自 leetcode.

1
2
3
4
5
6
7
8
9
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 
输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

分析

假设待匹配的每个 word 的宽度为 ww.
第一印象使用滑动窗口. 我们只检查字符串在滑动窗口中的部分, 是否是输入 words 的一个连接. 因为 words 都是等宽度的, 所以如果滑动窗口内的部分确实是连接, 那么按 ww 为宽度进行划分后形成的 substring 集合, 必然等价于输入的 words 集合. 使用滑动窗口, 我们就可以一个字符一个字符地考察, 每增加一个字符, 可能产生新的 match.

1
2
3
4
5
6
7
8
// [  ] 对应 word 的宽度

              |-新探测的字符
              v
 xxxxx.....xxxAxxx...
  [  ][  ][  ] 
  ^          ^
  |--window--|

然而, 每次新增字符要检查滑动窗口部分是否 match 了所有的 word 是无需从窗口头部开始重新检查, 有很多数据是可以复用的. 只是这个复用并不是紧邻的, 也就是考察上一个字符时和和考察接下来的字符时, 并不能共享信息. 而是当前的滑动窗口状态和 ww 个字符前的状态有很大的相似性.

1
2
3
4
5
6
7
// [  ] 对应 word 的宽度

  |--old window--|
  [  ][  ][  ][  ]        <- 之前可能的匹配
  xxxxxxxxxxxxxxxxxxxx
      [  ][  ][  ][  ]    <- 移动 w 个字符后的匹配
      |--new window--|

因此, 可以拆分出 ww 个不同的 “赛道”, 不同的赛道之间 offset 为 1, 每个赛道仅在新增 ww 个字符后才考察状态变化: 是否产生了新的匹配.

1
2
3
4
5
6
7
8
// [  ] 对应 word 的宽度

   xxxxxxxxxxxxxxxxxxxx
   [  ][  ][  ][  ]       <- 赛道 0
    [  ][  ][  ][  ]      <- 赛道 1
     [  ][  ][  ][  ]     <- 赛道 2
      [  ][  ][  ][  ]    <- 赛道 3
       [  ][  ][  ][  ]   <- 赛道 0 (新增 w 字符后)

如前所述, 每个赛道中上一次匹配的状态和下一次匹配的状态有很大的可复用性. 理论上, 只需要记录这个赛道中所有 substring 出现的次数, 每次新增/删除 substring 后, 检查各个 substring 的 count 是否和目标一致即可. 然而在具体的实现时, code 层面有办法做很大的优化, 避免真的遍历所有的 substring 的 count.

实现

首先实现一个 word 匹配器, 该匹配器做了优化, 使得检查输入的 words 是否正好和目标匹配, 能在短时间内完成. 为此, 在每次新增/删除 word 时, 多做了一些状态维护.

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
/// 存储待匹配的 word 及每个 word 目前的匹配情况
class SimpleMultiSet {
  
  /// word: count
  /// < 0 的 count 表示仍需一定数量的匹配
  /// > 0 的 count 表示超出了匹配
  /// 不存在的 word 表示正好匹配
  private var dict: [Substring: Int] = [:]

  /// 用待匹配的 words 初始化
  init(words: [String]) {
    for word in words {
      dict[word[...], default: 0] -= 1
    }
  }

  /// 新增加一个 candidate
  /// 理论上, 对应 word 的 count + 1
  /// 但当调整会导致 count == 0 时, 同时将 word 从 dict 里移除
  func push(_ word: Substring) {
    if let count = dict[word] {
      if count == -1 {
        dict[word] = nil
      } else {
        dict[word] = count + 1
      }
    } else {
      dict[word] = 1
    }
  }

  /// 去掉一个 candidate
  /// 理论上, 对应 word 的 count - 1
  /// 但当调整会导致 count == 0 时, 同时将 word 从 dict 里移除
  func remove(_ word: Substring) {
    if let count = dict[word] {
      if count == 1 {
        dict[word] = nil
      } else {
        dict[word] = count - 1
      }
    } else {
      dict[word] = -1
    }
  }

  /// 检查是否所有初始的 word 都正好匹配完
  func verify() -> Bool {
    return dict.isEmpty
  }
}

在此基础上根据上面的多赛道滑动窗口分析, 实现主算法.

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
/// Main entry point
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
  /// early exit
  if words.isEmpty || words[0].isEmpty {
    return []
  }
  
  let wordSize = words[0].count
  let count = words.count * wordSize
  if s.count < count {
    return []
  }

  /// 根据 word 宽度决定当前的赛道个数
  let sets = (0..<wordSize).map { _ in SimpleMultiSet(words: words) }
  /// 当前赛道
  var setIndex = 0

  /// 各个字符的 index
  // 当前 word start
  var i = s.startIndex
  // 当前 word end
  var j = s.index(i, offsetBy: wordSize)
  // 最旧的 word start
  var k = i
  // 最旧的 word end
  var l = j

  var stepper = 0
  let setLoopCount = wordSize
  
  var results: [Int] = []

  /// 增加初始的 word
  sets[setIndex].push(s[i..<j])
  if sets[setIndex].verify() {
    results.append(0)
  }

  while j != s.endIndex {
    /// 每新增一个字符, 决定当前赛道
    stepper += 1
    setIndex = (setIndex + 1) % setLoopCount

    /// 去掉超出窗口的 word
    if stepper >= count {
      sets[setIndex].remove(s[k..<l])
      s.formIndex(after: &k)
      s.formIndex(after: &l)
    }
  
    /// 增加新的 word
    s.formIndex(after: &i)
    s.formIndex(after: &j)
    sets[setIndex].push(s[i..<j])

    /// 检查当前赛道是否正好匹配
    if sets[setIndex].verify() {
      results.append(stepper - count + wordSize)
    }
  }
  return results
}

整体上使用了 Swift String 的 index 和 Substring 操作避免产生不需要的 copy.

性能分析

假设有 kk 个 word 待匹配, 每个 word 宽度为 ww, 输入字符串的长度为 ll.

  • 时间上
    • 初始化阶段: 对 ww 个赛道每个都创建 SimpleMultiSet. 每次创建时 SimpleMultiSet 需要将 kk 个 word 加入 dict, 考虑到 word 加入 dict 时的 hash 操作, 理论上会遍历 word 中的每个字符, 因此每次初始化耗时 O(k⋅w)O(k \cdot w). 因此初始化阶段总耗时 O(k⋅w2)O(k \cdot w^2).
    • 运行阶段: 是一个 main loop, 针对输入字符串中的字符循环 l−wl - w 次. 每次循环引入一个新的字符, 最多只需要从对应赛道的 SimpleMultiSet 中增加一个 ww 长度的 substring, 并去掉一个 ww 长度的 substring. 考虑到 word 加入和离开 dict 时的 hash 操作, 最多只需要 O(w)O(w). 其他操作都可以在 O(1)O(1) 内完成, 所以总耗时为 O(w⋅(l−w))O(w \cdot (l - w)). 一般而言 w≪lw \ll l, 因此可近似为 O(w⋅l)O(w \cdot l).
    • 总耗时 O(l⋅w+k⋅w2)O(l \cdot w + k \cdot w^2). 一般情况下, k≪lk \ll l, 或可把 kk 视为常数, 此时总耗时为 O(l⋅w)O(l \cdot w). 如果进一步把 ww 也视为常数, 则最终时间复杂度仅为 O(l)O(l).
  • 空间上
    • 主要存储消耗为 ww 个赛道对应的 ww 个 SimpleMultiSet .
    • 每个 SimpleMultiSet 最多时需要存储 kk 个宽度为 ww 的substring. 简化来看, 如果把存储 substring 用的 dict 的装载因子视为常数, 则单个 dict 占用空间 O(w⋅k)O(w \cdot k).
    • 总占用空间 O(k⋅w2)O(k \cdot w^2), 如果把 kk, ww 均视为常数, 那么整体空间复杂度仅为 O(1)O(1).

leetcode record
(leetcode 上的耗时分析和 server 上的 Swift 版本有很大关系, 实际参考价值有限)