概要
关于“彩蛋”，数据结构与算法系列博客中，如有可能，博主尽量会在每一篇博客里埋下彩蛋。彩蛋的意义在刚开始写博客的开篇有说明过，实际就是算法实现过程的一些小技巧，而这些小技巧往往都是可以改进执行效率的。关于所有的彩蛋都会有特别的解释说明，千里之行始于足下，共勉～
LeetCode进阶944-算法优化
彩蛋
进阶版对比普通版效率上有质的提高，主要是将双重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进阶226-翻转二叉树（华为面试题）
彩蛋
对比三种实现代码执行结果会发现，三种方法最终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;
}
<font color="#FF0000">源码中的addElement被synchronized修饰，整个方法体做了加了同步锁。</font>
- 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方法，<font color="#FF0000">三个方法均没发现synchronized关键字</font>
小结
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的使用。最后，如果觉得本篇对你有所帮助不妨关注一波，来个赞~
扫一扫 关注我的微信订阅号
网友评论