python - 计算列表中只出现一次的元素: how do I optimise my performance? 非常慢

Question

我有一个包含用户名的大列表(大约 60,000 个字符串)。每个用户名代表一次提交。有些用户只提交了一次，即他们是“一次性用户”，因此他们的用户名在此列表中仅出现一次。其他人进行了多次提交(回访用户)，因此他们的用户名可以在此列表中多次出现。我想统计一下这些一次性用户有多少，并据此获得一些统计数据。以下是我当前正在获取的变量:

import time

start_time = time.time()

users = ["UserA", "UserB", "UserC", "UserA", "UserA", "UserA", "UserB", "UserB", "UserD"] # ...just a sample, this goes up to ~60,000 elements
print(f"1: got users list. Time elapsed: {time.time() - start_time}")

one_time_users = [user for user in users if users.count(user) == 1]
print(f"2: got one-time users list. Time elapsed: {time.time() - start_time}")

returning_users = [user for user in users if users.count(user) != 1]
print(f"3: got returning users list. Time elapsed: {time.time() - start_time}")

frequencies = [users.count(user) for user in set(users)]
print(f"4: calculated frequencies list. Time elapsed: {time.time() - start_time}")

sorted_frequencies = sorted(frequencies, reverse=True) # Descending order, largest first
print(f"5: got sorted frequencies list. Time elapsed: {time.time() - start_time}")

top_ten_frequencies_sum = sum(sorted_frequencies[:10])
print(f"6: got top 10 frequencies sum. Time elapsed: {time.time() - start_time}")

top_ten_frequencies_percentage = round(((top_ten_frequencies_sum / len(users)) * 100), 2)
print(f"7: got top 10 frequencies percentage. Time elapsed: {time.time() - start_time}")

average_submissions_per_user = round(len(users) / len(set(users)), 2)
print(f"8: got average submissions per user. Time elapsed: {time.time() - start_time}")

此操作非常慢。这是我的输出:

1: got users list. Time elapsed: 0.41695237159729004
2: got one-time users list. Time elapsed: 48.26731848716736
3: got returning users list. Time elapsed: 101.88410639762878
4: calculated frequencies list. Time elapsed: 104.39784860610962
5: got sorted frequencies list. Time elapsed: 104.39850783348083
6: got top 10 frequencies sum. Time elapsed: 104.39853930473328
7: got top 10 frequencies percentage. Time elapsed: 104.39856457710266
8: got average submissions per user. Time elapsed: 104.4005241394043

正如您所看到的，列表推导花费了最多的时间。有人可以向我解释一下吗:

1. 为什么它的时间复杂度这么慢。
2. 是否collections.Counter()将是一个更好的选择以及如何最好地在这里应用它。

谢谢!

Answer 1

您可以通过使用Counter来改进，在 2. 中，对于每个元素，您都会迭代整个列表，并且如果某个用户出现多次，则您将为同一用户执行多次此操作。
请注意，当您使用users.count(user)时，您会迭代所有用户列表以计算该用户出现的次数。这意味着相对于列表长度的二次复杂度。
使用计数器，您可以以线性复杂度解决它。
另外，在 4. 中，您将再次迭代和计数，而您可以从整个用户中删除刚刚计算的用户。
示例。

>>> one_time_users = {user for user,cnt in Counter(users).items() if cnt == 1}
{'UserC', 'UserD'}
>>> returning_users = set(users) - one_time_users
>>> returning_users
{'UserB', 'UserA'}

或更直接

one_time_users, returning_users  = [], []
for user,cnt in Counter(users).items():
   if cnt==1:
      one_time_users.append(user)
   else:
      returning_users.append(user)

这里是 l.count(el) 与 Counter(l) 的比较。

>>> l = random.choices(range(500), k=60000)
>>> timeit.timeit('[el for el in l if l.count(el) == 1]',setup='from __main__ import l',number=1)
71.70409394335002
>>> timeit.timeit('[el for el,cnt in Counter(l).items() if cnt == 1]',setup='from __main__ import l, Counter',number=1)
0.005492186639457941