2

I was working on the problem Permutations on LeetCode. I tried two identical solutions except that the first one uses Java stream and the other does not. Both got accepted, but the first one took 38ms and the second one's runtime is negligible (0 ms). I wonder what are the causes of such a dramatic difference. Following is my code

solution 1

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    List<List<Integer>> ans = new LinkedList<>();

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private void permutation(int[] nums, int pos) {
        if (pos == nums.length - 1) {
//            List<Integer> temp = new LinkedList<>();
//            for (int n : nums)
//                temp.add(n);
//            ans.add(temp);
            ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
        }
        for (int i = pos; i < nums.length; i++) {
            swap(nums, i, pos);
            permutation(nums, pos + 1);
            swap(nums, i, pos);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        permutation(nums, 0);
        return ans;
    }
}

solution 2

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    List<List<Integer>> ans = new LinkedList<>();

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private void permutation(int[] nums, int pos) {
        if (pos == nums.length - 1) {
            List<Integer> temp = new LinkedList<>();
            for (int n : nums)
                temp.add(n);
            ans.add(temp);
//            ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
        }
        for (int i = pos; i < nums.length; i++) {
            swap(nums, i, pos);
            permutation(nums, pos + 1);
            swap(nums, i, pos);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        permutation(nums, 0);
        return ans;
    }
}

Thank you for your time.

Stefan Zobel
  • 3,182
  • 7
  • 28
  • 38
gyuaisdfaasf
  • 439
  • 4
  • 12
  • 4
    Well, there are lots of classes to load, which just increases startup time significantly... – Louis Wasserman Sep 11 '19 at 22:24
  • 3
    Just accept that streams have an overhead. If you really want to know what it is, look at the source code. Covering the minute details of how streams is implemented and what the overhead is, is too broad to cover here, and is kind of off-topic for this site. – Andreas Sep 11 '19 at 22:51
  • 1
    Note that the differences you are seeing will be due *in part* to various JVM startup / warmup effects. A well-designed benchmark would eliminate these. I suggest you do some research on "Java benchmark frameworks" and use something like "jmh" to implement benchmarks like this. However, your observation that streams are slower is correct. – Stephen C Sep 11 '19 at 23:53
  • 1
    For information about how streams work under the covers: ["Streams under the hood: understand java.util.stream internals"](https://developer.ibm.com/articles/j-java-streams-3-brian-goetz/) by Brian Goetz. – Stephen C Sep 11 '19 at 23:58
  • Like with [this question](https://stackoverflow.com/q/34585444/2711488), Leetcode doesn’t measure the initialization of anything it uses itself (or which the JVM did already use) before entering your code. But it doesn’t use lambda expressions nor the Stream API. By the way, your code would be even faster when not using `LinkedList`. That’s especially true as you know the size of the lists at creation time so you could create `ArrayList`s with the right initial capacity. – Holger Sep 12 '19 at 12:47

0 Answers0