ARTS #29

Algorithm

本周选择的算法题是：Plus One

规则如下：

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution

我实现的方案：

Runtime：16 ms，快过 99.94%。

Memory：12.6 MB，低于 100%。

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:        
        for i in range(len(digits) - 1, -1, -1):
            digits[i] = 0 if digits[i] == 9 else digits[i] + 1
            if digits[i]: return digits
                
        return [1] + digits

Review

Supercharge Your Classes With Python super()

本文用了一个复杂的多重继承例子来描述 Python 的功能。

首先 Python 支持在继承中调用指定父类的方法：

class Animal:
    def eat(self):
        print("eat")

class Mammal(Animal):
    def eat(self):
        print("Mammal eat")

class Dog(Mammal):
    def eat(self):
        super(Mammal, self).eat()
        super().eat() # => super(Dog, self).eat()
        print("Dog eat")

Dog().eat()

# eat
# Mammal eat
# Dog eat

super() 等同于 super(Dog, self)。

然后考虑下面这个多重继承的例子：

class Animal:
    def eat(self):
        print("eat")

class Mammal(Animal):
    def eat(self):
        print("Mammal eat")

class Runnable:
    def eat(self):
        print("Runnable eat")

class Dog(Mammal, Runnable):
    def eat(self):
        super().eat()

Dog().eat()

# Mammal eat

Runnable 也有 eat 方法，我们可以通过把 Runnable 的继承位置放到前面来调用：

class Dog(Runnable, Mammal):
    def eat(self):
        super().eat()

Dog().eat()

# Runnable eat

Python 会通过 Method Resolution Order(or MRO) 来寻找要调用的方法。同时 Python 也提供了属性来检查这个列表：

print(Dog.__mro__)

# (<class '__main__.<locals>.Dog'>, 
# <class '__main__.<locals>.Runnable'>, 
# <class '__main__.<locals>.Mammal'>, 
# <class '__main__.<locals>.Animal'>, 
# <class 'object'>)

除了继承，Python 还能以 mix-in 的方式来对类进行拓展：

class RunnableMixin:
    def run(self):
        self.eat()

class Dog(Mammal, RunnableMixin):
    def eat(self):
        super().eat()

Dog().run()

# Mammal eat

Mixin 如其名，能混合其他类的功能，虽然 RunnableMixin 自身没有 eat 方法，但是仍然可以调用。

Mixin 可以摆脱类在多重继承下的复杂性，同时可以在类中直接混合其他类的功能，虽然也是继承的语法，但是相对于“is-a”，它更像是“includes-a”的关系。

Tip

OC 的 direct 关键字将给属性、方法带来直接调用，而不是通过 objc_msgSend 发送消息：

@interface MyClass: NSObject
@property(nonatomic) BOOL dynamicProperty;
@property(nonatomic, direct) BOOL directProperty;

- (void)dynamicMethod;
- (void)directMethod __attribute__((objc_direct));
@end

objc_direct_members 关键字能将整个 Category 标记为 direct：

__attribute__((objc_direct_members))
@interface MyClass ()
@property (nonatomic) BOOL directExtensionProperty;
- (void)directExtensionMethod;
@end

但是得益于底层对 objc_msgSend 的优化， direct 并不能带来性能上的明显优势。

不过标记为 direct 将对 Runtime 不可见，也就是：

更小的 Binary size
不会有外部调用

direct 只能在相同的 module 内调用，这个特性可以帮助 OC 带来私有 API，以及防止被 swizzling。

重温了分布式下的几篇文章，试图从庞大、复杂的分布式技术栈中理清一些重要的树干。

分布式要解决的核心问题是：

提高系统容量
关键业务保护

其中，提高系统容量的途径有：

缓存
负载均衡
异步调用
数据分区、数据镜像

业务保护本质上是为了防止单点故障拖累整个系统，可采取的措施有：

服务拆分
服务冗余
限流降级
高可用架构
高可用运维

落到一些具体的技术方案上，如服务调度的逻辑应该是可演化的，从最初的服务间的依赖开始，到服务状态、生命周期管理，再到整体服务架构的版本管理，接着是更加底层的资源/服务调度，最后是服务的弹性伸缩，每个节点可以独立发布，最终形成一个完整的服务调度解决方案。

而流量调度系统需要解决的问题是：

自动化，无需人工干预即可完成流量调度
高可用，在系统资源不足的情况下能帮系统平稳渡过

流量调度系统的关键技术：

高性能 - 使用高性能的技术来开发
扛流量 - 集群
业务逻辑 - 支持注入简单的业务逻辑
服务化 - 在不停机地情况下完成配置变更

数据调度（带状态）主要是为了解决分布式下一致性的问题，可采取的解决方案为：

Master - Slave 方案
Master - Master 方案
两阶段和三阶段提交方案
Paxos 方案

这几个都是属于在应用层解决问题，更好的方案是将承载数据的底层（文件系统）做成分布式系统，从数据结点上解决，这样对业务层来说就是透明的。

这些技术栈可以跨得很长、很深，我们想要达成的是全栈监控、服务/资源调度、流量调度、状态/数据调度和开发运维高度的自动化，这是初心，也是树干。

Algorithm

Solution

Review

Tip

Share