Sucha's Blog ~ Archive for March, 2021

21年3月25日 周四 20:33

Swift AVL Tree 和 SortedDictionary

苹果的 Collection 集合类型,我是找不到链表和树的,至于为什么,也许是底层封装好后,上层透露出来给大伙用,就不用担心了吧。

实际上没有那么美好,举个例子,一个不断更新的整数序列,新进来的整数有可能是做插入,或删除(比如元素不存在,就插入,存在就删除),且每次更新完后,都取最小的几个数字做输出,也就是一个不断求 Least(N) 的可变序列,这样的需求应该不难理解。

如果用苹果提供的数据结构,应该怎么做呢,不管是用 Array、Set 或是 Dictionary,最后的输出,总是免不了做一个 O(N * LogN) 的 sorted,其实我只是取最小的几个而已,这个全局的 sort 未免太奢侈了。

即便 Dictionary 是类似红黑树这样的结构(当然不是),对于所有元素 sorted,拿到所有元素的排序,再取 prefix,其实也是不必要的。

上面的需求,是我抄袭 skywind3000 miniavl 的原因,我将其翻译到了 Swift,然后呢,跟 Mutable Dictionary 结合,就变成了 SwiftSortedDictionary,AVL 树在 SwiftAvlTree

分析一下吧,AVL 树的插入、删除,查找都是 O(LogN),不过因为有 Dictionary 的加持,查找相关节点其实只需要 O(1),所以删除、查找变成了 O(1),当然删除比较特别,也就是做两、三个旋转而已,算 O(1) 了。

最后 Least(N) 的排序是交给 AVL 树来做的,一个闭包循环,加入一个表示序列进度的 index,一个可以控制结束的 inout 修饰的 stop 参数,就行了。

下面是测试的环境,我是在一台 i5 的老 MacOS 上测试的,基数是 256,添加了 512 个数,每次添加取 Least 16,同样的逻辑,循环了 10 次,结果对比如下:

with amount:256 addition:512 prefix:16 loop:10

Test Dicionary:
round 1: 111ms, avg: 111ms
round 2: 109ms, avg: 110ms
round 3: 109ms, avg: 110ms
round 4: 109ms, avg: 109ms
round 5: 109ms, avg: 109ms
round 6: 109ms, avg: 109ms
round 7: 109ms, avg: 109ms
round 8: 108ms, avg: 109ms
round 9: 109ms, avg: 109ms
round 10: 112ms, avg: 109ms

Test SortedDicionary:
round 1: 21ms, avg: 21ms
round 2: 18ms, avg: 19ms
round 3: 18ms, avg: 19ms
round 4: 19ms, avg: 19ms
round 5: 19ms, avg: 19ms
round 6: 19ms, avg: 19ms
round 7: 19ms, avg: 19ms
round 8: 19ms, avg: 19ms
round 9: 19ms, avg: 19ms
round 10: 19ms, avg: 19ms

当然现实中使用也是有收益的,负责的一个不具名的项目,因为要做上述类似的逻辑,之前单独使用 dictionary 结构做插入、删除,最后 sorted 函数在 time profile 排前面,使用了 sorted dictionary 后,耗时在 profile 中是完全看不到了。

不过就我负责的那个项目来说,因为还有其他的问题如频繁 UI 刷新以及 layout 的制约,肉眼可见的观感的改进不明显,但从 time profile 的结果来看,是有改进的,算达到了预期吧。

21年3月24日 周三 22:22

PageEventBus 大改动

上一周,PageEventBus 第一次用在了其他场景,让我不得不重新思考了一下使用 responder chain 隐含传递、关联 event bus 的优势、劣势,最后决定是将这个重要的特性去掉。

先说一下问题,使用了系统 UISearchViewController,然后使用了 result view controller,但是 result view controler 无法通过 responder chain 拿到 event bus,猜测是 search view controller 使用了其他的 window,或是其他的问题。

这样的话,估计如果有应用到其他的一些系统类,使用 responder chain 来拿到 event bus 这种想法,也是行不通的。

于是,做成了一个中心化的架构,默认使用带类型的 event bus 做 key,将新建立的 bus 缓存到一个中心节点中,其他同样类型的 event bus,通过查询中心节点,就能拿到 bus,然后 bus retain count +1,最后当所有持有 bus 的实例销毁后,这个类型的 bus 也会被自动销毁掉的。

这样的修改,对于单页面是没问题的,但是对于使用同样的事件类型,但具有多个实例,在不同的 UI 层次上,需要区分 bus 的情况,就需要特别处理一下了。这个时候,需要修改 agent 中默认的 event bus name,来建立多个不同的 event bus 实例。

21年3月16日 周二 21:04

PageEventBus 实践心得

在这次重构中实践了一把上个月说到的 PageEventBus,说到重构,其实只完成了一半,但是目前的心得,感觉是挺不错的。

因为页面交互很多,然后 UI 层次也比较复杂,有了 PageEventBus 后,少了很多传递数据的逻辑,一些有 UI 层次的 view,比如各种 StackView 包裹的有复杂业务功能的 view,不需要单独开业务参数接口了,整洁,同样的相关 view model 也不需要单独开业务接口了,整洁哈。

因为是在 didMovedToWindow 时候才去找 superview 持有的 bus,之前担心许多 view 下来会不会有什么影响,但实际上需要 findBus 的 view model 没有很多,所以 UI 绘制效率一点都不影响,况且只有第一次需要通过 next responder 来找,找到后就挂接上了,稳得很。

不过也有在之前没有考虑好的,比如 view controller 这个部分,因为 page model 继承于 view model,对于 controller 及 controller 上的 view 是 unowned let 的方式,意味着初始化的时候,就开始访问 controller 及其 view 了,这很不好。

因为 controller 的 view 不应该那么早被导入到内存,一般都在实际需要展示前再让它加载到内存,所以实际上 page model 没法完全独立于 controller,需要在 controller viewDidLoad 后才进行初始化。

所以这算个小遗憾吧,我现在的做法是,做一个可选闭包,在 viewDidLoad 里面执行,确保有了 viewDiDLoad 后,才初始化 page model,这样就好很多了,估计后面会改到 BlockViewController 里面做例子。

另外,还有些遗憾的点是,不复杂的业务,实际上根本用不到这个 event bus;还有就是,如果需要在不同的业务 controller 之间做数据传递,当前的 PageEventBus 又不可以拓展,比如没有相关路由的接口,可以连接两个不同的 event bus。

连接两个不同的 event bus,有时候还是很必要的,当然这个完全可以交给系统的 notification 来完成,但是接口感觉又麻烦了一点,后续感觉可以在这点上继续推进的,虽然现在的工程不一定能够用上,缺少实践心得还是感觉稍微有点不爽。

21年3月15日 周一 22:27

PinLayout 及 StackViewLayout

虽然现在 iOS 开发几乎全部都是使用 AutoLayout 了,诸如 OC 时代的 Masonry 或者 Swift 时代的 Snapit,或者 TinyConstraint,但其实基于 frame layout 还是有一些可以介绍的,就比如 PinLayout 以及 StackViewLayout

这里注意 StackViewLayout 在 dev 分支下才有内容,另外官方的 StackViewLayout 其实有循环引用,我提了一个 pull request,解决了循环引用,并加入了 distribution 的方案,估计没人看了。

PinLayout 很有意思,做为 UIView 的一个计算属性,chainable 方式不断接下来描述这个 layout 的位置、大小,最后在 deinit 的时候,才真正将传递进来的 UIView 进行设置,设置的属性是 center 及 bounds。

因为已经在一个重构的项目中使用了这两套方案,可以说一下了,相对于 AutoLayout,其实是不够方便的,但有些限制还是不错的。不够方便的是,PinLayout 描述的其实是有先后顺序的,就跟 AutoLayout 的 priority 一样,先描述的,PinLayout 会先 deinit,layout 完成后就成了其他 view layout 描述的输入。

自认为虽然不方便,但也算不错的限制是,不像 AutoLayout,只要有 superview 就可以描述,PinLayout 及 StackViewLayout,描述 subview 时,只能在 layout 的过程中,比如 layoutSubviews 或者是 sizeThatFits 里面。

另外在自动计算宽度、高度方面,PinLayout 相比 AutoLayout,要麻烦许多,需要 view 重写 sizeThatFits,限定宽度、高度后,基于这个计算另外的方向。

StackViewLayout 按照作者的说法是大量参考了 Yoga,这个组织其实也有个基于 Yoga 的 FlexLayout。大部分的功能有了,但是却没有 distribution,蛮可惜的,后面我自己加上了一个搓实现,不管怎么样,先有得用再说。

这俩个库的优势当然是计算速度极快,而且库很小,基于 frame 计算,如果没有自动宽高的话,是很安全的。

加上自动宽高的限定后,按照官网的描述,layout 逻辑被单独隔离在一个函数中,在 layoutSubivews 有使用,在 sizeThatFits 也有使用,另外 AutoLayout 用的是 intrinsicContentSize 来计算内容大小。

如果需要适配 AutoLayout,有时是得考虑重写这个函数的,这个函数默认不会刷新,需要单独刷新一下,看 UIView 有介绍。

StackViewLayout 相比 UIStackView 可以做到一些特别的方案,比如因为有 grow 和 shrink,可以玩剩余比例。而且在搭建的时候,因为 chainable 很方便,就都在一个 lazy 属性中全部描述完了,我说的是描述多层嵌套的 StackViewLayout,看起来是很赏心悦目的。

只是具体 Layout 真的得多动一下脑筋,毕竟不是 AutoLayout 是多项式计算的,这里是固定流程的,特别是一些限定了宽度高度的场合,我可是将 subview 高度自动计算完后,设置给 StackViewLayout 的,StackViewLayout 再拉伸其他的 subview。

大概就是这样了吧,还可以用下的,不晓得后面有了 SwiftUI 后会怎么样了,SwiftUI 毕竟还没有用过。

21年3月15日 周一 20:46

西行漫记读后感

也许是从某个微博用户上面读到了有关西行漫记的点点信息,于是就找来看了,读的是微信读书上面的版本,试用了几天无限卡才读完。

这本书名字实际是《红星照耀中国》,但我搜时用的就是西行漫记,到底是从哪里读来的标题忘记了,之前命名为西行漫记,是因为在解放前,国统区其实不能出版红色读物,所以命名为西行漫记是为了好低调传播。

在这之前,有在 B 站上看了沙盘推演里面李得胜的四渡赤水,徐海东等出神入化的战争艺术。

话题转回来,这本书是西方第一次了解到红色中国的窗口,当时斯诺也是费了不少劲才从白区去到红区,因为红区被完全封锁了,留有少许的时间窗口,刚好也应该是在西安事变之前的一小段窗口期,东北军不鸟常凯申,没有围剿红军,而是准备秘密合作,于是有了空隙,斯诺终于找了一个机会去了红色根据地,不过当时还有大财主的民团各地流窜,被碰到会没命,也是很危险的。

斯诺去之前是满腹孤疑,对根据地、红军的方方面面一堆的疑问,第一天就见到了周总理,被总理给安排了 90 天的行程,心里还觉得时间太长了,后面实际花了 120 天,走的时候还恋恋不舍。

里面篇幅其实挺多的,最精彩的,当然是访问李得胜的记录,以及对于红军如何得到广大农民支持的描述。

里面的不少论述在论持久战里面其实也有,当时就很客观,深入的讨论了中国人民抵抗日本的必然胜利,所需要的条件,什么是主要条件,什么是次要条件,什么是内部条件,什么是外部条件,为什么这些外部条件会成立,另外战争会分几个阶段(应该是论持久战里面的了,都混在一起说了吧),然后中国的优势和劣势,日本的优势和劣势,等等。

李得胜说这些话是很有资本的,毕竟国共内战已经 10 年了,经历了五次大围剿,还发展壮大了。

还讨论了具体会用的战略,“战略应该是一种在一条很长、流动的、不定的战线上 进行运动战的战略,快速进攻、快速退却,是一种大规模的运动战”,“我们的战略和战术应该注意避免在战争初期阶段进行大决战,而应该逐步打击敌军有生力量的志气、斗志和军事效率”。

说到得到农民拥护,当时军阀割据,为了养兵,各地都横征暴敛,征税都预征了几十年,国民党代表的是大地主、大资本家、以及国外资本的势力,广大的农民们只能是越来越穷。

为何会拥护共产党呢,是因为土地革命,革了大地主的命,将地分给广大农民,少征税,因此各地都收到广大群众的欢迎,这个国民党是做不到的。这也是红军为何是初期很穷的原因,也是为什么如燎原之火的原因,真的因为各地都是军阀,广大农民活不下去了。

对比一下,李得胜在回答斯诺对印度的看法时,说”印度不经过土地革命,是永远不会实现独立的“。当然印度在 1947 年就独立了,不过应该是类似国民党上台一样吧,代表的是大地主、大资产阶级的利益,现在种性、各地利益分割就可以看到,显然生产力远未得到解放。

估计是年龄大了吧,现在都喜欢看这样的书了。