CodingTour —

ARTS #37

Algorithm

本周选择的算法题是：Pascal’s Triangle II

规则如下：

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

Solution

我实现的方案：

Runtime：24 ms，快过 90.10%。

Memory：12.5 MB，低于 100%。

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        last_row = [1]
        for row_index in range(1, rowIndex + 1):
            row = [1]
            for col_index in range(1, row_index):
                row.append(last_row[col_index - 1] + last_row[col_index])
            last_row = row + [1]

        return last_row

这个版本用了一个额外的临时数组记录当前行的状态。

Runtime：20 ms，快过 97.98%。

Memory：12.6 MB，低于 100%。

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        last_row = [1] * (rowIndex + 1)
        for row_index in range(1, rowIndex + 1):
            for col_index in range(1, row_index):
                last_row[row_index - col_index] += last_row[row_index - col_index - 1]

        return last_row

优化后去掉了临时数组以及数组的插值开销，关键之处在于列的循环方式要改成后向，避免影响对后续值的计算。

Review

iOS Performance tips you probably didn’t know (from an ex-Apple engineer)

提取一些有用的知识点

UILabel 的内存开销比你认为的要多

生成位图
monochrome
- 单色内容
- 使用 kCAContentsFormatGray8Uint (每像素1个字节) 作为 CALayerContentsFormat
- 内存占用：width * height * contentScale ^ 2 * 1
non-monochrome
- Emoji 或多色的 AttributedString
- 使用 kCAContentsFormatRGBA8Uint (每像素4个字节) 作为 CALayerContentsFormat
- 内存占用：width * height * contentScale ^ 2 * 4
过早或过度优化都不可取

TableView / CollectionView 场景下可以将 text 置为 nil 以减少潜在内存：

tableView(_:didEndDisplaying:forRowAt:)
collectionView(_:didEndDisplaying:forItemAt:)

总是使用串行队列，并将并行队列作为最后一个选项

GCD 调度任务时，找不到空闲线程时会创建一个新的，会带来线程数量潜在变多的情况
线程的创建和切换不是免费的，要权衡任务的执行时长是否值得创建线程
自己显式控制队列，为不同的场景创建不同的队列
如果要使用并行队列，用你自己创建的，而不是 dispatch_get_global_queue：
QoS / Priority 等信息不能被正确传递

或许没有看上去那么糟糕

一些系统组件只在收到内存警告时才释放内存，如 CollectionView

在真实调试时，可以用私有 API 来模拟内存警告：

[[UIApplication sharedApplication] performSelector:@selector(_performMemoryWarning)];

避免使用 dispatch_semaphore_t 来等待异步任务

潜在的优先级反转问题，补一张图：

不要使用 UIView 的 tag

UIKit 使用 objc_get/setAssociatedObject() 实现 tag
避免使用 tag 并不能带来明显的性能改善
在 touch envents 处理过程中可以采用这项优化，因为该场景下用户对响应更敏感，可以节省毫秒级的时间开销

Tip

Python 的代码自动格式化工具

程序员如何用技术变现

总结一下：

程序员作为一个手艺人，要相信可以靠自己的技能变现
在公司工作和自己的规划一定不能冲突，一方面提高自己的技能，一方面可以让自己更为独立和自由地生活
学习时间花在有难度的地方，研究公司里外那些更为核心更有技术含量的技术
写文章要写别人没写过的或者自己能写得更好的
输出自己的影响力
程序员要通过自己的技能使得自己受到尊重
重视积累、时间的力量
关注有价值的东西
- 寻找市场上真正供不应求的地方
- 关注技术趋势 - 一方面需要将老技术的本质吃透；另一方面需要看新的技术是否顺应技术的发展趋势
- 时刻问自己两个问题：这个技术解决了什么问题？为什么是这个技术解决？
找到能体现价值的地方
重视动手能力
关注技术的付费点
- 能帮别人挣钱的地方
- 能帮别人省钱的地方
提升自己的能力和经历 - 增加自己的信息背书
查看一手的信息源 - 提高信息的获取效率
输出观点和价值观 - 提高自己的影响力
培养优质的朋友圈

Equifax 信息泄露始末

思考以及总结：

要重视安全
对外提供的接口/能力要注意权限控制
敏感信息要保护、隔离开
使用开源框架要时刻关心安全性，可以通过对代码库进行静态分析，检查使用的库版本是否有已知的漏洞，从而提醒维护者及时升级

从 Equifax 信息泄露

攻击手段及防范方式：

利用程序框架或库的已知的漏洞
- 了解它们的版本号，时刻跟踪这些产品的版本和最新的安全公告
- 及时打补丁
暴力破解密码
- 使用强度高的密码，提醒用户定期更换
- 密码加密存储，加上安全随机数作为 salt，避免彩虹表攻击
- 使用双重验证机制
代码注入
利用程序日志不小心泄露的信息
- 避免保存不必要的数据，使用完立即销毁
- 做好数据隔离，将数据操作保持在局部可控区域内进行
- 重要数据打码或加密返回
社会工程学
- 对用户来说，最好不同的网站使用不同的密码

另外在数据的管理上，需要：

建立多层安全防护
建立一个流程来快速部署带有安全补丁的软件产品
保护内部系统不在公网暴露，建立对异常访问模式的监控机制
要有安全意识，“支持性软件产品没有安全性漏洞”的假设不可取

何为技术领导力？

重要吗？为什么需要？

个人与公司在选择上的本质是一样的，需要关注长期优势。

技术领导力是：

尊重技术，追求核心基础技术
追逐自动化的高效率的工具和技术，同时避免无效率的组织架构和管理
解放生产力，追逐人效的提高
开发抽象和高质量的可以重用的技术组件
坚持高于社会主流的技术标准和要求

个人对技术领导力的体现为：

能够发现问题
能够提供解决问题的思路和方案，并能比较这些方案的优缺点
能够做出正确的技术决定
能够用更优雅，更简单，更容易的方式来解决问题
能够提高代码或软件的扩展性、重用性和可维护性
能够用正确的方式管理团队
创新能力

个人在获取技术领导力道路上的修炼：

扎实的基础技术
非同一般的学习能力
坚持做正确的事
不断提高对自己的要求标准