ARTS第十周

之前忘了发布

1.Algorithm：每周至少做一个 leetcode 的算法题
2.Review：阅读并点评至少一篇英文技术文章
3.Tip：学习至少一个技术技巧
4.Share：分享一篇有观点和思考的技术文章

以下是各项的情况：

Algorithm

链接：[LeetCode-19]-remove-nth-node-from-end-of-list

题意：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

分析：

　　只有三个配对
　　循环时,如果有符合条件的配对.就会将符合条件的配对替换成"",然后进入下一次循环...
　　如果循环时,没有符合条件的配对,这时length == s.length(),循环退出.并返回
　　如果字符全部配对成功.字符最后会被替换后变为空字符.当空字符进入循环时,因为没有可配对的内容.三次配对都会失败.这时length == s.length(),循环退出.并返回

class Solution {

   public boolean isValid(String s) {

　　/* 只有三个配对
　　循环时,如果有符合条件的配对.就会将符合条件的配对替换成"",然后进入下一次循环...
　　如果循环时,没有符合条件的配对,这时length == s.length(),循环退出.并返回
　　如果字符全部配对成功.字符最后会被替换后变为空字符.当空字符进入循环时,因为没有可配对的内容.三次配对都会失败.这时length == s.length(),循环退出.并返回*/
　　

　　 if (s.equals(""))
　　　　return true;
　　while (true) {
　　int length = s.length();
　　s = s.replace("()", "");
　　s = s.replace("[]", "");
　　s = s.replace("{}", "");
　　if (length == s.length())
　　　　break;
　　}
　　　　return s.length() == 0;
　　}

暴力做法

class Solution {

    int i;

    public ListNode removeNthFromEnd(ListNode head, int n) {

        if(head == null){

            i=0;

            return null;

        }

        head.next = removeNthFromEnd(head.next,n);

        i++;

        if(i==n) return head.next;

        return head;

     }

}

Review

分享 JVM内存模型　

　JVM自诞生就是为了实现“编写一次，随处运行 ”的目的。 Sun Microsystems 创建了JVM -- 对底层OS的抽象，解释了编译的Java代码。 JVM是JRE（Java运行环境）的核心组件，创建运行Java代码，但现在可使用其他语言（Scala，Groovy，JRuby，Closure 等等 ......）

分享的这篇主要讲的就是 JVM 的 “运行数据区域” （Runtime Data Areas）

Contents [hide]

先总体介绍了下有哪几部分知识点组成，

基于堆栈的体系结构，然后做了简要的介绍，举了例子：（因为觉得已经忘完了有必要复习所以记录如下）

　　举例栈里计算 3+4

　　　　如果要在字节码中添加3和4：

首先在操作数堆栈中压入3和4。
然后调用iadd指令。
iadd将弹出操作数堆栈的最后2个值。
将int结果（3 + 4）压入操作数堆栈，以供其他操作使用。

接下来介绍了字节码和操作

　　（记录下：）

public class Test {

  public static void main(String[] args) {

    int a =1;

    int b = 15;

    int result = add(a,b);

  }

  public static int add(int a, int b){

    int result = a + b;

    return result;

  }

}

“ javac Test.java ”命令在Test.class中生成一个字节码。由于Java字节码是二进制代码，因此人类无法读取。Oracle在其JDK javap中提供了一个工具，该工具可以将二进制字节码转换为JVM规范中易于阅读的带有标签的操作代码集。

命令“ javap -verbose Test.class ”给出以下结果：

Classfile /C:/TMP/Test.class

  Last modified 1 avr. 2015; size 367 bytes

  MD5 checksum adb9ff75f12fc6ce1cdde22a9c4c7426

  Compiled from "Test.java"

public class com.codinggeek.jvm.Test

  SourceFile: "Test.java"

  minor version: 0

  major version: 51

  flags: ACC_PUBLIC, ACC_SUPER

Constant pool:

   #1 = Methodref          #4.#15         //  java/lang/Object."<init>":()V

   #2 = Methodref          #3.#16         //  com/codinggeek/jvm/Test.add:(II)I

   #3 = Class              #17            //  com/codinggeek/jvm/Test

   #4 = Class              #18            //  java/lang/Object

   #5 = Utf8               <init>

   #6 = Utf8               ()V

   #7 = Utf8               Code

   #8 = Utf8               LineNumberTable

   #9 = Utf8               main

  #10 = Utf8               ([Ljava/lang/String;)V

  #11 = Utf8               add

  #12 = Utf8               (II)I

  #13 = Utf8               SourceFile

  #14 = Utf8               Test.java

  #15 = NameAndType        #5:#6          //  "<init>":()V

  #16 = NameAndType        #11:#12        //  add:(II)I

  #17 = Utf8               com/codinggeek/jvm/Test

  #18 = Utf8               java/lang/Object

{

  public com.codinggeek.jvm.Test();

    flags: ACC_PUBLIC

    Code:

      stack=1, locals=1, args_size=1

         0: aload_0

         1: invokespecial #1                  // Method java/lang/Object."<init>":()V

         4: return

      LineNumberTable:

        line 3: 0

  public static void main(java.lang.String[]);

    flags: ACC_PUBLIC, ACC_STATIC

    Code:

      stack=2, locals=4, args_size=1

         0: iconst_1

         1: istore_1

         2: bipush        15

         4: istore_2

         5: iload_1

         6: iload_2

         7: invokestatic  #2                  // Method add:(II)I

        10: istore_3

        11: return

      LineNumberTable:

        line 6: 0

        line 7: 2

        line 8: 5

        line 9: 11

  public static int add(int, int);

    flags: ACC_PUBLIC, ACC_STATIC

    Code:

      stack=2, locals=3, args_size=2

         0: iload_0

         1: iload_1

         2: iadd

         3: istore_2

         4: iload_2

         5: ireturn

      LineNumberTable:

        line 12: 0

        line 13: 4

}

然后是重点： 运行数据区

　　　　介绍了原理（本质是堆）

　　　　介绍了方法范围

方法区域是所有Java虚拟机线程之间共享的内存。在虚拟机启动时创建的，并由类加载器从字节码加载。只要加载它们的类加载器处于活动状态，方法区域中的数据就会保留在内存中。

方法区域存储：

类信息（字段/方法的数量，超类名称，接口名称，版本等）
方法和构造函数的字节码。
每个类加载的运行时常量池。

规范：不强制在堆中实现方法。例如，在 JAVA7 之前，Oracle HotSpot 使用一个名为 PermGen 的区域来存储“方法区域”。PermGen 区域 与 Java 堆（以及像堆一样由 JVM 管理的内存）是连续的，并且被限制为默认空间 64MB（由参数-XX：MaxPermSize修改）。从Java 8开始，HotSpot 现在将“方法区域”存储在称为 Metaspace 的隔离开的本机内存空间中，最大可用空间是总可用系统内存。

注意：方法区域不能超过最大大小。如果超过此限制，JVM将抛出 OutOfMemoryError。

　　　　介绍了运行时常量池

该池是“方法区域”的子部分。由于它是元数据的重要组成部分，因此Oracle规范描述了“方法区域”之外的运行常量池。对于每个加载的类/接口，此常量池都会增加。该池就像常规编程语言的符号表。换句话说，当引用类，方法或字段时，JVM使用运行时常量池在内存中搜索实际地址。它还包含常量值，例如字符串文字或常量图元。

String myString1 = “This is a string litteral”;

static final int MY_CONSTANT=2;

　　　　介绍了 PC寄存器 （有空翻翻组成原理对照下）

反正就是为了记录当前正在执行的Java虚拟机指令（在方法区域中）的地址

　　　　介绍了 JAVA虚拟机堆栈（线程）还有 堆在 JVM 里工作原理

　　　　　　这里打个断点，需要补充上工作原理

最后说（线程中）本机方法堆是由JNI（Java本机接口）调用的本机代码的堆栈？？没看懂，估计翻的不对。

Tip

　为什么一般数组都是从0开始编号？（重温数据结构）

　　　首先 重温数组概念 ：

　　1. 数组（Array）就是一种线性表数据结构，用一组连续内存空间来存储一组具有相同类型的数据。

　　线性表结构：数组，链表，队列，栈　　非线性表：比如二叉树，堆，图等　　　

　 2. 连续的内存空间和相同类型的数据

　　因为这两个特性或者说是限制，拥有一个性质： “随机访问”。顾名思义，可以随机地去访问数据，但相应的，让数组的很多操作变的非常低效，比如想在数组中删除，插入一个数据，运气不好就必须后移大量数据。

　　　　拓展：因为当插入一个新元素时，如果插入末尾，那么此时时间复杂度为O（1），所以如果要将某个数组插入到第K个位置，为了避免大量的数据迁移，我们有一个简单的方法就是：直接将第K位置数据搬移到数组的最后，把新元素直接放入到第K个位置。这种处理思想也会在快速排序中使用到。

　　同理，删除操作，比如数组A[10]删除前三个元素，为了避免后面元素要搬移三次，我们可以先记录下已经删除数据 . 每次删除操作并不是真正的搬移数据，只是记录数据已经被删除。当数组没有更多空间去存储数据时候，我们才

　　触发真正的删除操作 , 删掉前三个元素 , 剩下原数组其他元素向前移动三个位置即可。而这种思路正是JVM标记清楚垃圾回收算法的核心思想。

　　　　其次 我们需要警惕数组的访问越界问题

　　例如 : 下面一段C语言代码乍看上去没有问题

int main(int args,char* arg[])

{

   int i = 0 ;

   int arr[3] = {0};

   for(; i<=3 ; i++)

  {

     arr[i] = 0;

     printf("hello world\n");

  }

   return 0 ;

}

　　看起来会是输出三次hello world , 实际上是无线循环打印hello world ，这是为什么？

　　实际因为数组大小为3 : A[0] , A[1 , A[2] 。而代码中for循环的结束条件写成了 i<=3 而非 i<3 ，导致当i=3时候， A[3]访问越界。 C 语言中 , 只要不是访问首先的内存，所有的内存空间都是可以自由访问的。根据数组寻址公式 , A[3]也会被定为到某块不属于数组的内存地址上 , 而这个地址如果正好是存储变量 i 的内存地址 , 那么A[3]=0 就相当于 i=0 , 就会导致代码无限循环。

　　数组越界在C语言是因为没有规定数组访问越界时候，编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址可用 , 那么程序就可能不会报任何错误。而JAVA就不会像C一样，把数组检查的工作丢给程序员去判断，也因此会出现我们日常中头疼仅次于java.lang.NullPointerException: null 的错误异常 : java.lang.ArrayhIndexOutOfBoundsException 。

　　　　比如这段代码 :

int[] a = new int[3];

a[3] = 10 ;

　　就会抛出java.lang.ArrayhIndexOutOfBoundsException

　　最后 回到提出的问题 ：这些都了解后就可以来思考为什么数组要从0开始编号，而非从1 ?

　　　　从数组的内存模型来看 , 下标意味着"偏移"(offset) 。如果用 A 来表示数组的首地址， A[0] 代表偏移为0 的位置，即是首地址，而 A[K] 就代表偏移K个type_size的位置，所以计算 A[K]的内存地址：

　　A[K]_address = base_address + K * type_size

　　　　但是从1开始计数的话 , 计算 A[K]的内存地址的公式就变为：

　　A[K]_address = base_address + (K-1) * type_size

　　　从1开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。为了提高效率，减少这一次不必要的减法操作，数组从0 开始编号变成约定俗成的，甚至是默认的规则。另一方面也是因为历史原因： C语言设计就是从0开始编号，其他语言为了减少程序员学习难度就直接照搬。实际上，虽然大多数编程语言都默认数组从0开始，但还是有不少例外的，例如 python 就支持负数下标（但数组下标仍然默认从0开始记数，举这个例子是为了说明虽然Python从功能上可以支持默认从负数下标开始，但为了减少学习难度还是从0开始）， MATLAB 就是从1开始计数。

　　这周看到管理“深度系统”微服务：与Ben Sigelman的问答。

　　 InfoQ最近与LightStep首席执行官，OpenTracing和OpenTelemetry项目的创始人Ben Sigelman进行了交谈，讨论了在深层系统中管理微服务的挑战，在深层系统中，单个服务所有者与他们不拥有的大量服务依赖项进行交互。问题出在控制与责任之间的差异，以及团队可以准确确定每种服务内部和之间发生的事情的方式。服务彼此调用时，沟通链不断加深，使团队快速诊断特定位置发生错误或速度变慢的能力变得复杂，然后 Sigelman 针对这个主题讲了不少自己的看法。我觉得有帮助，分享出来。

巴特西

ARTS第十周

Algorithm

Review

Tip

为什么一般数组都是从0开始编号？（重温数据结构）

Share

最新文章

热门文章