Speed tests for different algorithms. Surprising results :D


  • 0
    A

    First I wrote this solution, which uses Deque.

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> q = new ArrayDeque<>();
        if (root == null) return res;
        boolean dir = true;
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = dir ? q.pollFirst() : q.pollLast();
                level.add(node.val);
                TreeNode n1 = dir ? node.left : node.right;
                TreeNode n2 = dir ? node.right : node.left;
                if (n1 != null) 
                    if (dir) q.offerLast(n1);
                    else q.offerFirst(n1);
                if (n2 != null) 
                    if (dir) q.offerLast(n2);
                    else q.offerFirst(n2);
            }
            res.add(level);
            dir = !dir;
        }
        return res;
    }
    

    It's kind of ugly, but it gets the job done. I also thought that having a Deque means that very little data is being copied over, the elements in the deque are retrieved and added via pointers. And so I assumed that this should be pretty fast.

    Then however I saw this solution by GraceLuli, which appears to be faster than the deque approach, even though it has this very inefficient line:

    tmp.add(0, n.val);
    

    which copies all elements in the array every time a new element is inserted at index 0. And yet this solution runs faster than the deque approach.

    I then optimized it by allocating enough space in the arraylist to hold all the elements and avoid copying elements:

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) { 
        List<List<Integer>> res = new ArrayList<>(); 
        if(root == null) return res;
    
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean order = true;
    
        while(!q.isEmpty()) {
            int size = q.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < size; ++i) tmp.add(-1);
            for(int i = 0; i < size; ++i) {
                TreeNode n = q.poll();
                if(order) tmp.set(i,n.val);
                else tmp.set(tmp.size() - i - 1, n.val);
                if(n.left != null) q.add(n.left);
                if(n.right != null) q.add(n.right);
            }
            res.add(tmp);
            order = !order;
        }
        return res;
    }
    

    This, of course, appears to be the fastest solution of all three. Here are the runtimes in nanoseconds for comparison:

    1. Deque approach --------------------------------- 301341 ns
    2. ArrayList-insertion approach ------------------- 283056 ns
    3. Optimized ArrayList-insertion approach --------- 229197 ns
    #3 is the winner, it performs faster than 61% of submissions.
    # I am still very curious who and how managed to get it run in 1 ms. 
    

    Even if the 1 ms solution is a custom-built implementation of Deque or Queue which only uses arrays of exact size as needed, the TreeNodes are still stored by reference, so I have no idea where further optimization can come from.

    Given all this, I am still amazed that Java seems so slow sometimes with object allocation compared to array allocation. Note: I ran these tests in LeetCode.


  • 0

    About the 1ms submissions: I got the following accepted in 1ms in the third submission attempt (the first two times it got 2ms). Maybe you can get yours accepted in 1ms as well if you submit a few more times.

    public class Solution {
        private List<List<Integer>> zigzag = new ArrayList();    
        private void dfs(TreeNode node, int depth) {
            if (node != null) {
                if (depth == zigzag.size())
                    zigzag.add(new ArrayList());
                zigzag.get(depth).add(node.val);
                dfs(node.left, depth + 1);
                dfs(node.right, depth + 1);
            }
        }
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            dfs(root, 0);
            for (int i=1; i<zigzag.size(); i+=2)
                Collections.reverse(zigzag.get(i));
            return zigzag;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.