算法

什么是维稳算法？ 维稳算法(Order Maintenance)是儒家思想君君臣臣的集大成者 - 这个算法使我们可以拿取任意两个事物，然后进行一个全序比较。 换言之，Order Maintenance可以看成一个链表，但是链表的所有元素直接可以快速比较前后。 也就是说，OM带有以下三个api： Head(): OM，取得链表头 Create(before:OM):OM，在before后插入一个节点 <=(lhs: OM, rhs: OM): bool，判断lhs是否在rhs的前面 OM的实现不是这篇文章的重点，就放在Order Maintenance - Google Slide这里了。 最近工作中发现了动态LCA（给予一棵树，处理树上的修改穿插着LCA查询）可以用OM解决。 另外碎碎念：Order Maintenance在Incremental Computing，Persistent Data Structure，跟String Algorithm上面都有应用，已经属于我走到那跟到那的变态跟踪狂了，下头算法！必须告它性骚扰！ 一般来说，这个问题可以用link cut tree解决，两者复杂度一样，但是思路跟工具都不一样。特别是用到了维稳算法！维稳算法解动态LCA也有各种各样的extension，比如魔改一下可以用来增量维护binding in lambda calculus。 具体操作如下： 我们可以给树的每个节点一个OM区间，并且用preorder traversal进出时间维护区间开闭。 具体操作是，给一颗新的树，我们可以维护一个OM timer。此timer在traversal递归进/出的时候会各进行一次自增，并且用自增前的两个值来初始化OM区间。这样，所有OM值都是独一无二的，并且树的区间包含子树的区间。同时，无直系亲属关系的两节点区间不相交。 新加入的叶子节点的区间可以用兄或（如果兄不存在）父的区间右端点连续插入两个值初始化。 我们维护一个装着区间的平衡二叉树。区间的序是左端点的序，而BST每一节点储存"该BST子树的最大右端点"。 这时候，找寻多个节点的LCA，成为了‘找寻最大的（左端点最右），包含所有节点区间的区间’。 这可以分两步完成： 0：去除所有不够左的左端点。由于是暂时的，我们不需维护平衡性，只需维护子树最大右端点，所以是O(log(n)) 1：在所有右端点足够右的子树里，寻找最右的左端点。 具体操作是： 当右子树子树最大右端点足够大的时候，递归进去。 否则，如果当下节点右端点足够大，返回。 否则，左子树子树最大右端点足够大，递归进去。 这是log(n)，跟link cut tree大O一样（但我认为更好懂也更优雅！） 另外顺带一提：Edward Kmett对这个问题的函数式特化版做了一个改进，达到了O(log(height))，见 On-line Lowest Common Ancestor

别急！ 别急！ 我们先别急着切入正文，而是先看看一道算法题： 圆角骑士魔理沙：数组多次取第X大元素 大家在评论区可以看到，这道题有一定的难度：不少人给出了错误，或者超时的答案。 尽管最高赞给出的答案的确是正确的，其实有一个简单很多的做法： 对N生成二叉搜索树，然后用M索引之。 等下，这不是O(n log n)的吗？ 所以才说别急！我们想一想，当M < N的时候，这个二叉树，并不是所有节点，都会被索引。 那，我们为什么要去把不会被用的二叉树部分构建出来捏？ 但是，我们怎么知道‘树的那一部分会被用上’？ 答案是，我们可以同时交叉构建树跟索引树的过程 - 默认情况下，树是没构建的。当我们索引没被构建过的树，我们会构建这里的最小一部分，然后保存下结果，再进行构建。 class LazyBST: def __init__(self, arr): self.constructed = False self.arr = arr self.size = len(arr) def idx(self, index): if not self.constructed: self.constructed = True self.head = self.arr[0] self.left = LazyBST([x for x in self.arr[1:] if x <= self.head]) self.right = LazyBST([x for x in self.arr[1:] if x > self.head]) if index < self....

“Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowchart; it’ll be obvious.” – Fred Brooks, The Mythical Man Month (1975) 吐槽一下，最近手指好疼，怀疑打字打太多了，等下有空看看医生，orz 我们先看这一个著名的笑话： 三个程序员被要求穿过一片田地，到达另一侧的房子。 菜鸟程序员目测了一下之间很短的距离，说：“不远！我只要十分钟。” 资深程序员看了一眼田地，想了一会，说：“我应该能在一天内过去。”菜鸟程序员很惊讶。 大神程序员看了一眼田地，说：“看起来要十分钟，但我觉得十五分钟应该够了。” 资深程序员冷笑了一声。 菜鸟程序员出发了，但只过了一会，地雷爆炸了，炸出了巨大的洞。这下他必须偏移预定的路线，原路返回，反复尝试穿过田地。最后他花了两天到达目的地，到的时候颤颤发抖，还受了伤。 资深程序员一出发就匍匐前进，仔细地拍打地面，寻找地雷，只有在安全的时候才前进。他在一天的时间内小心谨慎地缓慢爬过了这片地，只触发了几个地雷。 大神程序员出发之后径直穿过了田地，十分果断。他只用了十分钟就到了另一边。 “你是怎么做到的？”另外两个人问道，“那些地雷怎么没有伤到你？” “很简单，”他回答道，“我最初就没有埋地雷。” 一般来说，我们写程序，都是这样的步骤： 0：写出程序 1：写测试 2：通过测试查找错误，回到0修补，如果没发生问题就假装程序写好了 这时候有一个很大的问题：debug是一个很麻烦的过程，而且debug后不代表程序没有问题，只代表了程序在这些测试上没有问题（所以你还要牢费心力找测试）。更严重的问题是，在多线程或者分布式系统里面，同一段代码同一段输入，问题是概率性的：有可能会发生，也有可能不会发生。更更糟糕的一点 - 这些分布式代码，比如paxos的实现，往往是最核心的代码，当这些代码发生问题后，会带垮整个服务器集群，造成巨大的损失。 但是，为什么我们要劳心劳力的去debug？我们不把错误放进程序，不就好了？ 或者，我们更进一步，为什么要写程序？把程序种子埋土里，然后过几天等程序长大了，就收掉，不就行了？ 你先别笑，这的确是编写复杂程序的一个方法。 更具体的说，当我们程序运行到一半，假设我们随机修改一下变量的值，很明显程序不会没问题的继续运行下去。 比如说，如果我们在写一个二叉搜索树，当我们运行的时候，把一颗树的最左节点跟最右节点交换了，那接下来可能会找不到需要的值。 也就是说，我们的程序需要遵守一定的规则(invariant)。对于上面的例子来说，我们需要遵守的invariant是，一个二叉树的左边的所有节点小于等于自身，自身小于等于右边的所有节点。 所以，我们写程序的时候，要保证这些invariant的正确性。但是，我们可以反过来，从这些invariant，推导出一个程序！ 更具体的说，我们 0 - 写下程序输入跟输出符合的条件，一般来说，输入的条件并不等价于输出的条件，所以这时候，这两个条件之间，是有一个空缺的 1 - 根据这些规则，猜出一小段代码，这些代码会把这些空缺变得更小，然后我们不停进行这个操作，直到空缺消失。这时候，程序就编写完成了。...

最近遇到一道很有趣的算法题： 给与数组N[0, n)跟M[0, m)，并且m <= n，其中M的元素都在[0, n)以内，换句话说可以用M索引N。这个时候，我们对每个M里面的元素m，找出N里面第m大的元素，换句话说，我们要计算出 map (\m_element -> sort n !! m_element) m 比如说，假如N是[1, 9, 3, 8, 10, 7, 2, 10, 8]，M是[7, 2, 0]，结果应该是[10, 3, 1] 但是，我们希望平均时间复杂度是O(n log m)，这怎么做？（注意，这比n log n小，而很多做法都是后者） 为了给大家一些思考时间，明天再放答案 更新：答案在https://zhuanlan.zhihu.com/p/578991429

首先这里不是用打表这种对于提高打牌技术没有实际意义的 baka 方法。 特殊型(国士，七对型)听牌先按下，字牌因为没有什么难度请读者自行作为课后作業。这里先只考慮由 1~9 的万，条，筒组成的牌形。 众所周知标准和牌形是由一对将＋四面子组成的。听牌则有单骑，两面，嵌张。对于如下简单的情形的只要是稍会麻将的就能不难看出是听 2 5 筒的(请忽略最右的白牌)。 那么来分析一下人类玩家在看到这一手牌时做了什么样的思考，然后如何把这样的思考转化为算法。 表示法 首先，根據花色拆为 (12366 索)， (345566 万)， (24 索) 三组。 我们要一个在 APL 中表示手牌的方法。假设己经有做了分组，那么如上圖的手牌就可以用一个 nested array 表示 ⊢hand←(1 2 3 6 6)(3 4 5 5 6 7)(3 4) ┌─────────┬───────────┬───┐ │1 2 3 6 6│3 4 5 5 6 7│3 4│ └─────────┴───────────┴───┘ 然而这样的表示对于处理没有什么助益，所以要把每一组编码成一个长度为9的array，对应每种花色 1~9 的牌每张出现的数量。 enc←{⍺←9⊣⎕IO←1 ⋄ ((⊢∘≢⌸⍵)@(∪⍵))⍺⍴0} enc 1 2 3 6 6 1 1 1 0 0 2 0 0 0 enc¨hand ┌─────────────────┬─────────────────┬─────────────────┐ │1 1 1 0 0 2 0 0 0│0 0 1 1 2 1 1 0 0│0 0 1 1 0 0 0 0 0│ └─────────────────┴─────────────────┴─────────────────┘ 己完成的面子 在上面所示的听牌中，人类可以一眼看出三组中 345 567 万是己完成的面子，那这「一眼」中发生了什么？...

∇R←DECODE N R←2⊥N ∇ ∇R←X ENCODE N R←(X⍴2)⊤N ∇ ∇R←ENCODE32 N R←(32⍴2)⊤N ∇ ∇R←ENCODE64 N R←(64⍴2)⊤N ∇ ⍝ example ⎕←A←ENCODE64 865940890845960854 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 DECODE A 8....

（其实我倒数第三第四章跳了，实在看不动了。。。orz） 初看之下，这本书很逗比：身为一本算法书，只有十多个算法，一半的时间用来定义不知所云的奇葩语言，语言枯燥无比。。。简直什么鬼= = 如果你这样想，只能表明你完全没看进去：就跟Software Foundations是包着Coq皮（想歪的去面壁）的PL书一样，这本书比起纯正的算法书，更算得上是以算法之名，讲PL，讲如何编程，如果你只是来 看算法的话，你一定会失望。如果不是，你来对地方了：读完以后，你会对dijkstra 的The Humble Programmer之类的EWD有着更深的了解，会对computation 改变认识，知道该如何写代码，有一些reasoning/deduction的heuristic，也会感叹于dijkstra疯子般的radical reasoning下，就是不会学到什么算法（除非你算法跟我一样弱得过不去NOIP初赛） 前一半的不知道叫什么的语言已经是一绝了，我看之前完全无法想象跟while大同小异的一门语言能给我带来如此巨大的震撼-formalism跟minimalism尽管不是不可见，但是语言最核心是由nondeterminism construct构建起来的：你有没有考虑过其实你每天用的if语句其实是个败笔？该语言的variable设计也是神来之笔，我一开始看的时候也没明白为什么在极简主义的语言里面要引入如此复杂的东西，认为是画蛇添足，直到一遍又一遍的看，才领悟了精妙之处。。。完爆某另一个图灵奖得主写的算法书里面的不知所云的语言（ 后一半是利用这个语言解决各种问题，比如equivalence class，比如shortest spanning tree。。。一开始他是以极度formal的tone做这个的，proof什么的一个都不漏，到了后期你明白怎么搞了，由于篇幅关系，跳掉了一大部分formal proof，left as exercise，更着重于：我们如何解决这个问题？并给出了一定的example/heuristic，比如对intermediate step做出assumption，（shortest spanning tree中，assume已经决定的set of edge自己也是shortest spanning tree）（换句话说在什么时候需要加强induction hypothesis），比如当你代码钦定了什么的时候，利用之来优化（对一个naive 算法由3 pass改成2 pass，得出Rem’s algorithm），比如把计算从循环中往外拉，改为incrementally update之。。。 这本书其实绝大部分时候都在讲如何去对一个又一个的问题进行分析，分解，最后解决之-一开始的语言设计是如此，后面的算法也是如此，看这本书的过程，更多的像是跟dijkstra一起研究如何解决一个又一个的问题-从问题的定义下手，用直觉更heuristic找出可能有用的insight，并用之分解问题（算法设计），亦或者从现有的方案下手，质疑一切，找出问题，然后精简，或者去掉之（语言设计）。确实，Dijkstra 最后说了大概这样一段话：我们的确不太可能看完一本书，就明白该如何思考，但是我希望你读完这本书以后，能用seperation of concern之类的办法（没错，Dijkstra 发明了seperation of concern，还发明了pair programming，是软件工程中很重要的人（雾）），对一个复杂的问题，进行分解，导致不再复杂，是intellectually manageable的。 不过语言的确很枯燥，英文勉强的不用读了，这更多的我觉得是dijkstra认为“难的东西就是难的，无论如何修饰也是如此”导致的。。。