我可以在哪里改进我的代码以缩短其执行时间？

Question

HackerRank 的请求：

\n

\n

如果客户在特定日期的支出金额大于或等于 2\xc3\x97 客户在过去几天的平均支出，他们会向客户发送有关潜在欺诈的通知。银行不会向客户发送任何通知，直到他们至少拥有前几天的交易数据的跟踪数据。

\n

给定跟踪天数d和客户在n天期间的每日总支出，确定客户在所有n天内收到通知的次数。

\n

\n

我的代码可以解决问题，但是对于大型测试用例来说有时间限制。我的代码无法通过时间限制要求。我的代码实际上很短：

\n

from statistics import median\n\nfirst_multiple_input = input().rstrip().split()\nn = int(first_multiple_input[0])\nd = int(first_multiple_input[1])\nexpenditure = list(map(int, input().rstrip().split()))\ncount=0\nfor i in range(len(expenditure)-d):\n    if expenditure[d+i] >= 2*median(expenditure[i:d+i]) :\n        count+=1\nprint( count)\n

\n

请指出造成延误的原因以及如何改善。

\n

帮助理解代码的小测试用例：

\n

9 5                 expenditure[] size n =9, d = 5\n2 3 4 2 3 6 8 4 5   expenditure = [2, 3, 4, 2, 3, 6, 8, 4, 5]\n

\n

Answer 1

分析/想法

你median(expenditure[i:d+i])是罪魁祸首，因为每次对大小为 d 的整个未排序切片进行排序都需要 O(d log d) 时间。您可以通过保留尾随元素的当前窗口（例如在SortedList中）将其减少到 O(log d) 。您可以从中间的一两个元素中获取中位数，并且要更新，只需添加一个新元素并删除最旧的元素即可。

执行

from sortedcontainers import SortedList

n = 9
d = 5
expenditure = [2, 3, 4, 2, 3, 6, 8, 4, 5]

count = 0
trailing = SortedList(expenditure[:d])
half = d // 2
for i in range(d, n):
    median = (trailing[half] + trailing[~half]) / 2
    if expenditure[i] >= 2 * median:
        count += 1
    trailing.add(expenditure[i])
    trailing.remove(expenditure[i - d])
print(count)

我们可以省略 the/ 2和 the 2 *，但是“中位数”将是错误的名称，并且命名事物很困难。我们可以这样做if expenditure[i] >= trailing[half] + trailing[~half]，但我发现不太清楚。

输出

如果你添加

    print(f'{trailing=} {median=} {expenditure[i]=}')

在该median = ...行之后，您可以看到发生了什么：

trailing=SortedList([2, 2, 3, 3, 4]) median=3.0 expenditure[i]=6
trailing=SortedList([2, 3, 3, 4, 6]) median=3.0 expenditure[i]=8
trailing=SortedList([2, 3, 4, 6, 8]) median=4.0 expenditure[i]=4
trailing=SortedList([2, 3, 4, 6, 8]) median=4.0 expenditure[i]=5
2

替代实施

使用zip而不是索引：

count = 0
trailing = SortedList(expenditure[:d])
half = d // 2
for today, oldest in zip(expenditure[d:], expenditure):
    median = (trailing[half] + trailing[~half]) / 2
    if today >= 2 * median:
        count += 1
    trailing.add(today)
    trailing.remove(oldest)
print(count)

替代数据结构：排序的常规列表

我在 HackerRank 上发现了这个问题，它没有sortedcontainers. 但以下内容在那里被接受。

我们可以使用常规的 Python list，但可以借助Python 标准库对其sorted进行排序：bisect

from bisect import bisect_left, insort

count = 0
trailing = sorted(expenditure[:d])
half = d // 2
for today, oldest in zip(expenditure[d:], expenditure):
    median = (trailing[half] + trailing[~half]) / 2
    if today >= 2 * median:
        count += 1
    insort(trailing, today)
    del trailing[bisect_left(trailing, oldest)]
print(count)

访问中间元素需要 O(1) 时间，查找插入/删除索引需要 O(log d) 时间，实际插入/删除需要 O(d) 时间（因为它需要将所有元素移动）索引右侧）。但 O(d) 转换速度非常快且水平较低。

另外两个：排序字节数组和计数排序

该问题最初并未提及 HackerRank。现在我看到这些值仅限于 0 到 200 之间的整数，我们还可以使用 a bytearray：

trailing = bytearray(sorted(expenditure[:d]))

正如我刚刚在讨论中指出的那样，对于这个允许值的范围，我们还可以使用计数排序的形式。我认为芬威克树会让这个速度特别快，我稍后可能会尝试。

基准

在评论中您提到 n=200000 和 d=10122 作为一个大案例。所以我用这个数据进行了测试：

n = 200000
d = 10122
expenditure = random.choices(range(201), k=n)

我的解决方案的基准：

                       at replit.com   on my weak laptop
SortedList + indexing   ~1.8 seconds    ~6.4 seconds
SortedList + zipping    ~1.8 seconds    ~6.4 seconds
sorted regular list     ~0.6 seconds    ~8.8 seconds
sorted bytearray        ~0.3 seconds    ~1.7 seconds

不知道为什么常规列表解决方案在我的笔记本电脑上相对较慢。我怀疑它超出了我的 CPU 的 1 级缓存。