使 Python 代码更快地处理大型数据集

Question

我正在 HackerEarth 上解决一个问题（全文可以在这里找到）：

Bob 有一个歌曲播放列表，每首歌曲都有一个与之关联的歌手（用整数表示）

Bob最喜欢的歌手是播放列表中歌曲最多的歌手

数一下Bob最喜欢的歌手有多少个

例如，以

[1, 1, 2, 2, 3]

作为输入，输出应为

2

，因为

1

和

2

都是最常见的。

问题是我的代码通过了除具有大数据集的测试用例之外的所有测试用例，这违反了时间限制。当然，我需要进一步优化我的代码。 这是我的代码：

singer_tokens = input()
singer_tokens = singer_tokens.split(' ')

fav_singers = []
result = []

for i in singer_tokens[:]:
    if i not in result:
        result.append(i)

for i in result:
    fav_singers.append(singer_tokens.count(i))


max_elem = max(fav_singers)

print(fav_singers.count(max_elem))

Answer 1

瓶颈与改进

您的代码有两个主要的低效步骤。

您在此处搜索每个新项目的唯一值列表。 一旦结果开始很大，这种搜索就会变得低效

for i in singer_tokens[:]:
    if i not in result:   # this is inefficient
        result.append(i)

这一步是使用 python 中的

set

高效完成的：

result = set(singer_tokens)

然后您在完整输入中搜索每个唯一值，这意味着您必须再次阅读每个唯一值的完整列表。

for i in result:
    fav_singers.append(singer_tokens.count(i))

您可以使用字典来跟踪值。这样您就不必提前知道唯一值的列表：

counts = {}
for s in singer_tokens:
    counts[s] = counts.get(s, 0) + 1

或者，更好的是，使用

collections.Counter

:

from collections import Counter

counts = Counter(singer_tokens)

然后获取最大值的数量：

counts = list(Counter(singer_tokens).values())

print(counts.count(max(counts)))

含电池

现在，有一个更好的方法，因为 python 交付时包含电池，使用

statistics.multimode

:

from statistics import multimode

print(len(multimode(singer_tokens)))

输出：

2