ARTS #147

Algorithm

本周选择的算法题是：Two City Scheduling。

规则

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Example 1:

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Example 2:

Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3:

Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

Constraints:

2 * n == costs.length
2 <= costs.length <= 100
costs.length is even.
1 <= aCosti, bCosti <= 1000

Solution

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        ans, gaps = 0, []
        n = len(costs)//2
        for a, b in costs:
            ans += a
            gaps.append(b-a)
        gaps.sort()
        for i in range(n):
            ans += gaps[i]
        return ans

Review

After one year of Rust

仔细想一想，Rust 的发展格外迅速：

9 年前：由 Mozilla Research 孵化
7 年前：第一个稳定版本
4 年前：正式支持 async-await 语法
今天：可提供成熟的面向生产环境的服务器解决方案

除了 JavaScript，很少有编程语言的生态发展得如何之快，Dropbox、Figma、NPM、Microsoft、CloudFlare、Facebook、Amazon、Discord 这些知名企业也部分应用了 Rust，还有 Linux 内核。

为什么要引入 Rust 跨端：

客户端开发有一定的复杂度
1. 实施复杂性，客户端几乎都是单体架构
2. 底层代码的案例保障较少
客户端有更高的性能需求
1. 在有限的资源里满足日益增长的需求
2. 需要更少的耗电量来满足日益增长的需求
各个平台之间存在差异，团队不想做重复性的工作和犯同样的错误
Rust 是一个有安全性保证的系统级语言
Rust 能保证内存安全和并发安全，意味着，可以让团队专注于业务，降低错误率
Rust 对底层控制力强，但又不失现代语言的高级特性和抽象能力，可降低项目的维护成本

使用 Rust 的潜在收益：

只需要一份代码库来进行设计、实施和审查
唯一面向服务端的客户端，便于实施安全策略

做跨端的几条原则：

不能影响用户体验，App 应该做到性能足够好，且耗电尽量少
与原生平台交互应该非常方便
不应只是单独的一些组件，而是对整体代码做过权衡之后的核心代码（非 UI 代码可以跨平台）
Rust 代码应包含与平台无关的通用代码，特定平台的代码应该保留在特定平台的代码中。

Tip

Python3 中的 range 返回的是 Iterable 而不是 Iterator。

仔细想想这样也合理，比如如下代码：

numbers = range(3)
tuple(numbers)
# (0, 1, 2)
tuple(numbers)
# (0, 1, 2)

而如果是 Iterator：

numbers = iter(range(3))
tuple(numbers)
# (0, 1, 2)
tuple(numbers)
# ()

由于 Iterator 是有状态的，所以再次执行是空。

Python3 里的每个 Iterator 都是 Iterable，每次对 Iterable 调用 iter 也会得到一个新的 Iterator，这个行为减少了错误发生的可能，而且为 Python3 中的大量动作提供了一致的抽象。

降低架构风险的做法

功能性需求

解决问题的最好方法是在一开始就避免问题发生。工程师或架构师往往是是项目问题的终结者或挑战者，要认识到最复杂的需求也应该是最有趣的需求，但如果要以非常高的复杂性和风险得到一个几乎没有价值的需求，那就要重新考虑实现这些功能是否有意义。

非功能性需求

即使功能性需求很简单，有时候架构师也会做出非常复杂和具有风险的设计，对非功能性需求来说，应该有且仅有一个正确的目标，通过目标引导走在正确的方向上，帮助做出取舍，并在多个备选方案中作出最优的选择，不能让微不足道的性能或可用性等改进导致非功能性需求的设计过于复杂。

设计

在设计层面，所有的组件/服务应该具有相似的复杂度。每个服务就像一座桥梁，复杂性就是桥梁上的负载，如果负载太高，桥就会断，所以每座桥在设计之初就会明确可承受的负载量。对服务来说，一旦复杂度达到临界点，服务就会变得难以维护和扩展。与其拥有一个格外复杂的服务，不如拥有两、三个不太复杂的服务。

工具

在做数据库、语言或框架选型时，要考虑开发团队是否拥有相关的经验。多数情况下工具本身不会犯错，而是取决于开发人员能够用它做成什么。比如团队有多年的使用、优化 PostgreSQL 经验，那么仅仅因为 MongoDB 在某些事情上可能比 PostgreSQL 做得更好而切换到 MongoDB 就不是一个明智的选择，一般来说，利用过去的经验更多，项目的风险就越小。

原型

理想情况下，在项目开始前就认定项目会成功是最好不过的。现实往往不是这样，谁都不希望开发很久后才发现设计不太好，那么在项目价值最低的阶段用 PoC 或 MVP 验证设计的可行性是不错的选择，这会产生极高的 ROI：价值最低也是成本最低，但有助于改进设计并消除不确定性。