python list.sort() 与 list.sort(key=itemgetter(0))

Question

我是一个 python 菜鸟，但我正在使用 python 来解决 leetcode 上的问题。我在 leetcode 上解决了一个（合并重叠间隔）。我有以下代码：

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) < 2: return intervals
        intervals.sort(key=itemgetter(0))
        merged = [intervals[0]]
        for interval in intervals[1:]:
            if merged[-1][1] >= interval[0]: merged[-1][1] = max(merged[-1][1],interval[1])
            else: merged.append(interval)
        return merged

我注意到如果我替换 intervals.sort(key=itemgetter(0)) 使用 intervals.sort() 我的性能明显变差（分别为 ~80ms 和 ~110ms）

sort() 在技术上与 sort(key=itemgetter(0)) 不是一样的吗？他们不应该有相同的运行时间吗？除非，leetcode 只是与重新编码确切的运行时不一致吗？

Answer 1

intervals.sort(key=itemgetter(0)) 不同于 intervals.sort()。 intervals.sort(key=itemgetter(0)) 只比较两个区间的第一项，但 intervals.sort() 当第一项相同时比较第二项。所以 intervals.sort(key=itemgetter(0)) 可能有更多的间隔看起来与 sort 相同，或者在比较间隔时只做较少的比较。这可能是第一个运行更快的原因之一。

另一个可能的原因是优化。另外Python是解释型语言，解释器在运行ning的时候可能会生成二进制代码，做一些优化。哪一个会获得更好的性能取决于解释器。

但根据经验，在大多数在线判断中，30ms左右的差异只是测量误差。再试一次你可能会得到不同的结果。

Answer 2

您的主要问题已经得到解答。

LeetCode 的性能测量根本不准确。你可以在解决问题时忽略他们的基准数据。

class Solution:
    def merge(self, intervals):
        merged = []
        for interval in sorted(intervals, key=lambda x: x[0]):
            if merged and interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)
        return merged

class Solution:
    def merge(self, intervals):
        merged = []
        for interval in sorted(intervals):
            if merged and interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)
        return merged

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

python list.sort() 与 list.sort(key=itemgetter(0))

python list.sort() vs. list.sort(key=itemgetter(0))

python

sorting

intervals

参考资料