Claude vs ChatGPT: A Coder's Perspective on LLM Performance

-
In the rapidly evolving world of Large Language Models (LLMs), recent releases from OpenAI's ChatGPT have garnered significant attention. However, when it comes to coding tasks, Anthropic's Claude.ai continues to impress me with its speed and quality of output.

Benchmarking with LeetCode

While LeetCode problems aren't the definitive measure of an AI's coding capabilities (they're pre-designed puzzles, after all), they offer an interesting playground for comparison. Let's dive into a recent example:

The Problem

3319. K-th Largest Perfect Subtree Size in Binary Tree
Medium

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the kth largest perfect binary subtree, or -1 if it doesn't exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

 

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 2000].
  • 1 <= Node.val <= 2000
  • 1 <= k <= 1024

My Solution
I tackled this problem using a combination of Post-Order Depth-First Search (PO-DFS) and a Priority Queue. Here are the performance stats:

Runtime: 197 ms
Memory Usage: 103.6 MB

```
Marcelo's Solution:

public class Solution {
    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        PriorityQueue pQueue = new PriorityQueue(false, 2500);
        int height = 0;
        int numberNodes = 0;
        IsPerfectSubtreePostOrder(root, ref height, ref numberNodes, pQueue);

        int retVal = -1;
        while (pQueue.Count > 0 && k > 0)
        {
            double priority = 0;
            retVal = (int)pQueue.Dequeue(out priority);
            k--;
        }

        return k > 0 ? -1 : retVal;
    }

    private bool IsPerfectSubtreePostOrder(TreeNode node,
                                           ref int height,
                                           ref int numberNodes,
                                           PriorityQueue pQueue)
    {
        if (node == null)
        {
            height = 0;
            numberNodes = 0;
            return true;
        }

        int rightHeight = 0;
        int rightNumberNodes = 0;
        bool rightSubtree = IsPerfectSubtreePostOrder(node.right, ref rightHeight, ref rightNumberNodes, pQueue);

        int leftHeight = 0;
        int leftNumberNodes = 0;
        bool leftSubtree = IsPerfectSubtreePostOrder(node.left, ref leftHeight, ref leftNumberNodes, pQueue);

        height = Math.Max(rightHeight, leftHeight) + 1;
        numberNodes = rightNumberNodes + leftNumberNodes + 1;

        bool isPerfectSubtree = false;
        if (rightSubtree && leftSubtree && rightHeight == leftHeight)
        {
            pQueue.Enqueue(numberNodes, numberNodes);
            isPerfectSubtree = true;
        }

        return isPerfectSubtree;
    }
}

public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private double priority;
        public HeapEntry(object item, double priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public double Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private bool ascend;
    private int count;
    private int capacity;
    private HeapEntry[] heap;

    public int Count
    {
        get
        {
            return this.count;
        }
    }

    public PriorityQueue(bool ascend, int cap = -1)
    {
        capacity = 10000000;
        if (cap > 0) capacity = cap;
        heap = new HeapEntry[capacity];
        this.ascend = ascend;
    }

    public object Dequeue(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }
    public object Peak(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public object Peak(/*out double priority*/)
    {
        //priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public void Enqueue(object item, double priority)
    {
        count++;
        bubbleUp(count - 1, new HeapEntry(item, priority));
    }

    private void bubbleUp(int index, HeapEntry he)
    {
        int parent = (index - 1) / 2;
        // note: (index > 0) means there is a parent
        if (this.ascend)
        {
            while ((index > 0) && (heap[parent].Priority > he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
        else
        {
            while ((index > 0) && (heap[parent].Priority < he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
    }

    private void trickleDown(int index, HeapEntry he)
    {
        int child = (index * 2) + 1;
        while (child < count)
        {
            if (this.ascend)
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority > heap[child + 1].Priority))
                {
                    child++;
                }
            }
            else
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority < heap[child + 1].Priority))
                {
                    child++;
                }
            }
            heap[index] = heap[child];
            index = child;
            child = (index * 2) + 1;
        }
        bubbleUp(index, he);
    }
}
```

ChatGPT's Approach
ChatGPT 4 with Code Interpreter took a slightly different route:
  • Highly optimized PO-DFS
  • Used a List instead of a Priority Queue
  • Performance:
Runtime: 170 ms
Memory Usage: 72.2 MB

```
ChatGPT Solution:
public class Solution
{
    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        List<int> perfectSubtreeSizes = new List<int>();
        CalculatePerfectSubtreeSizes(root, perfectSubtreeSizes);

        if (perfectSubtreeSizes.Count < k)
        {
            return -1;
        }

        perfectSubtreeSizes.Sort((a, b) => b.CompareTo(a));
        return perfectSubtreeSizes[k - 1];
    }

    private int CalculatePerfectSubtreeSizes(TreeNode node, List<int> sizes)
    {
        if (node == null)
        {
            return 0;
        }

        int leftSize = CalculatePerfectSubtreeSizes(node.left, sizes);
        int rightSize = CalculatePerfectSubtreeSizes(node.right, sizes);

        if (leftSize == rightSize && (leftSize == 0 || IsPowerOfTwoMinusOne(leftSize + rightSize + 1)))
        {
            int currentSize = leftSize + rightSize + 1;
            sizes.Add(currentSize);
            return currentSize;
        }

        return -1;
    }

    private bool IsPowerOfTwoMinusOne(int n)
    {
        return (n & (n + 1)) == 0;
    }
}
```

Claude's Solution
Claude.ai consistently outperforms ChatGPT in this and other examples I've tested. Its approach:
  • Pruned version of PO-DFS
  • K-min Priority Queue
  • Performance: 
Runtime: 164 ms
Memory Usage: 71.1 MB

```
Claude.ai Solution:

public class Solution
{
    private PriorityQueue<int, int> topK;
    private int k;

    public int KthLargestPerfectSubtree(TreeNode root, int k)
    {
        this.k = k;
        this.topK = new PriorityQueue<int, int>(k, Comparer<int>.Create((a, b) => a - b));
        
        DFS(root);

        return topK.Count == k ? topK.Peek() : -1;
    }

    private int DFS(TreeNode node)
    {
        if (node == null)
            return 0;

        int left = DFS(node.left);
        int right = DFS(node.right);

        if (left == right && IsPowerOfTwoMinusOne(left + right + 1))
        {
            int size = left + right + 1;
            if (topK.Count < k)
            {
                topK.Enqueue(size, size);
            }
            else if (size > topK.Peek())
            {
                topK.Dequeue();
                topK.Enqueue(size, size);
            }
            return size;
        }

        return -1;
    }

    private bool IsPowerOfTwoMinusOne(int n)
    {
        return (n & (n + 1)) == 0;
    }
}
```

The Future of AI and Coding

It's astounding to think that we're only in the first decade of LLMs since the groundbreaking "Attention is All You Need" paper. The rapid progress we've seen raises exciting questions:

  1. How will these models evolve in the coming decades?
  2. What impact will they have on software development practices?
  3. How can we best leverage AI assistants in our coding workflows?

As we continue to explore these questions, one thing is clear: the synergy between human creativity and AI capabilities is reshaping the landscape of software development.

Cheers,
ACC

Comments

Post a Comment

Popular posts from this blog

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    Go's `map` is generally more effi
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more