概要
關(guān)于“彩蛋”，數(shù)據(jù)結(jié)構(gòu)與算法系列博客中，如有可能，博主盡量會在每一篇博客里埋下彩蛋。彩蛋的意義在剛開始寫博客的開篇有說明過，實際就是算法實現(xiàn)過程的一些小技巧，而這些小技巧往往都是可以改進(jìn)執(zhí)行效率的。關(guān)于所有的彩蛋都會有特別的解釋說明，千里之行始于足下，共勉～
LeetCode進(jìn)階944-算法優(yōu)化
彩蛋
進(jìn)階版對比普通版效率上有質(zhì)的提高，主要是將雙重for循環(huán)的內(nèi)存循環(huán)拆成了獨立的方法，這便是本文的彩蛋。
源碼
- 雙重for循環(huán)
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;
}
字節(jié)碼
- 雙重for循環(huán)
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繼續(xù)內(nèi)層for循環(huán)
57: iinc 4, 1 //++j
60: goto 23 //繼續(xù)內(nèi)層for循環(huán)
63: iinc 3, 1 //++i
66: goto 10 //繼續(xù)外層for循環(huán)
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 //繼續(xù)內(nèi)層for循環(huán)
35: iconst_0 //false賦值
36: ireturn //return false
分析
比較雙重for循環(huán)和封裝的字節(jié)碼會發(fā)現(xiàn)，核心的字節(jié)碼實現(xiàn)基本是一致。細(xì)節(jié)上有略微區(qū)別（主要表現(xiàn)在注釋的幾行），封裝法的字節(jié)碼實現(xiàn)甚至在代碼行數(shù)上甚至并不具備優(yōu)勢。但是仔細(xì)觀察對比封裝實現(xiàn)的字節(jié)碼方法體的goto指令（32）和雙重for循環(huán)實現(xiàn)的字節(jié)碼中的goto指令（60），再對比字節(jié)碼中循環(huán)體的開始位置，封裝法goto：0～32，雙重for循環(huán)goto：20～60，結(jié)合goto指令實際移動棧針中指針位置的特點，封裝對比雙重for循環(huán)實際在多次循環(huán)的情況下對指針的操作開銷會更低一些。
小結(jié)
封裝除了能對復(fù)雜的業(yè)務(wù)邏輯代碼進(jìn)行拆分解耦，提高代碼可讀性、可維護(hù)性。同時在一些場景下也能提高程序執(zhí)行效率，雙重for循環(huán)就是最經(jīng)典的實例。
LeetCode進(jìn)階226-翻轉(zhuǎn)二叉樹（華為面試題）
彩蛋
對比三種實現(xiàn)代碼執(zhí)行結(jié)果會發(fā)現(xiàn)，三種方法最終leetcode測評的效率都是100%，但是方法一的runtime時間確實1ms，而方法二和方法三的runtime卻是0ms。為什么同樣的算法思想使用不同的數(shù)據(jù)結(jié)構(gòu)，使用Stack比使用LinkedList要慢呢？這便是本篇的彩蛋！
源碼
- 棧實現(xiàn)
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;
}
- 隊列實現(xiàn)
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;
}
分析
本質(zhì)上是由于不同的數(shù)據(jù)結(jié)構(gòu)在底層源碼實現(xiàn)的不同導(dǎo)致。上述兩種方法執(zhí)行主要不同在于分別使用了stack.push、stack.pop（棧實現(xiàn)）和queue.offer、queue.pop方法（隊列實現(xiàn)）。對比下兩者實現(xiàn)源碼：
- 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方法中調(diào)用子類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方法調(diào)用add方法，add方法調(diào)用linkedLast方法，<font color="#FF0000">三個方法均沒發(fā)現(xiàn)synchronized關(guān)鍵字</font>
小結(jié)
synchronized同步會大大較低方法執(zhí)行效率，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;
}
- 執(zhí)行結(jié)果
syn耗時(ms):126
非syn耗時(ms):37
進(jìn)一步證明了synchronized同步會降低執(zhí)行效率，但是為什么synchronized會降低執(zhí)行效率？筆者推薦閱讀《深入理解Java虛擬機(jī)》第13章，由于主題和篇幅關(guān)系本篇不具體展開。
總結(jié)
本篇核心結(jié)論，兩個重點：1、多使用方法封裝，減少嵌套for循環(huán)；2、Stak比LinkedList高效，由于基類方法加了鎖，而鎖會降低執(zhí)行效率，除非必要減少synchronized的使用。最后，如果覺得本篇對你有所幫助不妨關(guān)注一波，來個贊~
掃一掃 關(guān)注我的微信訂閱號
