arts-20200628

Algorithm

比特位计数

题目：给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

• Sample 1
  • input: 2
  • output: [0, 1, 1]
• Sample 2
  • input: 5
  • output: [0, 1, 1, 2, 1, 2]
    给出 O(n) 一趟遍历的解法

分析：

1. 设计算 n 的 bits 中 1 的个数的过程为 f(n)，则输出为 [f(0), f(1), ..., f(n)]，至少需要遍历一遍
2. 根据题目要求，联想到只有当前的状态可以根据前一步状态来简单计算来得到才能满足要求，看起来是个标准的 dp
3. dp 方程
   1. 首先盲猜 n 和 n-1 的关系，简单列举了几个不太有思路
   2. 然后想到 int 有移位操作，特别是右移位(>>)时，符号位不变，对于正整数来说减少了一个1，所以有 f(n) = f(n >> 1) + g(n) 其中 g(n)是 n 最低位 1 的个数，我们知道
      1. n 为奇数时 n % 2 == 1, n 为偶数时 n % 2 == 0
      2. n % 2 等价于 n & 1，且后者更快
         因此 f(n) = f(n >> 1) + (n & 1)
4. 最终代码如下

   class Solution {
       public int[] countBits(int num) {
           int [] bits = new int[num + 1];
           if (num == 0) {
               return bits;
           }
           bits[1] = 1;
           for (int i = 2; i <= num; i++) {
               bits[i] = bits[i >> 1] + (i & 1);
           }
           return bits;
       }
   }

5. 看了 disscuss，发现有大佬提到 n & (n - 1) 可以去掉最后一个 1，因此还有一种解法 f(n) = f(n & (n - 1)) + 1

Review

Embracing Immutable Architecture https://medium.com/react-weekly/embracing-immutable-architecture-dc04e3f08543

1. 作者认为：状态是软件工程复杂性之源，变化的状态让代码难以理解和维护，不可变状态是控制复杂性的有效手段。
2. 核心要素
   1. 严格限制的状态转移，例如只允许 pure function 修改状态
   2. 单向数据流
3. 个人理解
   1. 和 functional programming 理念类似，状态不可变、只允许新增状态，好处是不共享状态所以不会有并发问题
   2. 追求 pure function，会使得函数结果很容易预测，不容易出bug，另外编译器可以提前做优化，性能上有些提升
   3. 并非使用所有场景，每次都创建新的状态可能性能开销很大，需要工程师作出权衡
   4. 基础架构领域也有这个趋势，例如部署方式上 Docker 和 tomcat war 包的区别，前者每次部署都使用新 image，而后者是在同一个 web container 做原地升级

Tip

1. 关于 kotlin 的实践
   1. kotlin 和 java 混写
      1. 不能使用 lombok
         • 原因
           • 根据官方的说法，kotlin 和 java 混写时，需要 kotlin 在 java 之前被编译see https://kotlinlang.org/docs/reference/using-maven.html
           • lombok 是编译时注解，Getter, Setter, Constructor 等根据注解生成的方法都需要编译成字节码之后才有
         • 解决办法
           • 把 带lombok 注解的 java 代码用插件 Delombok
      2. 编译插件配置
         • 需要为 kotlin-maven-plugin 指定 java 和 kotlin 源代码路径，e.g.

           <plugin>
               <groupId>org.jetbrains.kotlin</groupId>
               <artifactId>kotlin-maven-plugin</artifactId>
               <version>${kotlin.version}</version>
               <executions>
                   <execution>
                       <id>compile</id>
                       <phase>compile</phase>
                       <goals>
                           <goal>compile</goal>
                       </goals>
                       <configuration>
                           <sourceDirs>
                               <sourceDir>${project.basedir}/src/main/kotlin</sourceDir>
                               <sourceDir>${project.basedir}/src/main/java</sourceDir>
                           </sourceDirs>
                       </configuration>
                   </execution>
                   <execution
           </plugin>

      3. 打包指定 Main Class
         • 原因：在 java 项目打包时，通常需要指定 Main Class 作为项目的入口，而在纯 kotlin 代码中，main 函数通常是下面这种写法

           // Foo.kt
           // empty class
           class Foo {}
           
           fun main(args: Array<String>) {
               // do something
           }

         • 看了下编译结果，编译生成的类为 FooKt.class，在 pom 里写上就ok了

           Share

           benchmark 是工程是进行性能分析的必备工具，jmh 作为 openjdk 生态中的重要工具，广泛应用在各大开源项目中，本文简单介绍下 jmh 的 HelloWorld，作为工程师快速上手 jmh 的小参考, see openjdk tools - Hello jmh