On teh way

Learn Profiling 2 -- Java Origin This time we profiling a java program. When I implement a problem to solve the longest-palindromic-substring problem which described in leetcode . I thought the running time should be O(n^2) and should pass the test. But result is time limit exceed. So I decide to profile my program to find out the problem. Tool We use a tool called JProfiler(which is very powerful but need to pay for it). Source Full source is at gist . Part of code about code tuning is following(before tuning): int len = string . length ( ) ; final LinkedList < PalindromicCenter > centers = new LinkedList < > ( len * 2 - 1 ) ; final char [ ] toCharArray = string . toCharArray ( ) ; { int j = 0 ; for ( int in = 0 ; in < toCharArray . length - 1 ; in ++ ) { centers . add ( new PalindromicCenter ( 1 , j ++ ) ) ; centers . add ( new PalindromicCenter ( 0 , j ++ ) ) ; ...

Learn Profiling and Performace Tuning Programming pearls Recently, I read some chapter of programming pearls about the performance, which is can be applied to my homework about prime generation. Here is some performance optimization levels: System Structure Algorithm and Data Structures Code Tuning System Software Hardware Algorithm For algorithm design, it also provide some tips: Save state to avoid recomputation Preprocess infromation into data structure Divide and conqure Scanning algorithms Code tuning Rules are repeated here( I still not understand some rules, I will update them to add my understanding). One thing to mention is not all rule can speed up your program( it may even slow down it), it just some aspect you can think of. Space For Time Rules Data Structure Augmentation: e.g. add left children count in binary search tree to speed up i-th element query. Store Pre-computed Results Caching Lazy Evaluation Time For Space Rules...

Google RPC In this blog, we are going to dive into the functionality what google’s RPC – a complex distributed RPC framework – can do, then we may get RPC is not so easy in large scale. We will focus on two main aspects of its RPC framework: load balance & overload handle. Load Balance In the blog of The Life of a Request to Google (2) , we have introduced that how Google’s RPC framework do the load balance in detail. Here, we just skim the backbone: In order to have better performance, RPC framework keep long-lived TCP connection to service producer; If connection silent long enough, fall back to UDP health check to save cost; Considering the cost to keep connections to all producer (may be up to hundreds), use determined algorithm to decide a subset of service producers to use; Use Weighted Round Robin to send request to its subset of producers, and update weight dynamically according to the response each producer returned. “In each response (inclu...

The Life of a Request to Google (2) In the last blog post , we have introduced what a request may experiences when traveling from user’s browser to the data center. Now, the request finally reach the Application Frontend and front end is trying to communicate with back end. Load Balance Third Trial: RPC In order to communicate with back end, front end can use REST way or RPC way. REST way is based on HTTP protocol; RPC way is based on TCP & UDP. Considering the efficiency of communication, google go the RPC way. Along with RPC, they also adopted protocol buffer, which serialize data in binary which is faster and smaller than textual data which is used by HTTP protocol. In order to avoid the slow 3 way handshake when establishing connection and the slow start features, they make long-lived connection to backend servers. When a front end is quiet long enough, the TCP connection is closed to save cost and periodic UDP datagram is sent to do health check. B...

Jail AtomicLong? The atomic class in Java Kingdom provide very handy and powerful functionalities in cases where our program’s state is simple enough to delegate to a atomic variable. If we look at the packages – java.util.concurrent.atomic , there exists five general kinds of atomic class: Atomic | | | | \__ Primitives : Long , Integer , Boolean , Reference | | | \ -- -- Arrasy element : LongArray , IntegerArray , ReferenceArray | | \______ Refelction related : LongFieldUpdater , IntegerFieldUpdater , ReferenceFieldUpdater | \ -- -- -- -- Reference with state : MarkableReference , StampedReference \__________ Primitives : Striped64 , LongAdder , DoubleAdder , LongAccumulator , DoubleAccumulator [ * ] [ * ] : Other four kinds of classes all start with `Atomic` , except this one . Each kinds of class has different usages domains as above list concludes, except the first and last type. They seems have some duplication: that is this...

Programming Pearls: How to Random? Notes for Programming Pearls: second edition , chapter 12, trying to remember the process to solve a problem. They want to automating the task of drawing a random sample from a printed list of precincts. The input consists of a list of precinct names and an integer m. The output is a list of m of the precincts choosen at random. There are usually a few hundred precinct names( each a string of at most a dozen characters), and m is typically between 20 and 40. Problem definition In order to make problem easier to understand and solve, we can make description more abstract. The input consists of two integers m and n, with m < n. The output is a sorted list of m random integers in the range [0, n-1} in which no integer occurs more than once. For probability buffs, we desire a sorted selection without replacement in which each selection occurs with equal probability. One solution Author give us an algorithm from Knuth ...

Substring With Concatenation of Words Problem Statement The following is the description of substring with concatenation of words: You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. For example, given: s: "barfoothefoobarman" words: [“foo”, “bar”] You should return the indices: [0,9]. Thoughts Given the problem, we can easily come up with the following solution: Compose all possible string combinations from the words array and compare them with target string: the time and memory complexity can be O ( n ! ) O(n!) O ( n ! ) ; Or, Find index of every single word and try to connect them; Or, Combine words using prefix tree and compare with target; In both cases, we need to compare string effectively, so we can use KMP algorithm. How to KMP KMP is a somewhat c...

KMP in Interview After some questions about basic knowledge of Java, interviewer give Amy the last question: how to find the ‘Longest common substring between two string’ efficiently? Amy thinks for a while and comes up with the DP solution which depends on the core equation of // longest common suffix dp [ i ] [ j ] = m [ i ] == n [ j ] ? dp [ i - 1 ] [ j - 1 ] + 1 : 0 max ( dp [ 1 . . x ] [ 1 . . y ] ) Interviewer check the solution and said, “It’s a good solution. But it’s time complexity is O(n^2) and space complexity is also O(n^2) . Can you come up with better algorithm?” Amy ponder the question again and suddenly the KMP algorithm dawn on her. What is KMP "The KMP algorithm is a very efficient string comparison algorithm which save the time by extra pre-process. When we compare string in common way, we do like this: when a mismatch happens, we reset start point to old_position + 1 : ...xxx...xxy xxy.. ⇑ mismatch ...xxx....