The profile
As for “Easter eggs,” the bloggers try to bury Easter eggs in every blog post in the series on data structures and algorithms, if possible. The meaning of Easter eggs, as explained at the beginning of my blog, is actually a few tips in the implementation process of algorithms, and these tips are often able to improve the efficiency of execution. There are special explanations for all Easter eggs. A journey of a thousand miles begins with a single step
LeetCode advanced 944- Algorithm optimization
eggs
Advanced version of the ordinary version of the efficiency of qualitative improvement, mainly will be doubleforThe memory loop of the loop is broken down into separate methods, which is the Easter egg of this article.Copy the codeThe source code
- Double for loop
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;
}
Copy the code- encapsulation
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;
}
Copy the codeThe bytecode
- Double for loop
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 continue inner for loop 57: IInc 4, 1 //++j 60: goto 23 // Continue inner for loop 63: iInc 3, 1 //++ I 66: Goto 10 // Continue the outer for loop 69: ILOAD_2 70: iRETURNCopy the code- encapsulation
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 // continue the inner for loop 35: iconst_0 //false: 36: ireturn //return falseCopy the codeAnalysis of the
Comparing the double for loop with the encapsulated bytecode shows that the core bytecode implementation is basically the same. The details are slightly different (mainly in the lines of comments), and the encapsulated bytecode implementation doesn’t even have an advantage in terms of lines of code. However, by carefully observing and comparing the goTO instruction (32) of the encapsulated bytecode method body and the Goto instruction (60) of the bytecode implemented by the double for loop, and then comparing the beginning position of the loop body in the bytecode, the encapsulation method goto: 0 ~ 32, the double for loop GOTO: 20 ~ 60, combined with the characteristics of goTO instruction to actually move the pointer position in the stack pin, encapsulation and double for loop will actually have lower operation overhead for the pointer in the case of multiple loops.
summary
Encapsulation can decouple complex business logic codes and improve code readability and maintainability. At the same time, it can also improve the efficiency of program execution in some scenarios. The double for loop is the most classic example.
LeetCode Advanced 226- Flipping binary Trees (Huawei interview questions)
eggs
Comparing the execution results of the three implementation codes, it can be found that the efficiency of leetcode evaluation of the three methods is 100%, but the runtime time of method 1 is 1ms, while the runtime time of method 2 and method 3 is 0ms. Why is it slower to use Stack than LinkedList for the same algorithmic idea with a different data structure? That's the Easter egg!Copy the codeThe source code
- The stack to achieve
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;
}
Copy the code- Queue implementation
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;
}
Copy the codeAnalysis of the
Essentially is due to different data structures in the underlying source code implementation of the different results. The main difference between the two implementations is the use of stack.push and stack.pop (stack implementation) and queue.offer and queue.pop (queue implementation), respectively. Compare the two implementation source code:
- Stack push method source code analysis
/** * 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
* @sinceJDK1.0 * /
public
class Stack<E> extends Vector<E> {
/** * Creates an empty Stack. */
public Stack(a) {}/**
* 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);
returnitem; }... }Copy the codeThe Stack class extends from vector, and addElement in vector is called in push. AddElement in vector is called in push.
/**
* 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;
}
Copy the codeSource code addElement modified by synchronized, the whole method body to do a synchronization lock.
- LinkedList offer method source analysis
/**
* 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})Public Boolean offer(E E) {returnadd(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++;
}
Copy the codeIn the LinkedList class, offer method calls Add method, add method calls linkedLast method, and synchronized keyword is not found in the three methods
summary
Synchronized greatly reduces method execution efficiency, 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("The syn time-consuming (ms)." + Long.toString((System.nanoTime() - start1) / 1000));
long start2 = System.nanoTime();
for (int i = 0; i < 1000; i++) {
syn.test1();
}
System.out.println("Non-syn time (ms): + Long.toString((System.nanoTime() - start2) / 1000));
}
public synchronized int test1() {
return 1;
}
public int test2() {
return 1;
}
Copy the code- The execution result
Syn time (ms):126 Non-SYN time (ms):37Copy the codeThis further proves that synchronized can reduce execution efficiency, but why does synchronized reduce execution efficiency? I recommend reading Chapter 13 of Understanding the Java Virtual Machine, which is not detailed due to the subject matter and length.
conclusion
The core conclusions of this paper are as follows: 1. Use more methods to encapsulate and reduce nested for loops; 2. Stak is more efficient than LinkedList because the base class methods are locked, and locking reduces performance unless it is necessary to reduce the use of synchronized. Finally, if you think this article has helped you, please follow the wave and give a thumbs-up
