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++));
    }
    centers.add(new PalindromicCenter(1, j));
}

int maxCenterI = 0;
int max = 0;
boolean canExtend;
do {
    canExtend = false;
    for (int i = 0; i < centers.size(); i++) {
        final PalindromicCenter center = 
        centers.get(i);
        if (center.canExtend 
    && extendCenter(center, i, toCharArray, len)) {
            canExtend = true;
            if (center.maxLen > max) {
                max = center.maxLen;
                maxCenterI = i;
            }
        } else {
            center.canExtend = false;
        }
    }
} while (canExtend);

Process:

First test – LinkedList#get()

When we see the result, it suddenly dawn on us that our wrong selection of LinkedList cause the original time from n^2 to n^3.
So replace it with ArrayList with size will solve it.

Second test – ArrayList#size()

This time, we find size() also cost many time and is useless because the size will never change. So we replace the invocation with a constant variable making a step forward.

Written with StackEdit.