LeetCode#494 target sum (dart is slower than python)

Question

I'm trying to solve a LeetCode problem target-sum, in two languages: Python & Dart. The difference of time taken is shocking for me"

• Python took ~70ms while Dart took ~900ms !! Why does Dart take so long? screenshot
• What should I do to improve Dart performance?

Solution in two different languages are as follows (same approach):

Python:

class Solution:
 def findTargetSumWays(self, nums: List[int], target: int) -> int:
 dp = {}
 
 def calculate(i, total):
 if(i == len(nums)):
 return 1 if (total == target) else 0
 
 if((i, total) in dp):
 return dp[(i, total)]
 
 dp[(i, total)] = calculate(i+1, total + nums[i]) + calculate(i+1, total - nums[i])
 
 return dp[(i, total)]
 
 return calculate(0, 0)

Dart

class Solution {
 int findTargetSumWays(List<int> nums, int target) {
 Map<MapEntry<int, int>, int> dp = {};
 int calculate(int i, int sum) {
 if (i == nums.length) {
 return sum == target ? 1 : 0;
 }
 final pair = MapEntry(i, sum);
 return dp[pair] ??
 (dp[pair] = calculate(i + 1, sum + nums[i]) +
 calculate(i + 1, sum - nums[i]));
 }
 return calculate(0, 0);
 }
}

Is Dart map causing this delay? If so what operations should I use?

• Toby Speight: Welcome to Code Review! Could you please edit to add a short summary of the problem statement? You can keep the link as a reference, but your question does need to be complete even if the linked material isn't accessible. Thanks.

Answer 1

Use hashable types as hashtable keys

An important requirement of hashtables is that they keys must be hashable:

• has a .hashCode implementation that returns the same value for two objects that are equal
• has a .equals implementation that returns true for two objects that are equal

Looking at the documentation of MapEntry, it looks like it inherits the hashCode and equals implementations from Object, which means it's not hashable.

The problem is that these objects are not equal:

MapEntry x = MapEntry(a, b);
MapEntry y = MapEntry(a, b);

This breaks the caching mechanism of the code, everything is recomputed.

You could implement a Pair with suitable hashCode and equals:

class Pair {
 final int first, second;
 Pair(this.first, this.second);
 bool operator==(Object other) =>
 other is Pair && first == other.first && second == other.second;
 int get hashCode => Object.hash(first, second);
}

Alternatively, you could compute a key to use with the cache, given the range of inputs in the problem description:

class Solution {
 int findTargetSumWays(List<int> nums, int target) {
 Map<int, int> dp = {};
 int calculate(int i, int sum) {
 if (i == nums.length) {
 return sum == target ? 1 : 0;
 }
 final k = key(i, sum);
 
 return dp[k] ??
 (dp[k] = calculate(i + 1, sum + nums[i]) +
 calculate(i + 1, sum - nums[i]));
 }
 return calculate(0, 0);
 }
 
 int key(int index, int sum) {
 return sum * 1001 + index;
 } 
}

Using this key function saves the overhead of object creation.

Programming challenge sites are not benchmarking tools

These sites are not proper benchmarking tools, and there are far too many unknowns an outsider simply cannot know:

• how efficiently are the program executors implemented for each language
• do the programs run on the same hardware
• do the programs run on the same network (same latency)

To name just a few. Don't read too much meaning into the timing results on these sites. They are just good enough to decide if your solution has the target time and space complexity.

Improve the Python code

There are many redundant parentheses:

if(i == len(nums)):
 return 1 if (total == target) else 0
if((i, total) in dp):
 return dp[(i, total)]

These could be:

if i == len(nums):
 return 1 if (total == target) else 0
if (i, total) in dp:
 return dp[i, total]

You can also take advantage that False is 0 in integer context, and True is 1, simplifying the first conditional:

if i == len(nums):
 return total == target

Lastly, instead of using dict as the cache, you can benefit from @cache in functools (implicitly imported on leetcode).

Putting it together:

class Solution:
 def findTargetSumWays(self, nums: List[int], target: int) -> int:
 @cache
 def calculate(i, total):
 if i == len(nums):
 return total == target
 
 return calculate(i+1, total + nums[i]) + calculate(i+1, total - nums[i])
 
 return calculate(0, 0)

• Abhishek Patil: Thanks, this works ! Can you please explain why dart is taking longer than the python? Where exactly dart is lagging? Is it map?
• janos: Since I don't know how leetcode executes Python and Dart code, I cannot tell if one takes longer than the other and if so then why. I don't like to speculate when I cannot have the data. This is what I meant by the section to not treat programming challenge websites as benchmarking tools.