LeetCode进阶-彩蛋二

关于“彩蛋”，数据结构与算法系列博客中，如有可能，博主尽量会在每一篇博客里埋下彩蛋。彩蛋的意义在刚开始写博客的开篇有说明过，实际就是算法实现过程的一些小技巧，而这些小技巧往往都是可以改进执行效率的。关于所有的彩蛋都会有特别的解释说明，千里之行始于足下，共勉～

彩蛋

进阶版对比普通版效率上有质的提高，主要是将双重for循环的内存循环拆成了独立的方法，这便是本文的彩蛋。	
复制代码

源码

• 双重for循环

public int minDeletionSize1(String[] A) {
		if (A.length == 0) return 0;
		int count = 0;
		for (int i = 0; i < A[0].length(); ++i) {
			for (int j = 1; j < A.length; ++j) {
				if (A[j].charAt(i) < A[j - 1].charAt(i)) {
					count++;
					break;
				}
			}
		}
		return count;
	}
复制代码

• 封装

public int minDeletionSize1(String[] A) {
		if (A.length == 0) return 0;
		int count = 0;
		for (int i = 0; i < A[0].length(); i++) {
			for (int j = 1; j < A.length; j++) {
				if (A[j].charAt(i) < A[j - 1].charAt(i)) {
					count++;
					break;
				}
			}
		}
		return count;
	}
复制代码

字节码

• 双重for循环

public int minDeletionSize1(java.lang.String[]);
    Code:
       0: aload_1
       1: ifnonnull     6
       4: iconst_0
       5: ireturn
       6: iconst_0
       7: istore_2
       8: iconst_0
       9: istore_3
      10: iload_3
      11: aload_1
      12: iconst_0
      13: aaload
      14: invokevirtual #2                  // Method java/lang/String.length:()I
      17: if_icmpge     69

      20: iconst_1
      21: istore        4
      23: iload         4
      25: aload_1
      26: arraylength
      27: if_icmpge     63
      30: aload_1
      31: iload         4
      33: aaload
      34: iload_3
      35: invokevirtual #3                  // Method java/lang/String.charAt:(I)C
      38: aload_1
      39: iload         4
      41: iconst_1
      42: isub
      43: aaload
      44: iload_3
      45: invokevirtual #3                  // Method java/lang/String.charAt:(I)C
      48: if_icmpge     57

      51: iinc          2, 1     //++count
      54: goto          63       //break继续内层for循环
      57: iinc          4, 1     //++j
      60: goto          23       //继续内层for循环  

      63: iinc          3, 1    //++i
      66: goto          10      //继续外层for循环
      69: iload_2
      70: ireturn
复制代码

• 封装

public int minDeletionSize2(java.lang.String[]);
    Code:
       0: aload_1
       1: ifnonnull     6
       4: iconst_0
       5: ireturn
       6: iconst_0
       7: istore_2
       8: iconst_0
       9: istore_3
      10: iload_3
      11: aload_1
      12: iconst_0
      13: aaload
      14: invokevirtual #2                  // Method java/lang/String.length:()I
      17: if_icmpge     37

      20: aload_1
      21: iload_3
      22: invokestatic  #4                  // Method isNoSort:([Ljava/lang/String;I)Z
      25: ifeq          31
      28: iinc          2, 1

      31: iinc          3, 1
      34: goto          10
      37: iload_2
      38: ireturn

  public static boolean isNoSort(java.lang.String[], int);
    Code:
       0: iconst_1
       1: istore_2
       2: iload_2
       3: aload_0
       4: arraylength
       5: if_icmpge     35
       8: aload_0 
       9: iload_2
      10: aaload
      11: iload_1
      12: invokevirtual #3                  // Method java/lang/String.charAt:(I)C
      15: aload_0
      16: iload_2
      17: iconst_1
      18: isub
      19: aaload
      20: iload_1
      21: invokevirtual #3                  // Method java/lang/String.charAt:(I)C
      24: if_icmpge     29

      27: iconst_1             //true赋值
      28: ireturn              //return true
      29: iinc          2, 1   //++i
      32: goto          2      //继续内层for循环
      35: iconst_0             //false赋值
      36: ireturn              //return false
复制代码

分析

比较双重for循环和封装的字节码会发现，核心的字节码实现基本是一致。细节上有略微区别（主要表现在注释的几行），封装法的字节码实现甚至在代码行数上甚至并不具备优势。但是仔细观察对比封装实现的字节码方法体的goto指令（32）和双重for循环实现的字节码中的goto指令（60），再对比字节码中循环体的开始位置，封装法goto：0～32，双重for循环goto：20～60，结合goto指令实际移动栈针中指针位置的特点，封装对比双重for循环实际在多次循环的情况下对指针的操作开销会更低一些。

小结

封装除了能对复杂的业务逻辑代码进行拆分解耦，提高代码可读性、可维护性。同时在一些场景下也能提高程序执行效率，双重for循环就是最经典的实例。

彩蛋

对比三种实现代码执行结果会发现，三种方法最终leetcode测评的效率都是100%，但是方法一的runtime时间确实1ms，而方法二和方法三的runtime却是0ms。为什么同样的算法思想使用不同的数据结构，使用Stack比使用LinkedList要慢呢？这便是本篇的彩蛋！
复制代码

源码

• 栈实现

public TreeNode invertTree(TreeNode root) {	        
	        if (root == null) {
	            return null;
	        }
	        Stack<TreeNode> stack = new Stack<>();
	        stack.push(root);	        
	        while(!stack.isEmpty()) {
	            final TreeNode node = stack.pop();
	            final TreeNode left = node.left;
	            node.left = node.right;
	            node.right = left;           
	            if(node.left != null) {
	                stack.push(node.left);
	            }
	            if(node.right != null) {
	                stack.push(node.right);
	            }
	        }
	        return root;
	    }
复制代码

• 队列实现

public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			TreeNode left = node.left;
			node.left = node.right;
			node.right = left;
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		return root;
	}
复制代码

分析

本质上是由于不同的数据结构在底层源码实现的不同导致。上述两种方法执行主要不同在于分别使用了stack.push、stack.pop（栈实现）和queue.offer、queue.pop方法（队列实现）。对比下两者实现源码：

• Stack的push方法源码分析

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items.
 *
 * <p>A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 * <pre>   {@code
 *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 *
 * @author  Jonathan Payne
 * @since   JDK1.0
 */
public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }

    /**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);

        return item;
    }
    ...

}
复制代码

Stack类继承自vector，push方法中调用子类Vector中的addElement,Vector类中addElement的源码：

/**
     * Adds the specified component to the end of this vector,
     * increasing its size by one. The capacity of this vector is
     * increased if its size becomes greater than its capacity.
     *
     * <p>This method is identical in functionality to the
     * {@link #add(Object) add(E)}
     * method (which is part of the {@link List} interface).
     *
     * @param   obj   the component to be added
     */
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
复制代码

源码中的addElement被synchronized修饰，整个方法体做了加了同步锁。

• LinkedList的offer方法源码分析

/**
     * Adds the specified element as the tail (last element) of this list.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Queue#offer})
     * @since 1.5
     */
    public boolean offer(E e) {
        return add(e);
    }
    
    ...
    
    /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    ...
    
    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
复制代码

LinkedList类中，offer方法调用add方法，add方法调用linkedLast方法，三个方法均没发现synchronized关键字

小结

synchronized同步会大大较低方法执行效率，talk is cheap,show me the code:

public static void main(String[] args) {
		Syn syn = new Syn();
		long start1 = System.nanoTime();
		for (int i = 0; i < 1000; i++) {
			syn.test1();
		}
		System.out.println("syn耗时(ms):" + Long.toString((System.nanoTime() - start1) / 1000));

		long start2 = System.nanoTime();
		for (int i = 0; i < 1000; i++) {
			syn.test1();
		}
		System.out.println("非syn耗时(ms):" + Long.toString((System.nanoTime() - start2) / 1000));
	}

	public synchronized int test1() {
		return 1;
	}

	public int test2() {
		return 1;
	}
复制代码

• 执行结果

syn耗时(ms):126
非syn耗时(ms):37
复制代码

进一步证明了synchronized同步会降低执行效率，但是为什么synchronized会降低执行效率？笔者推荐阅读《深入理解Java虚拟机》第13章，由于主题和篇幅关系本篇不具体展开。

总结

本篇核心结论，两个重点：1、多使用方法封装，减少嵌套for循环；2、Stak比LinkedList高效，由于基类方法加了锁，而锁会降低执行效率，除非必要减少synchronized的使用。最后，如果觉得本篇对你有所帮助不妨关注一波，来个赞~