LeetCode.118.杨辉三角（简单）

class Solution {
    fun climbStairs(n: Int): Int {
        if (n == 1) return 1
        if (n == 2) return 2
        var pre1 = 2
        var pre2 = 1
        var cur = 0
        for (i in 3..n) {
            cur = pre1 + pre2
            pre2 = pre1
            pre1 = cur
        }
        return cur
    }
}

Java8 Lambda表达式

发表于 2019-10-25 更新于 2022-07-04 分类于 Java Disqus：

Java8 Lambda表达式有什么限制？

Java8的lambda和匿名类可以实现类似闭包的功能：它们可以作为参数传递给方法，并且可以访问其作用域之外的变量。

但有一个限制：它们不能修改定义Lambda方法的局部变量的内容。这些变量必须是隐式final的。

之所以会有这些限制，主要是由于局部变量是保存在栈上的，如果Lambda可以直接访问局部变量，且Lambda是在另一个线程使用的，那么使用Lambda的线程可能会在分配该变量的线程将这个变量收回之后，去访问该变量。因此，Java在访问自由局部变量时，实际上访问的是它的副本，而如果局部变量仅会赋值一次那就没什么区别了。

如果允许捕获可变的局部变量，就会引发造成线程不安全的可能性，而这是我们极力希望避免的。基于种种考虑，Java直接在语法层面做出限制，这其实也是不鼓励程序员使用改变外部变量的典型的命令式编程模式。

Java8 Lambda表达式是怎么实现的？

对lambda表达式里的代码，生成静态私有方法，创建一个函数式接口类的实例来调用这个私有静态方法。

这种方式实现的好处在于：

使用预定义的函数式接口类，不用新增类，避免新类的加载、验证、解析、初始化的耗时。
lambda表达式代码翻译到字节码的过程，可以动态的改变，方便做统一的优化。

为什么Java 8的Lambda表达式的字节码指令要使用invokedynamic指令？

Java8的设计者之一Brian Goetz对于lambda表达式的设计文档中所提到的方案选择：

一是转换策略要足够灵活以能够应对将来的优化。
二是要维持现有class文件标准的稳定性。

用invokedynamic指令干了什么？

invokedynamic调用JDK里的LambdaMetafactory类的方法来把Lambda表达式翻译为字节码。

不用invokedynamic的坏处？

如果把Lambda表达式的翻译方式写死在类的字节码，以后不方便统一修改翻译策略了。

Java8 Lambda表达式为什么不用匿名内部类实现？

Lambda表达式在语法上看起来就跟匿名内部类一样。

但是对于匿名内部类：

编译器会为每个匿名类生成一个新的class文件。由于每个class文件在使用前都需要经过一系列的加载、验证、解析、初始化的过程，大量的类文件会直接影响应用的启动性能。
每个新的匿名类都会为类或者接口产生一个新的子类型。如果你为了实现一个比较器，使用了一百多个不同的lambda表达式，这意味着该比较器会有一百多种不同的子类型。这种情况下，JVM的运行时性能调优会变得更加困难。

为什么Java8的特性需要Android Gradle插件特定版本才能支持？

Android系统上，Java-Bytecode（JVM字节码）是不能直接运行在Android系统上的，需要转换成Android-Bytecode（Dalvik/ART 字节码）。

为什么呢？比如Java 8的Lambda表达式是通过invokedynamic指令实现的，Android的dex编译器不支持invokedynamic指令，导致Android不能直接支持Java 8。

既然不能直接支持，那就只能在Java-Bytecode转换到Android-Bytecode这一过程中想办法，间接支持。这个间接支持的过程我们统称为Desugar（脱糖）过程。

具体是怎么实现的呢？比如Java 8的Lambda表达式，javac编译过后，Lambda表达式里的逻辑会被编译为私有静态方法，然后用invokedynamic去在运行时动态创建一个类实例，每个Lambda表达式都会对应一个函数式类接口的，在类方法里调用静态方法。脱糖的过程，就是把invokedynamic指令去除，直接调用静态方法。

脱糖

脱糖即在编译阶段将在语法层面一些底层字节码不支持的特性转换为基础的字节码结构，(比如 List 上的泛型脱糖后在字节码层面实际为 Object)； Android 工具链对 Java8 语法特性脱糖的过程可谓丰富多彩，当然他们的最终目的是一致的：使新的语法可以在所有的设备上运行。

D8编译器已经支持脱糖，让 Java 8 提供的特性（如 lambdas）可以转换成 Java 7 特性。

D8、R8编译器有什么特别？

D8 编译器作为默认的 DEX 字节码文件编译器，具有更好的性能；

R8 作为 ProGuard 的替代工具，用于代码的压缩（shrinking）和混淆（obfuscation）；

Java 7-8-9 等等新引入的语言特性并不能直接就能用在 Android 开发中，基本上现在的所有的 Android 开发者还在被困在 Java 6 SE 上。

为了让我们能使用上 Java 8 的特性，Google 使用了 Transformation 来增加了一步编译过程叫 desugaring，其实就是将我们代码里使用的 java 8 新特性翻译为 Dalvik/ART 能够识别的 java 6 字节码。这不可避免会导致一个问题 - 更长的编译时间。

为了解决这个问题，在 Android Studio 3.2 中，Google 使用 D8 替换了旧的 dx 编译器。D8 的主要改进是消除 desuguaring 的过程，让其成为 dex 编译的一部分，从而加快编译速度。

参考资料

卡顿检测 - BlockCanaryEx浅析

发表于 2019-08-20 更新于 2022-07-04 分类于源码分析 Disqus：

BlockCanaryEx检测主线程卡顿的原理是什么?

给Looper设置自定义的Printer，Looper的loop()方法在处理一个消息的前后会调用Printer的println()方法，通过这个方法就可以计算主线程处理每一个消息的耗时。

这一原理与BlockCanary相同，不同的是两者采集的信息不同。

阅读全文 »

卡顿检测 - BlockCanary浅析

发表于 2019-08-15 更新于 2022-07-04 分类于源码分析 Disqus：

BlockCanary检测卡顿基本原理

利用Looper.setMessageLogging()设置自定义的Printer。
主Handler一条消息处理前后会分别调用Printer的方法。
在消息处理前做线程堆栈采样，消息处理完时结束采样。
如果一条消息处理时间过长，就认为是卡顿，上报采样结果

BlockCanary缺点？

采样数据占用一定CPU资源。
采样的堆栈并不准确，有可能遗漏真正发生卡顿的代码堆栈。

阅读全文 »

ASM字节码插桩

发表于 2019-08-08 更新于 2022-07-04 分类于虚拟机 Disqus：

ASM是干什么的？

ASM 是一个 Java 字节码操控框架。

ASM 可以直接产生二进制 class 文件，也可以在类被加载入 Java 虚拟机之前动态改变类行为。

Java class 被存储在严格格式定义的 .class 文件里，这些类文件拥有足够的元数据来解析类中的所有元素：类名称、方法、属性以及 Java 字节码（指令）。

ASM 从类文件中读入信息后，能够改变类行为，分析类信息，甚至能够根据用户要求生成新类。

ASM的应用场景有AOP（CGLIB就是基于ASM）、热部署、修改其他jar包中的类等。

用ASM修改类的好处？

类的修改是硬编码在新生成的类文件内部的，没有反射带来性能上的付出。
越过Java常规语法限制，做出代码编写无法实现的事情。

字节码操纵操作工具很多，ASM有什么优势？

常见的字节码操作工具有：

ASM
JavaAssist
AspectJ（基于BCEL）
CGLIB（基于ASM）
ByteBuddy（基于ASM）

ASM优势：

体积小
性能高

ASM劣势：

需要熟悉字节码原理，API易用性低

JavaAssist优势：

不需要熟悉字节码原理，API易用性高

JavaAssist劣势：

体积大
性能差

所以ASM适用于对性能和体积敏感的场景。

参考：

Dynamic Java Bytecode Manipulation Framework Comparison

Visitor模式怎么理解？

把可变的和不变的分离。

具体而言，被访问者是不变的，而访问者是可变的。举个例子来说，我是不变的，而不同的人看我会有不同的眼光，这个看我的眼光是可变的。

访问者模式把数据结构和作用于结构上的操作解耦合，使得操作集合可相对自由地演化。

访问者模式适用于数据结构相对稳定，算法又易变化的系统。
因为访问者模式使得算法操作增加变得容易。

若系统数据结构对象易于变化，经常有新的数据对象增加进来，则不适合使用访问者模式。

访问者模式的优点：

增加操作很容易，因为增加操作意味着增加新的访问者。访问者模式将有关行为集中到一个访问者对象中，其改变不影响系统数据结构。

访问者模式的缺点：

增加新的数据结构很困难。

简单来说，访问者模式就是一种分离对象数据结构与行为的方法，通过这种分离，可达到为一个被访问者动态添加新的操作而无需做其它的修改的效果。

参考：

ASM为什么用Visitor模式？

.class 文件的结构是固定的，主要有常量池、字段表、方法表、属性表等内容，通过使用访问者模式在扫描 .class 文件中各个表的内容时，就可以修改这些内容了。

ASM的思想是什么？

ClassReader 的 accept 方法中传进来了一个参数ClassVisitor。在内部，ClassVisitor会不断的读取ClassReader的二进制byte[]，然后在解析后通过参数classVisitor的抽象visitXXX方法将属性全部转发出去。

参考：

Android 中使用ASM，对Activity生命周期打点统计

ASM API

分为核心API和树形API

核心API

ASM Core API可以类比解析XML文件中的SAX方式，不需要把这个类的整个结构读取进来，就可以用流式的方法来处理字节码文件。好处是非常节约内存，但是编程难度较大。然而出于性能考虑，一般情况下编程都使用Core API。在Core API中有以下几个关键类：

ClassReader：用于读取已经编译好的.class文件。
ClassWriter：用于重新构建编译后的类，如修改类名、属性以及方法，也可以生成新的类的字节码文件。
各种Visitor类：如上所述，CoreAPI根据字节码从上到下依次处理，对于字节码文件中不同的区域有不同的Visitor，比如用于访问方法的MethodVisitor、用于访问类变量的FieldVisitor、用于访问注解的AnnotationVisitor等。为了实现AOP，重点要使用的是MethodVisitor。

树形API

ASM Tree API可以类比解析XML文件中的DOM方式，把整个类的结构读取到内存中，缺点是消耗内存多，但是编程比较简单。TreeApi不同于CoreAPI，TreeAPI通过各种Node类来映射字节码的各个区域，类比DOM节点，就可以很好地理解这种编程方式。

Intellij Idea 中 ASM Bytecode Outline 插件

可以把java代码转为ASM框架的代码。

参考：

Android Studio 使用 ASM Bytecode Outline 插件来研究Java字节码

ASM如何使用？

ClassWriter是ClassVistor的实现类。

处理逻辑都写自定义ClassVisitor里。

模板的拦截代码如下：

ClassReader classReader = new ClassReader("meituan/bytecode/asm/Base");
ClassWriter classWriter = new ClassWriter(ClassWriter.COMPUTE_MAXS);

//处理
ClassVisitor classVisitor = new MyClassVisitor(classWriter);
classReader.accept(classVisitor, ClassReader.SKIP_DEBUG);
byte[] data = classWriter.toByteArray();

//输出
File f = new File("/classes/meituan/bytecode/asm/Base.class");
FileOutputStream fout = new FileOutputStream(f);
fout.write(data);
fout.close();

代码示例：在一个方法前后分别插入方法

例如有一个类

public class TestBean {
    public void halloAop() {
        AopInterceptor.beforeInvoke();
        System.out.println("Hello Aop");
        AopInterceptor.afterInvoke();
    }
}

要插入AopInterceptor的beforeInvoke()和afterInvoke()在TestBean的halloAop()的执行前后。

public class AopInterceptor {
    public static void beforeInvoke() {
        System.out.println("before");
    };

    public static void afterInvoke() {
        System.out.println("after");
    };
}

在自定义ClassVisitor的visitMethod方法中拦截halloAop方法，对不是halloAop的方法返回null表示不处理，对halloAop的拦截处理交给AopMethod类

class AopClassAdapter extends ClassVisitor {
    public AopClassAdapter(int api, ClassVisitor cv) {
        super(api, cv);
    }

public MethodVisitor visitMethod(int access, String name,
    String desc, String signature, String[] exceptions) {
        if ("<init>".equals(name))
            return null;//放弃原有类中所有构造方法
        if (!name.equals("halloAop"))
            return null;// 只对halloAop方法执行代理
        MethodVisitor mv = super.visitMethod(access, name, desc, signature, exceptions);
        return new AopMethod(this.api, mv);
    }
}

MethodVisitor中

visitCode方法，它会在ASM开始访问某一个方法的Code区时被调用，重写visitCode方法，将AOP中的前置逻辑就放在这里。

每当ASM访问到无参数指令时，都会调用MyMethodVisitor中的visitInsn方法。我们判断了当前指令是否为无参数的“return”指令，如果是就在它的前面添加一些指令，也就是将AOP的后置逻辑放在该方法中。

class AopMethod extends MethodVisitor implements Opcodes {
    public AopMethod(int api, MethodVisitor mv) {
        super(api, mv);
    }

    public void visitCode() {
        super.visitCode();    
        this.visitMethodInsn(INVOKESTATIC,"org/more/test/asm/AopInterceptor", "beforeInvoke", "()V");
    }

    public void visitInsn(int opcode) {
        if (opcode == RETURN) {//在返回之前安插after 代码。
            mv.visitMethodInsn(INVOKESTATIC, "org/more/test/asm/AopInterceptor", "afterInvoke", "()V");
        }
        super.visitInsn(opcode);
    }
}

参考：

invokevirtual指令执行方法后，方法的返回值存放在哪？

存放在栈帧的操作栈中。

当一个方法刚刚开始执行的时候，这个方法的操作数栈是空的，在方法的执行过程中，会有各种字节码指令往操作数栈中写入和提取内容，也就是出栈和入栈操作。

举个例子，例如整数加法的字节码指令iadd，这条指令在运行的时候要求操作数栈中最接近栈顶的两个元素已经存入了两个int型的数值，当执行这个指令时，会把这两个int值出栈并相加，然后将相加的结果重新入栈。

参考

局部变量表的执行过程？

参考：

虚拟机字节码执行引擎
深入理解Java虚拟机（第2版）第8章虚拟机字节码执行引擎
- 8.2.1 局部变量表
- 8.4.3 基于栈的解释器的执行过程

MethodNode有什么作用？

可以获取方法体内部的字节码指令等方法的一切信息

MethodNode有什么使用场景？

微信Android客户端卡顿检测工具：Matrix-Android-TraceCanary

判断一个方法是空方法？

遍历字节码指令，没有有效的字节码指令就是空

代码如下：

private boolean isEmptyMethod() {  
    ListIterator<AbstractInsnNode> iterator = instructions.iterator();  
    while (iterator.hasNext()) {  
        AbstractInsnNode insnNode = iterator.next();  
        int opcode = insnNode.getOpcode();  
        if (-1 == opcode) {  
            continue;  
        } else {  
            return false;  
        }  
    }  
    return true; 
}

判断扫描的函数是否只含有 PUT/READ FIELD 等简单的指令



private boolean isGetSetMethod() {
    int ignoreCount = 0;
    ListIterator<AbstractInsnNode> iterator = instructions.iterator();
    while (iterator.hasNext()) {
        AbstractInsnNode insnNode = iterator.next();
        int opcode = insnNode.getOpcode();
        if (-1 == opcode) {
            continue;
        }

        if (opcode != Opcodes.GETFIELD
                && opcode != Opcodes.GETSTATIC
                && opcode != Opcodes.H_GETFIELD
                && opcode != Opcodes.H_GETSTATIC
                && opcode != Opcodes.RETURN
                && opcode != Opcodes.ARETURN
                && opcode != Opcodes.DRETURN
                && opcode != Opcodes.FRETURN
                && opcode != Opcodes.LRETURN
                && opcode != Opcodes.IRETURN
                && opcode != Opcodes.PUTFIELD
                && opcode != Opcodes.PUTSTATIC
                && opcode != Opcodes.H_PUTFIELD
                && opcode != Opcodes.H_PUTSTATIC
                && opcode > Opcodes.SALOAD) {
            if (isConstructor && opcode == Opcodes.INVOKESPECIAL) {
                ignoreCount++;
                if (ignoreCount > 1) {
                    return false;
                }
                continue;
            }
            return false;
        }
    }
    return true;
}

判断一个方法是不是仅调用另外一个方法

private boolean isSingleMethod() {
    ListIterator<AbstractInsnNode> iterator = instructions.iterator();
    while (iterator.hasNext()) {
        AbstractInsnNode insnNode = iterator.next();
        int opcode = insnNode.getOpcode();
        if (-1 == opcode) {
            continue;
        } else if (Opcodes.INVOKEVIRTUAL <= opcode && opcode <= Opcodes.INVOKEDYNAMIC) {
            return false;
        }
    }
    return true;
}

参考资料

字典树

发表于 2019-07-07 更新于 2022-07-04 分类于算法 Disqus：

字典树特点

查询快
存储少

对相同前缀的字符串进行了压缩存储，存储空间少，访问一个字符串最多也只需要访问字符串的长度。

利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。

字典树有什么应用场景？

单词联想预测、单词纠错。

在搜索引擎中关键词提示，引擎会自动弹出匹配关键词的下拉框。

字符串检索

事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。

例如：

1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。
给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。

这样一方面可以节约存储空间，另一方面先用字典树预处理了海量文本，之后进行字符串查找时，不用在整个文本中查找特定字符串

词频统计

给定很长的一个串，统计频数出现次数最多情况。

例如：

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

字符串最长公共前缀

Trie树利用多个字符串的公共前缀来节省存储空间，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀，所以可以利用这个特点来解决一些前缀问题。

例如：

给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？