LeetCode中变量名略微改动引起的运行时间差异看似违反直觉

huangapple go评论70阅读模式
英文:

Counterintuitive LeetCode Runtime difference in slight variable name changes

问题

这是问题的翻译部分:

给定一个整数数组 nums,计算这个数组的中心索引。

中心索引是指索引左侧所有数字的总和等于索引右侧所有数字的总和。

如果数组不存在中心索引,返回 -1。

请注意,这三个代码示例是相同的,只是变量名称不同。尽管它们具有相同的空间复杂度,但在运行时性能上存在显著差异。您想要了解为什么会有这么大的差异,尽管逻辑相同。

英文:

I am very new to Leetcode, but I know a bit of programming. I thought I knew about what makes runtime slower or faster, but this Leetcode question is making me question everything. Below are 3 slightly different correct answers to the same easy question with the only difference being the name of the variables. I was under the assumption that shorter names would lead to faster runtimes, but not to this level of difference. All answers are the same space complexity. Can somebody explain why there's such a large difference despite the exact same logic?

This is the question:
Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.


class Solution(object):
    def pivotIndex(self, nums):
left & right respectively...
        leftSum, rightSum = 0, sum(nums)
        # Traverse elements through the loop...
        for idx, ele in enumerate(nums):
            rightSum -= ele
            if leftSum == rightSum:
                return idx      
            leftSum += ele
        return -1      
#Runtime: 103ms and beats 95.77% of all submissions despite being the same with just different variable names
# Space Complexity : O(1)
class Solution(object):
    def pivotIndex(self, nums):
        lS, rS = 0, sum(nums)
        # Traverse elements through the loop...
        for i, e in enumerate(nums):
            rS -= e
            if lS == rS:
                return i      
            lS += e
        return -1

Runtime: 106ms and somehow beats 90.78% of all submissions despite it being identical to the first, just different names

class Solution(object):
    def pivotIndex(self, nums):
        leftS, rightS = 0, sum(nums)
        for index, count in enumerate(nums):
            rightS -= count
            if leftS ==rightS:
                return index
            leftS += count
        return -1

Runtime: 118ms and only beats 52.74% of the other submissions despite identical code, just different names

答案1

得分: 1

我相信LeetCode平台上的运行时间可能会根据特定LeetCode服务器上的负载情况而变化,这取决于我们的代码在那个时刻执行的情况。

我认为重点应该放在解决方案的算法复杂度(时间复杂度和空间复杂度)上,而不是LeetCode报告的具体运行时间。运行时间可能受到我们控制之外的因素的影响,但算法复杂度是代码性能的更可靠衡量标准。在这种情况下,这三个解决方案的时间复杂度(O(n))和空间复杂度(O(1))都相同,这是一个更有意义的度量标准来进行比较。

英文:

I believe the run times on LeetCode platform can change depending on load on specific LeetCode server where our code is getting executed at that point in time.

I think It is important to focus on the algorithmic complexity (the time and space complexity) of your solutions rather than the specific runtimes reported by LeetCode. The runtimes can be affected by factors beyond our control, but the algorithmic complexity is a more reliable measure of the performance of your code. In this case, all three solutions have the same time complexity (O(n)) and space complexity (O(1)), which is a more meaningful metric to compare them.

huangapple
  • 本文由 发表于 2023年4月4日 11:02:06
  • 转载请务必保留本文链接:https://go.coder-hub.com/75925204.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定