Lambda expressions are a new syntax in Java 8 that can greatly simplify code and enhance the expressiveness of the language. The syntax of Lambda expressions is not described here, but a feature of Lambda expressions is mainly discussed from a topic.

I’ve been doing one problem a day in LeetCode since a while ago. That was before. Today when doing this problem, encounter a problem, record notes.

Let’s start with the title

The question itself is easy to understand: given several intervals, merge the overlapping intersections and return the combined interval.

It’s also easy to do: sort the intervals in order of “the interval with the smallest starting point is first, and the interval with the same starting point is first.”

Select the first interval A and traverse the remaining interval B in sequence. If the starting point of B is smaller than the end point of A, then A and B can be combined.

Repeat the selection of the first interval until all of the coalescable intervals are merged.

Finally, return the rest of the interval.

It’s supposed to be easy, but when you’re done, you can pass. The code is as follows:

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (o1, o2) -> {
        if (o1[0] != o2[0]) {
            return Integer.compare(o1[0], o2[0]);
        }
        return Integer.compare(o1[1], o2[1]);
    });

    boolean[] vis = new boolean[intervals.length];
    Arrays.fill(vis, true);

    for (int i = 0; i < intervals.length; i++) {
        if(! vis[i]) {continue;
        }

        for (int j = i + 1; j < intervals.length; j++) {
            if (intervals[j][0] <= intervals[i][1]) {
                vis[j] = false;
                if (intervals[i][1] < intervals[j][1]) {
                    intervals[i][1] = intervals[j][1]; }}}}int count = 0;
    for (boolean v : vis) {
        if(v) { count++; }}int[][] ans = new int[count][];
    for (int i = 0, j = 0; i < intervals.length; i++) {
        if(! vis[i]) {continue;
        }
        ans[j++] = intervals[i];
    }

    return ans;
}
Copy the code

Less well understood is that the execution time on LeetCode was 84 ms, beating 28.32% of Java commit records. I thought, this is O(N) complexity (with constant optimization space, of course), what could be more efficient?

The efficiency gap

So I looked at other people’s solutions, and they were basically the same, and the complicated ones were also O(N). Because some details on the processing, there will be a constant level of difference, but should not have such a large gap just right.

At the beginning, it was suspected that there was a large amount of data, and the current data and the previous data needed to be accessed in the traversal process. The time-consuming operation of data retrieval may have occurred at this time. Try to store the data you need to compare in temporary variables. They found no change in time.

In the end, I couldn’t figure it out, so I copied other people’s code and changed it bit by bit, depending on the execution time.

And it turns out that it’s the lambda expression here that causes the efficiency gap.

Java Lambda

Java lambdas 20 times Slower than Anonymous classes after a Google search

You can see some features of Lambda expressions:

  • Lambda expressions correspond to classes that are dynamically generated at run time. Dynamic generation at runtime is not the reason for the slowness here. Dynamically generating a simple class is faster than loading the same byte stream from an external resource.
  • Programs must load the framework used to generate Lambda classes in order to use Lambda expressions. Loading frames is what’s slow here. (The Oracle JDK uses ASM for this implementation.)
  • Regardless of the time it takes to load the Lambda framework, Lambda expressions are a little more efficient than classes.

So the reason for the slow use of Lambda expressions is obvious: LeetCode does not use Lambda expressions before executing the submitted code. When executing our code, we first load the framework that handles Lambda expressions. The time it takes to load the frame is added to the running time of the application.

Further verification

Although the principle is already known, but also to use the code from the actual verification again.

  • As mentioned in the answer, defining more Lambda expressions does not have a noticeable impact on the runtime either.
  • I also did an experiment where I performed the merge interval operation several times during a single run of the program. Using the same data each time, you can clearly see that the first execution takes significantly longer than the subsequent ones. This verifies that the “load Lambda framework” step does exist and that the load process is also a major time consuming operation.