idea's blog

* 暴力破解(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 等.

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

蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.

但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.

Continue reading »

KV 数据结构极大地简化了存储引擎的接口和实现. 基本的 KV 接口一般就是 Get(), Set(), 实现上代码也很简单, 极简的实现可以直接利用编码语言提供的 map(哈希, 红黑树)来提供内存数据结构, 而且硬盘上直接 dump 内存数据即可(类似 Redis 的策略).

不过, KV 存储引擎自己省事了, 但使用者不喜欢, 因为大部分的业务并不是 KV 所能表达的, 业务需要丰富的数据结构, 表格(table), 列表(list), map 等各种容器. 另外还需要排序功能, 业务依赖排序.

Continue reading »

分而治之算法(divide and conquer)是计算机算法领域最常用最有效的算法之一, 体现到编程上就是树(数据结构), 递归函数. 一般的代码模板是这样的:

func recursive(N){
	if(!N){return;}
	a, b = split(N); // divide 
	proc(a);         // conquer a
	recursive(b);      // process b
}

对于寻路, 分段处理最终达成目标这种模式的问题, 一般的代码模板是:

func recursive(N){
	if(!N){return;}
	a, b = split(N); // divide 
	r = proc(a);     // conquer a
	if(r){recursive(r + b);}  // conquer remain + b
	recursive(b);      // process b
}

多了一步:

if(r){recursive(r + b);}

因为前一段的剩余, 要和后一段组成新的问题, 然后被处理.

多副本一致性的理论基础: W + R > N

写时要同时写 W 个节点, 读时要同时读 R 个节点. 确保读的时候能获知集群的 commitIndex.
可以只读写 Leader, 因为 Leader 维护了 commitIndex.
如果要读 Follower, 则 Follower 要向 Leader 查询 commitIndex, 或者向 R 个节点查询获取最新的 commitIndex.

分布式事务也是类似, 协调者相当于 Leader, 参与者相当于 Follower.
如果 Follower 有未提交事务, 收到读或写请求时, 需要向协调者查询事务状态.

对于 Objective-C, 两个 NSMutableArray isEqual 返回 YES, 无论它们是否相同的范型类型. 这个特性导致 NSOutlineView 在展开两个空的节点(对应着不同的空数组实例)时, 出现混乱. 当你点击展开 A 时, 它却展开 B. 这个可能是 NSOutlineView 内部使用 isEqual 来判断 item 是否相等, 而不是用 "==".

即使数组不是空的, 只要它们包含相同的内容, 都会出现这个 bug. 原因就是, 不应该用 isEqual 来判断, 而应该用 == 来判断指针是否相等.