Posts

观点： 通过实现“值类型”，实现inline优化，又不改变Java全是引用类型的语义。 论据 思想实验： int x = 1; // x指向内存地址A，内容是整数1 int y = x; // （记住这个y） y指向同样的内存地址A，内容是整数1 x = 2; // x指向另一个内存地址B，内容是整数2。y仍然指向地址A，内容是1。 System.out.println(x); System.out.println(y); // out: // 可以看到 // 2 // 1 引用类型特有那些操作？ dereference；例如C中*a struct的分量访问和修改；例如，C中的a.foo = 1 而对于「基本类型」，以上操作均不能实现。 前者由于Java不提供；后者由于「基本类型」不是复合类型，也就无法实现。 引用= 的语义？ 将引用绑定给一个新的对象。 那么我们的「基本类型」能做什么事情？ 读取它的值 修改它的值 那么，实际上，值类型的实现和引用类型的实现本质上的结果完全一致。 由此得出结论，对于「基本类型」，值类型和引用类型等价。 对这篇文章的疑惑 语义上，我们难道不是按照值类型的语义来传递参数的吗？ 难道按照引用传递，不属于引用类型的语义吗？ public void test() throws Exception{ int x = 2; foo(x); // 传递了值 System.out.println(x); } public static void foo(int x) { x = 3; } // out: // 可以看见传递了值 // 2 参数传递的语义？ 值传递：将值拷贝一份绑定给参数。...

Data Flow Analysis: Foundations 在应用篇的所有算法，都可以看作是 Iterative Algorithm 现在，我们从形式化 Formal的角度来审视这些算法： A Functional View of Iterative Algorithm (Define)Given a CFG i.e.: a program with k nodes, the iterative algorithm updates $OUT[n]$ for every node n in each iteration. (Domain)Assume the domain of the values in data flow analysis is $V$, then we can define a K-tuple $$ (OUT[n_1],OUT[n_2],…,OUT[n_k]) $$ as an element of set $(V_1 \times V_2 \times … \times V_k)$ denoted as $V^k$, to hold the values of the analysis after each iteration....

Data Flow Analysis：Applications Overview What is Data Flow Analysis ? How application-specific Data flows on CFG with safe approximation. 分析算法感兴趣的数据如何流经控制流图。 CFG Nodes (Basic Blocks) 基本块 Edges (Control Flow) 控制流 CFG(a program) 整个程序 Safe Approximation safe approximation for different purposes 不同的分析目的，对于safe有不同的定义: Must Analysis：Under Approximation May Analysis: Over Approximation 相同点：这两种目的往往殊途同归地达到Soundness。 不同的目的对应了不同的手段：1. Data Abstraction 2. Approximation Strategies i.e. transfer functions & control flow handling. Preliminaries for Data Flow Analysis Input & Output States Definition:...

LC390.消除游戏 Created: January 2, 2022 1:46 PM 声明：我写的文章只是为了只有一个目的———把方法讲清楚、讲通透。 OJ上很少存在某个人原创的方法，大部分只是对已有的方法的重复。 ⚠️长度警告 Brute Force 暴力法 我们先来分析数组手动模拟的不可行性。 注意到 $1 \le n \le 10^9$。假设每个数 16bit，存放所有中间数需要最多 $16 \times 10^9$bit 也就是约 2GB！！。 就算预处理第一轮去除所有奇数，也要1GB。 要知道一般的OJ平台的上限仅仅是MB级别。因此，显然不可行。 我们必须寻求一些数学方法，一个是从数列的角度，一个是从函数的角度。 数列的角度 从题目的描述来看，我们的输入，无论怎么消除，仅仅只是一串等差数列。 回顾等差数列的三要素：1. 首项 $a_1$； 2. 公差 $d$； 3. 项数 $n$； 并有如下公式成立： $$a_n = a_1 + (n-1)\cdot d$$ 因此，就没有必要再存储数列中的每个元素的值了。 如果把输入看作是一个等差数列 $a^0$。e.g. 1, 2, 3, 4 ,5 那么，消除第一轮的产生一个新的等差数列 $a^1$。e.g. 2, 4 那么，消除第二轮的产生一个新的等差数列 $a^2$。e.g. 2 以此类推，消除$turn$轮产生一个新的等差数列 $a^{turn}$。 不难看出，每一轮消除过后存在一下差别： 公差 $d$ 加倍了 首项 $a_1$ 变了 项数 $n$ 变了 于是我们就要探索一下这三者是怎么变的：...