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 <= 20001 <= 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:
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:
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:
- How will these models evolve in the coming decades?
- What impact will they have on software development practices?
- 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