Python 中的性能改进基础知识

Question

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

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

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

问题如下：

问题陈述

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

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

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

输入格式

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

Link 问题：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))在这个迭代器中找到最小的不公平。

Answer 2

在 Kolmar 和 Steven 的帮助下，我写了以下文章：

n, k = int(input()), int(input())
num = sorted([ int(input()) for i in range(0,n) ])
min_unfairness = min( max_value - min_value for min_value, max_value in    zip(num, num[k-1:]) )
print(min_unfairness)

将其作为答案张贴在这里，以便如果有人想快速查看答案，他们可以看到这个:)

Python 中的性能改进基础知识

Performance Improvement Basics in Python

python

algorithm

performance

big-o