algorithm

Estimating branch probabilities says how one branch splits. BlockFrequencyInfo turns those local numbers into per-block frequencies, which nearly every profitability decision in LLVM ends up reading.

The core is a linear-time propagation over loop-packaged regions. Where no such structure exists — irreducible control flow — the accuracy goes with it.

LLVM's BranchProbabilityInfo assigns every multi-successor terminator a probability distribution over its successors. This post describes the estimation used when no profile is available and reimplements it as a standalone program.

The dominator tree lets us identify natural loops: a back edge T->H whose head H dominates its tail T defines a loop with the single entry H. This works only for reducible control flow graphs. Optimized machine code and decompiler output routinely contain irreducible loops, which have more than one entry and thus no dominating header, so the dominator-based method cannot see them.

This post builds a loop-nesting forest for an arbitrary CFG with the single-pass depth-first search of 韦韬、毛剑、邹维、陈宇(Tao Wei, Jian Mao, Wei Zou & Yu Chen) A New Algorithm for Identifying Loops in Decompilation, SAS 2007 (The 14th International Static Analysis Symposium).

A dominator tree can be used to compute natural loops.

• For every node H in a post-order traversal of the dominator tree (or the original CFG), find all predecessors that are dominated by H. This identifies all back edges.
• Each back edge T->H identifies a natural loop with H as the header.
  • Perform a flood fill starting from T in the reversed dominator tree (from exiting block to header)
  • All visited nodes reachable from the root belong to the natural loop associated with the back edge. These nodes are guaranteed to be reachable from H due to the dominator property.
  • Visited nodes unreachable from the root should be ignored.
  • Loops associated with visited nodes are considered subloops.

本文总结经典的区间第k小值数据结构题。 给定一个长为n的数组，元素为范围为[0,σ)的整数。有m个询问：求区间[l,r)中第k小的元素。

一些方法支持扩展问题：有m个操作，或者修改某个位置上的元素，或者询问区间[l,r)中第k小的元素。

In research papers, a segment tree refers to a tree data structure allowing retrieving a list of segments which contain the given point. In competitive programming, the name "segment tree" usually refers to a data structure maintaining an array. According to http://web.ntnu.edu.tw/~algo/Sequence2.html, the data structure originated from Baltic OI 2001: Mars Maps.

Discrete Fourier transform

题目描述

Expression Add Operators

今天在地铁上浪费了好多时间……呜呜……做其他事都没有效率，就利用这些时间写字了。

前几天LeetCode的Invert Binary Tree火了。名称有点糟，无法准确描述要求。

主要思路是遍历二叉树，把访问操作修改为交换左右孩子，每个节点都交换一次即可。

如果采用前序或中序遍历，则子树交换发生在遍历某棵子树之前，会引起麻烦。因此我想到了后序遍历，在遍历完子树后再交换左右孩子，重心就是如何实现常数空间复杂度的后序遍历。某些资料/问题称之为Morris post-order traversal。

题目描述

Best Time to Buy and Sell Stock IV

三类：

• 栈
  • 系统栈
  • 自己实现的栈
• 线索：Morris preorder/inorder/postorder traversal
• 其他edge-crawling方式：Schorr-Waite graph marking algorithm、Lindstrom-Dwyer algorithm

Suffix array是解决string search问题的一个工具，它是一个字串所有后缀的排序。

线性时间的构建算法主要有Kärkkäinen-Sanders()、Ko-Aluru()、KSP三种，其中KSP算法使用了类似suffix tree的构建方式，Kärkkäinen-Sanders算法时间复杂度的递推式为\(T(n)=T(\frac{2n}{3})+O(n)\)，通常认为性能不如\(T(n)=T(\frac{n}{2})+O(n)\)的Ko-Aluru。

按照的注记，借鉴对LMS substring递归排序使用的方法， 对原始的Ko-Aluru算法进行改动以简化内存使用和提升性能。 我的实现在字串和suffix array外仅使用两个数组：计数排序使用的桶和一个表示L/S类型的数组， 反映了Ko-Aluru算法能达到和同等的精简内存占用。

这个是学习编程时的一个耳熟能详的问题了：

n个人(编号为0,1,...,n-1)围成一个圈子，从0号开始依次报数，每数到第m个人，这个人就得自杀，之后从下个人开始继续报数，直到所有人都死亡为止。问最后一个死的人的编号(其实看到别人都死了之后最后剩下的人可以选择不自杀……)。

这个问题一般有两种问法：

• 给出自杀顺序。不少数据结构初学书都会以这个问题为习题考验读者对线性表的掌握。比较常见的解法是把所有存活的人组织成一个循环链表，这样做时间复杂度是O(n*m)的。另外可以使用order statistic tree(支持查询第k小的元素以及询问元素的排名)优化到O(n log n)。另外有篇1983年的论文An O(n log m) Algorithm for the Josephus Problem，但可惜我没找到下载链接。
• 求出最后一个人的编号。可以套用上一种问法的解法，但另外有更加高效的解法，下文展开讨论。

关于做题这回事，引用一下：

Chao Xu，Haskell用户.
acm算是用来训练秒面试题的一个方式。 像我这种非cs系学生全靠玩acm的训练秒各个公司。

深以为然。算法题带来的代码能力的效用实在是太大了，除了训练思维外对速度、准确性也有极大帮助。真切感受到解决一个大作业花了数小数编写，再花了更长的时间调试，和立刻写完、写完就对的差异。订阅过一些邮件列表，偶尔能看到一些非常苍白的问题的人，也能看到内容可能更空洞的回复。以及市面上很多浮夸的书。如果方法恰当潜心研习一段时间应该不会出现这样的问题呢。所以当我看到《编程之美》这个书名的时候，第一印象也是那类浮华的书，等待之前某次活动拿到一本看才发现不是，”编程“、”美“字样在我心目中的地位都被这些浮夸的事物玷污了。

我现在发现自己看过的东西拓扑顺序不太对了，简单说就是ld -la -lb -la，这可以算作一个tech joke吧。昨天经过fqj1994指导，今天终于把https开起来了，感觉又有所提高，好开心啊。

Approximate string matching

近似字符串匹配问题。

Levenshtein edit distance

在metric space中衡量两个字符串差异程度的一个指标，即通过一系列单字符的编辑操作把字符串A变成字符串B所需的最小编辑次数，其中的编辑操作可以是插入字符、删除字符以及修改字符。

计算编辑距离有个经典的Wagner-Fischer算法，使用了动态规划，用d(i,j)表示把字符串A的前i个字符变成字符串B的前j个字符所需的最小编辑次数（即子串的编辑距离）。

Parser之外的部分参考http://swtch.com/~rsc/regexp/regexp2.html ，代码都模仿自http://code.google.com/p/re1/source/browse 。注意到正则表达式是operator-precedence grammar，可以用一个扩展的Shunting-Yard算法来解析，其中用了一些特殊构造处理后缀操作符和括号。

Perfect maze

Perfect maze又称standard maze，指没有回路，没有不可达区域的迷宫。用图论的语言来说，就是可以用spanning tree表示的迷宫，保证迷宫中任意两个格子间都有唯一的路径。本文旨在探讨如何随机生成棋盘状perfect maze。迷宫格子的邻居的定义采用von Neumann neighborhood，即水平竖直方向相邻的四个格子。

变形Kruskal算法

说得通俗点，就是“随机拆墙”。

多日之前看到了Matrix67的《互联网时代的社会语言学：基于SNS的文本数据挖掘》，文中提到的方法是无监管的，而且无需词典就能提取词语，要素概括起来有两点：词的凝聚力，以及左右邻字的信息熵。今天把这个方法实现了一下。

对于凝聚力，我的理解是可以用词前后两部分的pointwise mutual information来描述，比如对于“博物馆”一词，考虑“博”与“物馆”之间，以及“博物”与“馆”之间的pointwise mutual information，两者取较小值作为“博物馆”这个词的凝聚力。

简介

Graph drawing即根据顶点和边的拓扑关系，将这张图展现出来。很明显，表现的形式种类是非常多的，如果精确到每个顶点的座标，那么方案有无穷多种。Graph drawing 目标是画出一张美观的图的布局来。美是个见仁见智的概念，何谓美？“每个本质在于旺盛的生命力，美的形象能够感染人的情感和鼓舞人心”，展现出来的图是否美每个人的看法可能都不一样，但有一些通用的要素是大家一般共同认可的，比如边的两端不能靠得太近也不能离得太远，相交边的数目要尽量少，有对称性等等。

缘由

和专业有关系的第一门有趣的课结束了，觉得有必要记录些什么。这篇文章就用来纪念我觉得最有意义的一次作业。

要求

需要分别编写MPI、Pthreads、OpenMP的并行实作。

层次

我不愿意把代码重复三份，分别为三种并行库编写程式，所以就用 autotools 管理项目，用不同的选项来启用不同的功能。这样做的另一个好处是很容易支持MPI+Pthreads或者MPI+OpenMP甚至是MPI+Pthreads+OpenMP，尽管这样混用不会带来性能上的提升。

Rush Hour是一款滑板游戏(这个词并不陌生，常见的滑板游戏还有华容道、八数码等）。规则很简单，看这里的图就明白了。

八数码问题，已访问状态采用 factorial number system 表示，未访问的未使用（简化代码） 实现了 Breadth First Search 和 Heuristic Search 两种算法。 带上命令行选项 -g 能输出 Graphviz 的 dot 格式的状态树。 比较满意的地方是把两种搜索算法的共同部分抽象出来了，写成了单独的 search 函数。

题目大意：有一个长为 N 的整数数列，每次可以把一个数增减一，求最少次数使得有连续 K 个数相同。 下面程序用 Size balanced tree 实现，卫星数据是子树节点数和子树关键字和。

似乎是某个TopCoder SRM的题目。

N 个球，有一个是坏的，坏球重量与好球不同（略轻/重于好球）。有一个天平，可以告知左右两边孰重孰轻，最小化最坏情况下称量次数，给出称量方案。下面讨论该问题的一个扩展——如何通过已知信息（即之前称量结果，之前的称量结果可能不是最优的）选择下一步称量方案，最小化最坏情况下的称量次数。

根据已有信息把所有球分为4类：

• 肯定是好球
• 不可能比好球轻（不能确定是否为坏球）
• 不可能比好球重（不能确定是否为坏球）
• 不知道任何信息

每个球必定属于以上四类中的某一类。我们只需知道每一类的数目即可，具体编号无关紧要。令\(s[nh][nl][nu]\)表示有\(nh\)个1类球，nl 个2类球，nu 个3类球，最坏情况下需要称量的次数。枚举一边放置的各类型球数 lh(1类),ll(2类),lu(3类)，枚举另一边放置的各类型球数 rh(1类),rl(2类),ru(3类),re(0类)。如果两边都有0类球，那么我们可以在两边各移去一个。我们可以保证0类球只出现在一边，不妨设为 rh(1类),rl(2类),ru(3类) 一边。