idea's blog

好的代码应该是直观的, 简单的. 直观就是"所思就所写", 想的是什么样就要把代码写成什么样子, 不要七拐八绕.

例如, 在做结构设计和流程设计时, 我们分析出某个功能流程应该这样做:

先做步骤1, 然后做步骤2.

什么是程序设计? 程序设计就是流程, 是串行化, 是先后顺序. 所以, 文档设计完毕之后, 必须写下这样的代码:

step1();
step2();

Continue reading »

常规的单机软件升级, 一般认为是一个原子操作, 也就是说, 软件会在"瞬间"完成升级, 即使不能在"瞬间"完成升级, 也要中断服务, 等升级完成后再提供服务.

对于需要中断服务的情况, 在分布式系统中是不能接受的. 同时, 分布式系统的升级永远不可能在"瞬间"完成. 因此, 分布式系统升级会面临一个长时间的中间态, 新旧版本的软件同时运行, 这就涉及到兼容性问题.

假如, 新版本的软件的数据格式改变了, 那么, 新版本写入的数据就无法被旧版本识别, 旧版本就会报错. 因为, 新版本的软件很容易做到向后兼容(新的兼容旧的), 但是, 向前兼容(旧的兼容新的)依赖预见性, 不可能预见全部未来.

如果分布式系统无法做到向前兼容, 这时候, 应该怎么办呢? 难道要停服升级?

一个常用的解决方案是在旧版本和新版本之间插入一个中间版本. 这个中间版本的主要特点是不写入新格式的数据, 但能识别新格式的数据.

我们先逐步把旧版本替换为中间版本, 在这个过程中, 因为没有新格式的数据产生, 所以没有兼容问题. 等旧版本全部替换完毕后, 逐步升级为新版本, 在这个过程中, 虽然新旧格式的数据都有, 但新版本都能识别, 也没有兼容问题

在单机编程时代, 每一项数据只有唯一的一份, 对数据的修改也是 in-place 的. 但是, 在并发编程领域, 包括分布式系统, 数据多版本(Multi Version, Versioning)是核心.

我们先从单机编程的内存操作出发. 对于内存的操作, 都是原地(in-place)更新的. 对象和内存空间强绑定, 当更新对象时, 是将对象的内存空间擦除然后用新数据写覆盖. 到了多线程编程时代, 就引入了锁机制, 因为擦除和写操作过程不是原子性的, 可能擦除到一半时, 就被其它线程读取了, 因此要加锁.

单机的硬盘操作, 基本也是借鉴内存操作, 也是对象和硬盘空间强绑定. 至少大部分程序员的思想是这样的, 这样比较直观. 跟内存操作一样, in-place 也遇到了操作的原子性挑战. 内存本来就是易失的(掉电后丢失), 但硬盘不一样, 数据需要持久化(掉电不丢失), 即使靠加锁解决了访问原子性问题, 但解决不了数据丢失问题. 所以, 硬盘操作是最先引入多版本技术的. 当需要修改某个对象时, 在另外的地方保存对象的新数据, 然后在另外的地方原子性地修改指向新数据的"指针". 事实上, 指针的修改也是多版本的, 不是 in-place 的, 后面会细说.
Continue reading »

例如要检测如下的环, 找出 a 点到 b 点的距离 mu, 以及环的周长 lam.

                +----------------+
                |                | 
+---------------+----------------+
a    mu         b                c
                |       v        |

用快慢指针同时遍历. 首先可知, 如果环存在, 快慢指针会在 c 点相遇. c 到 b 点的距离是 v. 那么可知, 相遇时, 快慢指针走过的距离是:

慢: mu + m * lam + v
快: mu + n * lam + v

它们是两倍关系, 所以:

2 * (mu + m * lam + v) = mu + n * lam + v
2 * mu + 2 * v + 2 * m * lam = mu + n * lam + v
v = n*lam - 2*m*lam - mu

这时, 两个指针再以同样的速度前进. s 从 a 点出发, f 从 c 点出发. 可以知道, 当 s 走了 mu 距离后, 到达 b 点. 而 f 走了 mu 距离后, 也到达 b 点. 两者相遇.

n*lam - 2*m*lam - mu + mu = n*lam - 2*m*lam

1. 问题可分而治之且 BFS

首先, 问题必须是可分而治之的, 并在最后合并. 分而治之(递归)是为了穷举, 合并是为了找最优.

Result r(costs[], target){
	args = [];
	for(cost in costs){
		tmp = r(costs - cost, target - cost) + cost;
		args += tmp;
	}
	return G(args);
}

虽然上面的代码是 DFS, 但形式上是 BFS, 而且也应该写成 BFS, 只不过 BFS 的代码不简洁而已.

思考: 与贪婪算法的区别.

2. 合并函数 G(...) 可迭代处理

因为 G() 是可以转换成迭代的, 所以代码变成:

Result r(costs[], target){
	ret = PRE;
	for(cost in costs){
		tmp = r(costs - cost, target - cost) + cost;
		ret = G(ret, tmp);
	}
	return ret;
}

PRE(开始之前)是引入的边界外的参数, 以便让代码处理逻辑简化, 不然要加 if 条件判断, 就无法在形式化上统一.

3. 增加缓存

Result r(costs[], target, dp){
	cache_key = make_cache_key(costs, target);
	if(dp[cache_key]){
		return dp[cache_key];
	}
	ret = PRE;
	for(cost : costs){
		tmp = r(costs - cost, target - cost, dp) + cost;
		ret = G(ret, tmp);
	}
	dp[cache_key] = ret;
	return ret;
}

4. 将递归转成迭代

#### 推导型

Result forward(costs, target){
	init(dp);
	cc[PRE] = costs;
	for(curr in range(PRE, target)){
		costs = cc[curr];
		for(cost : costs){
			dp[next] = G(dp[next], dp[curr] + cost);
			cc[next] = costs - cost if dp[next] updated;
		}
	}
	return dp[target];
}

#### 回溯型

Result backtrack(costs[], target){
	dp[PRE] = PRE;
	cc[PRE] = costs;
	for(curr in range(atomic, target)){
		for(prev in get_prev_list(curr)){
			costs = cc[prev];
			cost = costs.link(prev, curr); 
			dp[curr] = G(dp[curr], dp[prev] + cost);
			cc[curr] = costs - cost if dp[curr] updated;
		}
	}
	return dp[target];
}

5. 缓存可淘汰: 滑动窗口

这一条件不是必须的, 因为很多动态规划解法无法淘汰缓存. 如果缓存可淘汰, 而且是可以用滑动窗口的方式淘汰, 那么就是非常**经典且巧妙的**动态规划解法.

对于推导型动态规划, 只需要缓存最长的推导距离. 对于回溯型动态规划, 只需要缓存最长的回溯距离.

这里举的例子是单节点推导, 下一节点只依赖单一的前序节点, 但有些问题需要依赖多个前序节点才能出方案, 例如斐波那契数列. 需要注意.

* 暴力破解(brute force)

暴力破解, 就是穷举. 穷举的方式一般用递归, O(n^2). 优化的思路是减少递归步骤:

1. 更加严格的静态递归条件
2. 增加 close_list, 动态地判断是否需要进行递归, close_list 根据执行情况动态变化

另外的一种优化方向是消除递归. 因为递归是可以通过递归栈 open_list 来消除的. 可以对栈进行动态排序, 优先进行最可能成功的下一个步骤(A*). 这种排序优化, 导致可以使用不同的数据结构来存储递归栈: stack, queue, priority_queue.

有序性, 有序子集: 有一种非常常用的优化思路是利用输入条件的局部有序性(存在有序的子集), 不再穷举这些有序的子集. 在处理这些有序子集时, 采用 O(n) 或者 O(K) 算法, 最差也能采用二分法 O(logN), 而且其它元素与这些有序子集结合时, 也不再需要穷举.

A* 算法: open_list 根据沉没成本G和未来成本(H)之和来决定下一个处理步骤, 达成即最优.

* 动态规划(dynamic programming)

动态规划与暴力破解类似, 都是分而治之的思路, 但又不相同. 动态规划的下一个处理步骤是唯一的, 而且 open_list 初始可以确定, 后续单调递减. 下一个步骤的处理除了依赖自身的静态条件, 还依赖之前的处理结果集, 并维护这个结果集. 有点像消除了递归之后的暴力破解, 但暴力破解的 open_list 不是初始固定的.

* 直观解法(coding)

这类问题的解法非常直观, 一般没有算法上的优化空间, 也不需要技巧, 纯粹是为了训练编程能力. 考察做题者对变量的状态判断是否完备充分, 判断路径是否最简, if 分支是否可以合并等等. 所以, 就是考察边界条件的判断, 还有逻辑条件精减, 要求有非常强的逻辑思维能力.

一般这类题就是链表翻转, 有序链表合并, 删除重复元素, 数组遍历(螺旋向内, 螺旋向外, 蛇形, 等等), partition 等.

要点是: 边界判断, 分支合并, 简化重合边界的处理, 增加虚拟节点进行辅助.