SLKun 发布的文章

LeetCode刷题Wrapper


起因

LeetCode上的题目放到本地调试很麻烦, 需要在本地新建一个Main方法来运行, 多TestCase的测试也需要写很多重复代码, 所以想写一个简单Wrapper将很多重复的工作放在里面来执行.

目标

使用Wrapper之后, 只需要将Solution类放入再实现getTestCase()即可.
这里的Solution类可以直接不作任何修改的复制粘贴到LeetCode中, 不需要任何额外的代码即可直接运行这个类.

public class Problem7 extends AbstractSolution{
    /**
     * Given a 32-bit signed integer, reverse digits of an integer.
     * <p>
     * Example 1:
     * Input: 123
     * Output: 321
     * <p>
     * Example 2:
     * Input: -123
     * Output: -321
     * <p>
     * Example 3:
     * Input: 120
     * Output: 21
     * <p>
     * Note:
     * Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
     */
    class Solution{
        @Resource
        public int reverse(int x){
            // 统一调整到负数来处理
            boolean isPositive = x >= 0;
            x = isPositive ? -x : x;

            int result = 0;
            while(x < 0 && result >= Integer.MIN_VALUE / 10){
                int n = x % 10;
                if(result == 0){
                    result = result + n;
                }else{
                    if(result == Integer.MIN_VALUE / 10 && x < -8){
                        break;
                    }
                    result = result * 10 + n;
                }
                x /= 10;
            }
            result = x < 0 ? 0 : result;

            return isPositive ? -result : result;
        }
    }

    @Override
    protected Map<?, ?> getTestCase(){
        return ImmutableMap.builder()
                .put(123, 321)
                .put(-123, -321)
                .put(120, 21)
                .put(1534236469, 0)
                .put(-2147483412, -2143847412)
                .put(1463847412, 2147483641)
                .put(1234, 111)
                .build();
    }
}

由于使用Guava, 所以可能还需要引入它的依赖到工程中.
另外, Solution类的入口方法需要放上@Resource注解, 否则Wrapper无法找到运行的入口方法.
运行的结果如下所示:

TestCase 0: Passed
TestCase 1: Passed
TestCase 2: Passed
TestCase 3: Passed
TestCase 4: Passed
TestCase 5: Passed
TestCase 6: Wrong
    Input: 1234
    Output: 4321
    Expected: 111
Some TestCase Failed!

解析

首先展示一下AbstractSolution的内容:

public abstract class AbstractSolution{
    /**
     * 1. 实例化SolutionWrapper类
     * 2. 找到目标的Solution类并获得实例
     * 3. 找到目标方法(用@Resource注解)
     * 4. 检查参数类型和TestCase是否匹配
     * 5. 使用TestCase运行目标方法
     */
    public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for(Class<?> c : classes){
            if(c.getName().endsWith("$Solution")){
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if(targetClass != null && targetClass.getDeclaredConstructors().length > 0){
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if(targetClass != null){
            Method[] methods = targetClass.getDeclaredMethods();
            for(Method m : methods){
                if(m.isAnnotationPresent(Resource.class)){
                    targetMethod = m;
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if(targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0){
            Class<?> parameterTypes = targetMethod.getParameterTypes()[0];
            Class<?> testCaseType = testCase.keySet().toArray()[0].getClass();
            if(ReflectionUtils.isAssignableFrom(testCaseType, parameterTypes)){
                runCases(targetInstance, targetMethod, testCase);
            }
        }
    }

    private static boolean runCases(Object targetInstance, Method targetMethod, Map<?, ?> testCase) throws InvocationTargetException, IllegalAccessException{
        int index = 0;
        boolean allPassed = true;
        for(Object input : testCase.keySet()){
            Object result = targetMethod.invoke(targetInstance, input);
            Object expectedResult = testCase.get(input);
            boolean passed = result.toString().equals(expectedResult.toString());
            allPassed = passed && allPassed;

            if(passed){
                System.out.printf("TestCase %d: Passed\n", index++);
            }else{
                System.out.printf("TestCase %d: Wrong\n"
                                + "\tInput: %s\n"
                                + "\tOutput: %s\n"
                                + "\tExpected: %s\n",
                        index++, input, result, expectedResult);
            }
        }
        System.out.println(allPassed ? "All TestCase Passed!" : "Some TestCase Failed!");
        return allPassed;
    }

    protected abstract Map<?, ?> getTestCase();
}

我们在Problem7类中运行的main()方法放在了AbstractSolution里, 首先我们需要获得实际子类的实例, 即Problem7类的实例.
AbstractSolution类里, 我们是没办法知道到底具体是哪一个子类调用的main()方法的, 如果想要知道有两种方法:

  1. 运行的命令行参数里, 会带上实际执行的子类.
    例如在这个例子中, 命令行参数是java algorithm.leetcode.Problem7. 这样从命令行参数就可以知道实际调用main()的类是Problem7了.
  2. 在加载子类之前, 父类一定会被加载. 因此, 我们遍历当前一遍所有加载的类, 看当前类的哪一个子类被加载了, 就可以知道实际调用的类.

在这里, 我使用的是第二种方法, 通过ReflectionUtils.getLoadedSubClass(AbstractSolution.class)来获取, 具体实现如下:

    @SuppressWarnings("unchecked")
    public static <T> Class<? extends T> getLoadedSubClass(Class<T> superClass){
        // Read Loaded Classes
        Collection<Class<?>> classes = getLoadedClass(Thread.currentThread().getContextClassLoader());

        // Find the SubClass of CurrentClass
        for(Class c : classes){
            if(c.getSuperclass() != null && superClass.equals(c.getSuperclass())){
                return c;
            }
        }
        throw new IllegalStateException("No Valid SubClass.");
    }

    /**
     * 获取指定类加载器已加载的类
     */
    @SuppressWarnings("unchecked")
    public static Collection<Class<?>> getLoadedClass(ClassLoader cl){
        try{
            Field f = ClassLoader.class.getDeclaredField("classes");
            f.setAccessible(true);
            return (Collection<Class<?>>)f.get(cl);
        }catch(NoSuchFieldException | IllegalAccessException e){
            e.printStackTrace();
        }
        throw new IllegalStateException("Unexpected Error.");
    }

ClassLoader本身是没有提供方法让你获得当前已加载的类, 但是存在一个private的classes属性包含所有已加载的类, 因此可以通过读取该属性来获得指定类加载已加载的类.

在获得Problem7的实例solutionWrapper后, 我们再从Problem7类中找到其内部类$Solution并实例化它.
需要注意的是, 这里不能直接用newInstance(), 因为内部类没有public的构造器, 只有包含外部类引用的private构造器, 所以需要首先获得这个构造器, 然后使用构造器实例化内部类.

在获得内部类targetClass以后, 再遍历所有的方法找到标记有注解的方法作为入口方法targetMethod.
这里用@Resouce注解的原因只是...我觉得用JDK自带注解就够了...

最后, 检查一下testCase的类型和targetMethod的参数类型是否匹配, 就可以调用targetMethod来实际执行Solution类里的实际方法了.
这里考虑到存在primitive类型和其包装类混用的情况, 所以首先将其都unwrap, 如果都为primitive类型那么一定是可以转型成功的(当然可能损失精度).
如果没有primitive类型, 那么使用isAssignableFrom()方法来判断; 如果一个primitive一个正常对象, 那么必然转型失败.

    /**
     * 检查是否可从target转型到source
     * 考虑两个primitive类型一定可以互转(可能损失精度)
     */
    public static boolean isAssignableFrom(Class<?> source, Class<?> target){
        source = Primitives.unwrap(source);
        target = Primitives.unwrap(target);

        // All Object
        if(source.isPrimitive() && target.isPrimitive()){
            return true;
        }else if(!source.isPrimitive() && !target.isPrimitive()){
            return source.isAssignableFrom(target);
        }else{
            return false;
        }
    }

总的来说, 大体上的思路就是这样了, 我觉得还是很有意思的.

总结

这么一番操作下来, 感觉对框架内部实现的很多东西了解得更深了呢233
之前简单的看过Spring-Core的内部实现, 也是大量类似的检查代码, 以及一吨设计模式→_→
实话说, 感觉设计得有点太过复杂了...不过有可能是我看的源码版本比较老吧233(Spring 3.1.1)

懒果然是人类进步的阶梯(并不

Update 2019-05-10:
我把AbstractSolution又改了改, 在方法上做标注还是有一些略麻烦...
我把它改成了标注在内部类上, 然后用lookup属性来指定待执行的方法, 或者选取第一个找到的Public方法

public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for(Class<?> c : classes){
            if(c.isAnnotationPresent(Resource.class)){
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if(targetClass != null && targetClass.getDeclaredConstructors().length > 0){
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if(targetClass != null){
            Method[] methods = targetClass.getDeclaredMethods();
            Resource annotation = (Resource)targetClass.getAnnotation(Resource.class);
            for(Method m : methods){
                if(!annotation.lookup().isEmpty()){
                    // specify by lookup
                    if(m.getName().equals(annotation.lookup())){
                        targetMethod = m;
                    }
                }else{
                    // first public method
                    if(Modifier.isPublic(m.getModifiers())){
                        targetMethod = m;
                    }
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if(targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0){
            Class<?> parameterTypes = targetMethod.getParameterTypes()[0];
            Class<?> testCaseType = testCase.keySet().toArray()[0].getClass();
            if(ReflectionUtils.isAssignableFrom(testCaseType, parameterTypes)){
                runCases(targetInstance, targetMethod, testCase);
            }
        }
    }

Update 2019-09-04:

以前做的居然不支持多参数输入, 醉了醉了...
验证参数类型其实挺麻烦的, 感觉在我这个场景下也不是特别重要就删掉了...只检查参数数目是否一致
然后输出的检测考虑到可能会有比较复杂的类型输出出来干脆就用gson全部转换到字符串然后比较字符串好了...

public abstract class AbstractSolution{
    private final static Gson gson = new GsonBuilder().create();

    /**
     * 1. 实例化SolutionWrapper类
     * 2. 找到目标的Solution类并获得实例
     * 3. 找到目标方法(用@Resource注解)
     * 4. 检查参数类型和TestCase是否匹配
     * 5. 使用TestCase运行目标方法
     */
    public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for (Class<?> c : classes) {
            if (c.isAnnotationPresent(Resource.class)) {
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if (targetClass != null && targetClass.getDeclaredConstructors().length > 0) {
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if (targetClass != null) {
            Method[] methods = targetClass.getDeclaredMethods();
            Resource annotation = (Resource)targetClass.getAnnotation(Resource.class);
            for (Method m : methods) {
                if (!annotation.lookup().isEmpty()) {
                    // specify by lookup
                    if (m.getName().equals(annotation.lookup())) {
                        targetMethod = m;
                    }
                } else {
                    // first public method
                    if (Modifier.isPublic(m.getModifiers())) {
                        targetMethod = m;
                    }
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if (targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0) {
            runCases(targetInstance, targetMethod, testCase);
        }
    }

    private static boolean runCases(Object targetInstance, Method targetMethod, Map<?, ?> testCase) throws InvocationTargetException, IllegalAccessException{
        int index = 0;
        boolean allPassed = true;
        for (Object input : testCase.keySet()) {
            // read params
            Object[] params;
            if (targetMethod.getParameterCount() > 1) {
                params = new Object[Array.getLength(input)];
                for (int i = 0; i < params.length; i++) {
                    params[i] = Array.get(input, i);
                }
            } else {
                params = new Object[]{input};
            }

            // check parameter length
            if (params.length != targetMethod.getParameterCount()) {
                throw new IllegalArgumentException("Incompatible Parameters.");
            }

            // actual invoke
            Object result = targetMethod.invoke(targetInstance, params);
            Object expectedResult = testCase.get(input);

            // compare string
            String inputStr = gson.toJson(input);
            String resultStr = gson.toJson(result);
            String expectedStr = gson.toJson(expectedResult);
            boolean passed = resultStr.equals(expectedStr);
            allPassed = passed && allPassed;

            if (passed) {
                System.out.printf("TestCase %d: Passed\n", index++);
            } else {
                System.out.printf("TestCase %d: Wrong\n"
                                + "\tInput: %s\n"
                                + "\tOutput: %s\n"
                                + "\tExpected: %s\n",
                        index++, inputStr, resultStr, expectedStr);
            }
        }
        System.out.println(allPassed ? "All TestCase Passed!" : "Some TestCase Failed!");
        return allPassed;
    }

    protected abstract Map<?, ?> getTestCase();
}

关于键盘的一些碎碎念


像我可能是对键盘不太挑的类型, 一直薄膜键盘用下来感觉也挺不错的.

其实也用过同学的机械, 无论是国产轴还是原厂轴, 亦或是青轴, 茶轴, 黑轴, 红轴都试过, 但始终觉得都不是我的菜.

依稀记得买的第一个键盘是Fuhlen L400, 39块钱买了不吃亏不上当, 其实我用起来一直感觉还是不错的, 直到最近发现shift键经常按下去谈不起来emmm

后来买了笔记本, 型号是Gigabyte U2442D, 这是一款每次拿出来总有人要问是什么牌子的笔记本2333

当然这时候我一般会装一个x: 这是全球第二大主板厂商(x

言归正传, 我觉得这款笔记本的键盘的使用体验还是相当不错的, 和同期mbp2013款的键盘使用体验不相上下.
也是就此, 我觉得自己其实喜欢上这种短键程的剪刀脚键盘, 特别是悬浮式巧克力键帽.
我可以很自然地把手掌放在桌子上, 然后手指在键盘上翻飞, 非常舒适. 但是像那种一般的高键帽键盘就...必须得悬空打字了, 实话说我觉得很不习惯

新款mbp的蝴蝶键盘就真的是...有一种强烈的按锅仔片的感觉

于是, 后来台式机买新键盘的时候, 我就买了Rapoo E9100P, 虽然作为一个薄膜键盘来说确实有些贵了, 但是不得不说使用体验还是很棒的, 比如说我现在就是在用这块键盘敲字www
其他的薄膜键盘的推荐可能是thinkpad那款了吧...不过高昂的价格让我望而却步Orz

最后就是最近, 因为之前说Fuhlen L400挂了嘛, 考虑到Rapoo E9100P给我带来的良好体验, 于是入手了一块Rapoo V500.
本来一开始打算再买一块Rapoo E9100P这个系列的, 但是还是感觉有些贵= =
而且考虑到毕业了, 估计也不会再要, 不如干脆买一个超入门机械好了→_→ 顺便也可以习惯一下悬空打字的感觉吧emmm

未来工作的话主力键盘, 如果能够习惯机械的感觉的话, 可能会考虑换一块Varmilo吧...
应该会买87键版的, 然后海韵蓝? 主要是太好看了啊啊啊啊啊啊啊啊(我就是颜狗)
应该会买无线版本吧...嗯

20190505002313983_14909.png
20190505002418824_5345.png


Update 2019-05-24:
用了一段时间以后发现Rapoo V500简直坑爆了, 手感什么的就不说了, 我倒要求不是那么高
但主要是有些组合键按不下去啊啊啊啊啊
一开始看到常用键无冲就没想那么多, 直到最近用sublime的时候发现命令面板Ctrl+Alt+P老是按不出来, 于是...测试了一下
QQ截图20190524083653.png
好吧...就是这垃圾键盘按不出来, 而且不只是Ctrl+Alt+P还有0/U/K/Enter也是...
emmmmmmmmmmmmmmmmmmm...........我那个40块的Fuhlen L400都不会这样啊摔
果然机械键盘一定要注意全键无冲么Orz


关于技术学习的一些思考


我觉得任何技术都可以从这么几个角度去考虑:

技术选型

  • 这个框架它解决了什么旧的问题? 又带来了什么新的问题?
  • 它与其他同类技术相比有什么特点? 其侧重点在什么地方?
  • 基于以上问题, 该框架适用于什么场合?

软件工程的一个基本原则就是没有银弹, 任何技术都有其适用的场合, 在学习一个技术之前先想清楚为什么要学它.

比如说, 微服务的两大主要优点是 分布式部署 和 代码解耦, 但问题是如果你的项目量级根本没有大到需要分布式部署, 而且业务的复杂程度也没有大到耦合度很高, 那么到底是为什么需要它呢? 不要忘记了, 一项技术会有优点的同时那么必然也会有缺点以及其带来的问题.

优点没有享受到, 反倒是被缺点坑到吐血, 那就是本末倒置了.

当然你说是做技术储备, 从长远考虑, 那当我没说.

技术学习

一般来说, 技术文档可以分为三类: Tutorial, User Guide和Reference

  • 首先应该看的是Tutorial, 一般是step-by-step的教你做一个基本的demo出来.
  • 然后应该看的是User Guide, 一般是介绍整体功能结构以及常见场景的解决方案.
  • 最后是Reference, 基本上就是事无巨细的罗列所有功能了.

一般来说, Tutorial用来快速上手, 深入学习需要User Guide看一遍, Reference那就纯粹是查漏补缺了, 需要的时候翻一翻就行.

我个人的学习路线基本上是:

  • 首先通过step-by-step的Tutorial快速构建出一个demo, 了解其基本写法
  • 然后根据User Guide, 在demo上进行魔改以完成我所想的功能
  • 如果遇到一些奇葩问题, 可以去stackoverflow上看看有没有解答
  • 如果没有, 可能就需要去怼源码了→_→

学习Tutorial的时候可能很重要的一点是, 不仅仅是照着做, 更要想清楚为什么要这么做, 每一行都有什么用, 我能不能不这么写, 有没有别的写法.

技术总结

纸上得来终觉浅,绝知此事要躬行

在使用技术的过程中, 更要去思考和总结, 还是上面提到的几个问题:

  • 横向比较: 它与其他同类框架相比有什么特点?
  • 纵向比较: 这个框架它解决了什么问题? 又带来了什么问题?
  • 最后: 基于以上问题, 该框架适用于什么场合?

这是软件工程层面的, 从纯技术层面上, 在使用过程中会逐渐对其机制逐渐了解, 那么能不能从机制反推出框架内部的实现原理?

  • 如果实现一个功能类似的框架, 会怎么设计?
  • 框架现有的一些坑, 如果重新设计的话, 会怎么去设计?

带着以上问题再去学习源码, 必然是事半功倍, 你会了解到:

  • 框架的设计和你的设计有什么不同, 侧重点分别在什么地方?
  • 为什么框架会有这些坑? 也许是没想到, 那么你可以提交PR, 也许只是一种折衷和妥协, 那么为什么要这么妥协?
  • 如果你发现你的理念和现有框架的理念完全不同, 在某一方面又有突出优势, 那么说不定你就可以开个新的框架了呢233

技术本身不是重点, 重点是技术背后的思想和设计理念.

就好比挖沙子, 到底用铁铲挖还是挖掘机挖其实取决于你到底要挖多少沙子(不同场景). 挖基坑可以用挖土机, 那挖古墓还用挖土机? 而且会用铁铲挖了再去学怎么用挖掘机挖很难吗? 毕竟造挖掘机的人也是从用铲子挖开始的.
更重要的是, 怎么从挖掘机联想到推土机, 甚至是如何去自动化整个造房子的过程.


最大正方形


问题

0,1矩阵中最大的全1正方形

例如:

int[][] a = {
    {0, 1, 1, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {1, 1, 0, 1, 1},
    {1, 1, 1, 1, 1},
    {0, 1, 1, 1, 0},
    {0, 1, 1, 1, 0},
};

答案应该是: 2

解答

朴素的思路

思路上是把一个二维搜索问题变成了一个一维搜索问题
即将二维数组转化为柱状图, 在柱状图上找正方形, 例如上述例子转为柱状图后:

0, 1, 1, 1, 0, 
0, 2, 0, 2, 0, 
0, 3, 1, 3, 0, 
1, 4, 2, 4, 1, 
2, 5, 0, 5, 2, 
3, 6, 1, 6, 3, 
0, 7, 2, 7, 0, 
0, 8, 3, 8, 0, 

具体的找法比较绕口, 不如直接看代码:

private static int findMaxSquare(int[][] array){
    if(array.length == 0) return 0;

    int rows = array.length, cols = array[0].length;
    for(int i = 1; i < rows; i++){
        for(int j = 0; j < cols; j++){
            if(array[i][j] > 0){
                array[i][j] = array[i - 1][j] + 1;
            }
        }
    }

    int maxVal = 0;
    for(int[] row : array){
        for(int i = 0; i < cols - maxVal; i++){
            if(row[i] > maxVal){
                int cnt = 0, maxLen = row[i];
                for(int j = i; j < cols && cnt < maxLen && row[j] > cnt; j++, cnt++){
                    maxLen = Math.min(maxLen, row[j]);
                }
                maxVal = Math.max(maxVal, cnt);
            }
        }
    }
    return maxVal;
}

简单的来说, 就是找到可能的正方形左下角点以后, 向右搜索(cnt < maxLen && row[j] > cnt):

  • 一方面走的步数(cnt)不能大于目前已经走过的所有值的最小值(maxLen)
  • 另外一方面已经走过的值(row[j])必须大于当前走过的步数(cnt)

总而言之, 这是一个最坏情况O(N^3)的方法, 不过总体来说, 其实性能不算太差.

动态规划

如果一个点的它的左边, 左上, 上边至少构成某个长度(n)的正方形的话, 那么这个点应该能构成一个更大的正方形(n+1)
这样说起来可能有点绕...看例子吧:

0, 1, 1, 1, 0, 
0, 1, 0, 1, 0, 
0, 1, 1, 1, 0, 
1, 1, 2, 2, 1, 
1, 2, 0, 1, 2, 
1, 2, 1, 1, 2, 
0, 1, 2, 2, 0, 
0, 1, 2, 3, 0, 

题目中的例子整个状态空间如上图所示, 很显然...状态方程如下是成立的:

$$dp[i][j] = \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1$$

所以实现下来的话...

private static int findMaxSquare(int[][] array){
    if(array.length == 0) return 0;
    int rows = array.length, cols = array[0].length, maxVal = 0;
    
    int[][] dp = new int[rows][cols];
    for(int i = 0; i < rows; i++){
        if(array[i][0] == 1){
            dp[i][0] = 1;
            maxVal = 1;
        }
    }
    for(int j = 0; j < cols; j++){
        if(array[0][j] == 1){
            dp[0][j] = 1;
            maxVal = 1;
        }
    }

    for(int i = 1; i < rows; i++){
        for(int j = 1; j < cols; j++){
            if(array[i][j] == 1){
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
            maxVal = Math.max(maxVal, dp[i][j]);
        }
    }
    return maxVal;
}

总而言之, 这是一个最坏情况O(N^2)的方法, 只用把数组扫描一遍即可Orz

总结

动态规划的主要难点在于想出状态方程...


神奇的Unsafe类: Java实例内存布局初探


前情提要

Java相比C/C++最大的一个特点就是没有提供指针, 或者说没有提供对内存的直接访问操作, 导致很多比较底层的操作根本无法进行.
一方面给Java带来了内存上的安全性, 不像C/C++稍微一处理不好就会Segment Fault, 更可怕的是内存访问越界了程序却没有退出, 这会导致程序发生一些莫名其妙的事情, 比如说由于错误修改了循环的迭代变量导致循环无法退出(被坑过的我流下了眼泪)等.
但另一方面降低了Java的灵活性, 也让人无法弄清楚Java的运行时内存布局, 以及进行一些神奇的Hack操作.

但是在Hotspot虚拟机中, 提供了UnSafe类可以给我们进行很多非常底层的虚拟机操作, 包括:

  • 根据对象和偏移读写内存的getInt(Object o, long offset)/putInt(Object o, long offset, int x)
  • 根据地址直接读写内存的getAddress(long address)/putAddress(long address, long x)
  • 在直接内存区(Direct Memory)中分配内存的allocateMemory(long bytes)/freeMemory(long address), 这部分内存主要是被java.nio中的类所使用
  • 内存直接复制copyMemory(Object srcBase, long srcOffset, Object destBase, long destOffset, long bytes) 类似于memcpy
  • 属性偏移计算方法objectFieldOffset(Field f)
  • 一些底层内存信息addressSize()/pageSize()
  • 从字节码直接生成一个类defineClass(String name, byte[] b, int off, int len)
  • 加载实例也不是一个问题allocateInstance(Class cls)
  • 手动模拟Synchronized的加锁解锁操作monitorEnter(Object o)/monitorExit(Object o)
  • 抛出一个异常throwException(Throwable ee)
  • 喜闻乐见的CAS操作compareAndSwapObject(Object o, long offset, Object expected, Object x)
  • 以volatile模式操作某个属性getIntVolatile(Object o, long offset)
  • 读值并直接相加/设置的新原语getAndAddInt(Object var1, long var2, int var4)/getAndSetInt(Object var1, long var2, int var4)
  • 栅栏操作storeFence()/loadFence()

等等

不过, Oracle已经在JDK11里正式移除Unsafe类, 毕竟这些底层操作从某种角度来说破坏了Java构建的安全性, 虽然似乎其实有大量的开源框架都在使用该类, 比如Spring/Netty/Hadoop等等, 在新的JDK11下似乎也有替换的解决方案.
不过这些都不是重点, 本文的重点是如何通过Unsafe类提供的getAddress(long address)观察对象实例的内存布局.

正篇开始

Java的对象实例内存布局其实是一个老生常谈的问题了, 无论是著名的深入理解Java虚拟机还是网上都有很多文章说过这个问题, 但是我几乎没有看到结合实验来说明实例布局的实际情况的文章, 所以本文从实验的角度来说明这个问题.

对象实例内存布局总的来说, 可以分为三块:

  • 对象头
  • 实例数据
  • 对齐填充

下图展示了32位虚拟机的情况:
20190314172833568_30071.png

事实上, 对于64位虚拟机来说对象头其实有128Bit, 也就是16Byte. 在没有开启对象指针压缩的前提下, 对象头的布局才是如下所示:

|------------------------------------------------------------------------------------------------------------|--------------------|
|                                            Object Header (128 bits)                                        |        State       |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                                  Mark Word (64 bits)                         |    Klass Word (64 bits)     |                    |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
| unused:25 | identity_hashcode:31 | unused:1 | age:4 | biased_lock:1 | lock:2 |    OOP to metadata object   |       Normal       |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
| thread:54 |       epoch:2        | unused:1 | age:4 | biased_lock:1 | lock:2 |    OOP to metadata object   |       Biased       |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                       ptr_to_lock_record:62                         | lock:2 |    OOP to metadata object   | Lightweight Locked |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                     ptr_to_heavyweight_monitor:62                   | lock:2 |    OOP to metadata object   | Heavyweight Locked |
|------------------------------------------------------------------------------|-----------------------------|--------------------|
|                                                                     | lock:2 |    OOP to metadata object   |    Marked for GC   |
|------------------------------------------------------------------------------|-----------------------------|--------------------|

不过, 从JDK6开始, JVM就会默认开启对象指针压缩, 如果要让内存的结构如上图所示, 必须要手动关掉它-XX:-UseCompressedOops才行.

Talk is cheap. Show me the code.

public class MemoryAccess{
    private final static Unsafe unsafe = getUnsafe();
    public int a = 12345678;
    public int b = 87654321;
    public long c = -1;
    public char d = 66;

    public static void main(String[] args){
        MemoryAccess o = new MemoryAccess();
        long base = getBaseAddress(o), size = sizeOf(o);
        System.out.printf("Base: %x, Size: %d\n", base, size);

        // Read Memory First
        readMemory(base, size);

        // Fetch HashCode
        System.out.printf("HashCode: %x\n", o.hashCode());

        // Read a first
        System.out.println("Old a Val: " + o.a);
        // Modify a via memory
        int offset = 24, newAVal = 23333333;
        long newMemoryVal = (unsafe.getAddress(base + offset) & 0xffffffff00000000L) + newAVal;
        unsafe.putAddress(base + offset, newMemoryVal);
        // Read a again
        System.out.println("New a Val: " + o.a);

        // Read Memory Again
        readMemory(base, size);
    }

    static Unsafe getUnsafe(){
        try{
            Field f = Unsafe.class.getDeclaredField("theUnsafe");
            f.setAccessible(true);
            return (Unsafe)f.get(null);
        }catch(NoSuchFieldException | IllegalAccessException e){
            e.printStackTrace();
        }
        return null;
    }

    public static long sizeOf(Object object){
        long metaAddr = unsafe.getInt(object, 8L);
        return unsafe.getAddress(metaAddr + 4L) >>> 32;
    }

    static long getBaseAddress(Object obj){
        Object[] array = new Object[]{obj};
        long baseOffset = unsafe.arrayBaseOffset(Object[].class);
        return unsafe.getLong(array, baseOffset);
    }

    static void readMemory(long base, long length){
        System.out.printf("| %3s | %79s | %17s | %23s |\n", "Offset", "Binary", "Hex", "Dec");
        for(int i = 0; i < length; i += 8){
            long val = unsafe.getAddress(base + i);
            int leftVal = (int)(val >> 32);
            int rightVal = (int)(val);
            System.out.printf("| %6d | %s | %8x %8x | %11d %11d |\n", i, getLongBinaryStr(val), leftVal, rightVal, leftVal, rightVal);
        }
    }

    static String getLongBinaryStr(long val){
        return getLongBinaryStr(val, true);
    }

    static String getLongBinaryStr(long val, boolean padding){
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < 64; i++){
            if(padding && i % 4 == 0 && i != 0){
                builder.insert(0, " ");
            }
            builder.insert(0, val & 0x1);
            val = val >>> 1;
        }
        return builder.toString();
    }
}

简单解释一下:

  • getUnsafe用于获取Unsafe类的实例, 因为Unsafe类本来的设计是限定在rt.jar的内部使用, 直接使用getUnsafe()方法的话, 它会在内部验证Caller的类加载器是否为空, 即BootstrapClassLoader.
public static Unsafe getUnsafe() {
    Class cc = sun.reflect.Reflection.getCallerClass(2);
    if (cc.getClassLoader() != null)
        throw new SecurityException("Unsafe");
    return theUnsafe;
}
  • sizeOf用于获取对象实例的大小, 首先是从对象头中取得类在方法区的指针, 然后通过取方法区中的数据获得类的实例大小.
  • getBaseAddress用于获取一个对象实例的基地址, Unsafe类中也没有提供获得对象基地址的方法, 这里用了一个非常巧妙的方法, 即先把对象放到一个数组中, 然后读取数组的值即可知道对象指针的值, 也就是对象实例的基地址了.
  • readMemory用于从基地址开始打印指定长度的内存到控制台, 由于getAddress只能以64bit读取数据, 这里将这64bit分成左右两个部分分别显示十六进制和十进制值
  • getLongBinaryStr用于将long长度的数用带前缀0的二进制打印出来, Long.toBinaryString()是没有前缀0的

输出的结果如下所示:

Base: d4dc74e0, Size: 40
| Offset |                                                                          Binary |               Hex |                     Dec |
|      0 | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 |        0        1 |           0           1 |
|      8 | 0000 0000 0000 0000 0000 0000 0000 0000 0001 0111 1110 0011 0100 0010 0100 0000 |        0 17e34240 |           0   400769600 |
|     16 | 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 | ffffffff ffffffff |          -1          -1 |
|     24 | 0000 0101 0011 1001 0111 1111 1011 0001 0000 0000 1011 1100 0110 0001 0100 1110 |  5397fb1   bc614e |    87654321    12345678 |
|     32 | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0010 |        0       42 |           0          66 |
HashCode: 6e0be858
Old a Val: 12345678
New a Val: 23333333
| Offset |                                                                          Binary |               Hex |                     Dec |
|      0 | 0000 0000 0000 0000 0000 0000 0110 1110 0000 1011 1110 1000 0101 1000 0000 0001 |       6e  be85801 |         110   199776257 |
|      8 | 0000 0000 0000 0000 0000 0000 0000 0000 0001 0111 1110 0011 0100 0010 0100 0000 |        0 17e34240 |           0   400769600 |
|     16 | 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 | ffffffff ffffffff |          -1          -1 |
|     24 | 0000 0101 0011 1001 0111 1111 1011 0001 0000 0001 0110 0100 0000 1001 1101 0101 |  5397fb1  16409d5 |    87654321    23333333 |
|     32 | 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0100 0010 |        0       42 |           0          66 |

我们可以看到对象的基地址是0xd4dc74e0, 对象的长度是40Byte.

前128Bit就是之前提到的对象头, 后面的数据分别是64bit长度的属性c=-1, 由于Intel x86是小端序, 所以接下来是32bit长的属性a=12345678和32bit长的属性b=87654321, 最后是8bit长的属性d=66, 以及补齐到64bit对齐的填充0.
和书中说的一样, 实例数据部分会优先分配比较长的属性, 并尽量将相同宽度的属性放在一起.

对于对象头, 参考之前的对象头表, 0x17e34240是指向metadata的指针, 对象长度也是从这个指针所指向的内存中获取的, 而MarkWord部分, 却只知道对象现在是无锁状态(01), 为什么理应放hashCode的部分是0呢?

因为我们还没有计算过hashCode, 只有计算过hashCode, 那么在对象头部分才会将hashCode的值填入.
我们读取过一遍hashCode以后, 再次读取对象头部分的时候, 就会发现hashCode部分存入了之前计算出的hash值, 即0x6e0be858.
从此可见, 对象头中的hashCode相当于是一层简单的缓存, 避免对同一个对象hashCode的重复计算.

后面的代码演示了, 通过直接对内存进行修改来修改对象属性的值. 我们首先读取了属性a的值为12345678, 通过直接对内存进行修改, 我们就其的值改为了23333333.
这里的offset可以通过对对象实例内存进行观察得到, 也可以通过之前提到的objectFieldOffset(Field f)方法获得, 我猜大概也可以直接从方法区中类的metadata中读到.

另外就是这里没有演示出来的一点, 对象的metadata和类的class对象在内存里没有任何关系, 类的class对象也是一个位于堆区的普通对象, 是Class类的一个实例.

总结与展望

通过对Unsafe的操作, 我们能够对对象实例部分的内存进行任意读写, 经过测试, 整个堆区的内存都是可以任意读写的.
这从某种角度来说提供了一个高效的修改对象的方式, 相比反射过程冗长的检查过程, 这种方式简单直接当然也很容易出错, 而且非常依赖于具体的实现.

通过对对象实例内存的读取, 可以对对象实例内存的布局和数据变化有了更加深入的认识和了解, 实例内存布局不再是一个简单的图表或者一个虚拟机实现的头文件, 而是实实在在的数据变化.

考虑到, 我们可以通过对象实例获取到对象方法区的指针, 那么可以通过方法区内存的读取, 从而得到类在方法区内存的布局.
更进一步说, 如果我们能够找到对象的方法表, 而且这块内存可写, 那么我们其实可以做到方法级的Hook操作.
目前已知的一些Hook, 无论是自定义类加载器/动态代理或者是Instrument机制, 我们都只能整体的替换一个类, 而不能做到精准地只替换掉一个方法.
也许, 通过这种操作, 能够实现单独对一个方法的替换.

当然, 这样的hack操作肯定不会在生产环境中使用, 但是从对JVM深入理解以及好玩的角度来说, 我觉得继续探究一下还是挺有意思的.

Ref1: http://mishadoff.com/blog/java-magic-part-4-sun-dot-misc-dot-unsafe/
Ref2: https://github.com/keerath/openjdk-8-source/blob/master/jdk/src/share/classes/sun/misc/Unsafe.java