Ускорение кода Python для больших наборов данных
Решаю задачу на HackerEarth (полный текст можно найти здесь):
У Боба есть список воспроизведения песен, с каждой песней связан исполнитель (обозначается целым числом).
Любимый певец Боба — тот, чьих песен больше всего в плейлисте.
Посчитайте количество любимых певцов Боба
Например, если на входе [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))
Ответы 1
узкие места и улучшения
В вашем коде есть два основных неэффективных шага.
Здесь вы ищете в списке уникальные значения для каждого нового элемента. Как только результат станет большим, этот поиск станет неэффективным.
for i in singer_tokens[:]:
if i not in result: # this is inefficient
result.append(i)
Этот шаг эффективно выполняется с использованием набора в Python:
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
Или, лучше, используя коллекции.Счетчик:
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