Подсчет элементов в списке, которые встречаются только один раз: как мне оптимизировать производительность? Это очень медленно

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. Будут ли collection.Counter () лучшим выбором и как Лучше всего применить его здесь.

Спасибо!

Answer 1

Вы можете улучшить, используя Счетчик , в 2. для каждого элемента, вы перебираете весь список, и вы делаете это несколько раз для одного и того же пользователя, если пользователь встречается более одного раза.
Обратите внимание, что при использовании users.count(user) вы просматриваете весь список пользователей, чтобы подсчитать, сколько раз пользователь встречается. Это означает квадратичную c сложность по отношению к длине списка.
Используя счетчик, вы можете решить его с линейной сложностью.
Кроме того, в 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

Answer 2

Как уже упоминалось в вашем собственном комментарии, счетчик здесь значительно быстрее. Вы можете видеть из своего собственного времени, что создание набора результатов занимает около 10 мс (# 8 -> # 9), что примерно равно времени, которое потребует счетчик.

С счетчиком вы смотрите на один раз для каждого из N элементов, а затем один раз для каждого уникального элемента (не более N).

Когда вы используете .count(), вы перебираете весь список (быстрая реализация, но все же весь список) , Вы делаете это для каждого элемента, поэтому вы смотрите на каждый из N элементов N раз.

Каждый раз, когда ваш список увеличивается в 1000 раз, вам требуется 1000 раз для метода Counter, но в 1000000x для версий .count.