python - Python 中的性能改进基础知识

Question

所以这是我在 HackerRank 上解决的算法问题。它通过了除一个测试用例之外的所有测试用例，因为它超时。

我尝试进行了一些改进，但它仍然会超时。我想了解您如何查看自己的代码并找到它运行缓慢的地方。

请注意，我并不是在寻找解决问题的替代逻辑。这是我想到的解决方案，我想尝试并加快它的速度。

题目如下:

问题陈述

给定一个包含 N 个整数的列表，您的任务是从列表中选择 K 个整数，以使其不公平性最小化。

如果(x1,x2,x3,…,xk)是从列表N中选出的K个数，则不公平定义为

max(x1,x2,…,xk)−min(x1,x2,…,xk) 其中max表示K的元素中最大的整数，min表示K的元素中的最小整数。

输入格式

第一行包含一个整数N。 第二行包含一个整数 K。 接下来是 N 行。每行包含一个属于列表 N 的整数。

问题链接:https://www.hackerrank.com/challenges/angry-children/copy-from/11910253

第一次尝试:

n, k = int(input()), int(input())
num = sorted([ int(input()) for i in range(0,n) ])
lower, min_unfairness, upper = 0, 0, k

while upper <= len(num):
    current    = num[lower:upper]
    unfairness = current[-1] - current[0]
    if lower == 0: 
        min_unfairness = unfairness
    else: 
        if unfairness < min_unfairness:
            min_unfairness = unfairness 

    if min_unfairness == 0:
        break

    lower += 1
    upper += 1

print (min_unfairness)

第二次尝试:通过从循环中删除对 lower == 0 的检查进一步改进，因为这只发生在第一次迭代中。

n, k = int(input()), int(input())
num = sorted([ int(input()) for i in range(0,n) ])
lower, min_unfairness, upper = 0, 0, k

#Finding the unfairness of the 1st set and assigning it as min
current    = num[lower:upper]
unfairness = current[-1] - current[0]
min_unfairness = unfairness
lower += 1
upper += 1

while upper <= len(num) and min_unfairness != 0:

    #Finding unfairness of current set
    current    = num[lower:upper]
    unfairness = current[-1] - current[0]

    #Set it as min if it is lower than current minimum
    if unfairness < min_unfairness:
        min_unfairness = unfairness 

    lower += 1
    upper += 1

print (min_unfairness)

我不确定在尝试分析这个问题时应该采用什么方法。欢迎提出任何建议。

Answer 1

您做的最慢的事情是复制列表的一部分:current = num[lower:upper]。这使得这一步的复杂度从 O(n) 上升到 O(n•k)。

你真正应该做的只是获取元素，这些元素直接通过它们的索引定义了这个子列表的不公平性:

min_unfairness = min(num[i+k-1] - num[i] for i in range(n-k+1))

说明:当某个选择的第一个元素的索引为i时，最大元素的索引为i+k-1，所以这个选择的不公平等于num[i+k-1] - num[i]。代码 (num[i+k-1] - num[i] for i in range(n-k+1)) 给出了相关选择的不公平性的迭代器。所以 min(num[i+k-1] - num[i] for i in range(n-k+1)) 找到这个迭代器中最小的不公平性。