Почему мой код считается медленным?

Question

[kaliboba]

Добрый день, решил учить алгоритмы, зашёл на leetcode, нашёл задачу (ссылка внизу), написал код, однако на 20 тесте он выдаёт огромный массив и пишет, что время вышло за лимит
Вопрос, что в нём не так

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = {i: nums.count(i) for i in nums}
        s = sorted(d.items(), key= lambda x:x[1],     reverse = True)
        result = [s[i][0] for i in range(k)]
        return result

https://leetcode.com/problems/top-k-frequent-eleme...

Answer 1

[Сергей Горностаев]

Изучение алгоритмов стоит начинать с чтения соответствующего учебника, как минимум станет известна методика оценки сложности алгоритма. И лучше это делать после того, как прочитан учебник по языку и документация по его стандартной библиотеке.

Answer 2

[Wataru]

Ваш алгоритм работает за O(n^2). Вы для каждого числа в массиве считатете, сколько раз оно туда входит проходя по массиву через nums.count(i). Оптимальное же решение работает O(n). Надо в хеш-таблице подсчитать, сколько раз каждое число встречается, потом через алгоритм QuickSelect выбрать k-ый c конца элемент.

Ну, или можно за O(n log n) отсортировать массив и потом за один проход подсчитать сколько раз каждое число встречается. Дальше можно второй раз отсортировать по количеству вхождений и выдать k-ый элемент. Это решение тоже пройдет.

Comments

[Alexandroppolus]

там в условии пишут, что должно быть быстрее чем O(n log n). Так что без QuickSelect не обойтись..

[Wataru]

Alexandroppolus, Можно и за O(n log k), если вместо quickSelect использовать приоритетную очередь на k элементов. Все-таки, задача даже не hard.

[Wataru]

Alexandroppolus, Проверил, такое решение с priority_queue проходит и даже beats 29%. Когда как за O(n) beats 80%

[res2001]

Можно и без хэш таблицы.
По условию каждый элемент массива лежит в диапазоне [-10^4; 10^4].
Это всего лишь 20001 возможное значение - не много. Можно посчитать гистограмму в массиве из 20001 элемента за один проход по исходному массиву. Дальше с помощью QuickSelect выбрать k наибольших значений гистограммы. Индекс в массиве гисторамм - это само число.
Правда нужно учесть, что числа могут быть отрицательные, а индекс - >=0. И еще QuickSelect частично сортирует массив, так что надо с этим то же что-то делать.

[Wataru]

res2001, Вы правы про замену хеш таблицы на массив из 20000 элементов. Это будет, несоменно, быстрее. Но про QuickSelect - как раз и нужно, чтобы он частично отсортировал массив. Надо же в задаче выдать не k-ый с конца, а все k максимальных элемента. И QuickSelect, если его попросить k-ый c конца элемент, как раз положит максимальные k-1 справа от него. Ровно как в задаче и надо. И все это за O(n) в среднем.

[Сергей Горностаев]

Задача оптимально решается в одну строку библиотечным вызовом.

[Wataru]

Сергей Горностаев, каким?

[Wataru]

Сергей Горностаев, Вот в C++ основная часть решения действительно есть в библиотеке. Наверняка такое и в питоне есть. Но количества все равно придетется руками считать.

[Bright144]

Wataru,

sorted(set(nums), key=nums.count, reverse=True)[:k]

[Сергей Горностаев]

Wataru,
Counter(nums).most_common(k)

[Wataru]

Bright144, Сергей Горностаев,

Это очень красивые однострочники, но они оба работают медленнее оптимального решения за O(n).

sorted(set(nums), key=nums.count, reverse=True)[:k]

работает за O(n log n), ибо сортирует весь массив.

Counter(nums).most_common(k) судя по всему, работает за O(n log k).

[res2001]

Wataru,

QuickSelect, если его попросить k-ый c конца элемент, как раз положит максимальные k-1 справа от него. Ровно как в задаче и надо. И все это за O(n) в среднем.

Согласен. Но проблема о которой я писал, связана с тем, что по условию задачи надо вывести сами числа (а не количества вхождений), а в частично отсортированном массиве гистограмм индекс в массиве уже перестанет быть искомым числом. Поэтому число то же надо будет хранить в массиве гистограмм, т.е. это будет массив структур в терминах С/С++ ( struct gist_s {int val, count; };). Это несколько увеличивает затраты по памяти в 2 раза, но это не критично.

Answer 3

[Rsa97]

d = {i: nums.count(i) for i in nums}
Здесь вы для каждого значения в списке полностью просматриваете весь список. В результате получаете сложность O(n²). Таким образом, объём вычислений у вас увеличивается квадратично от увеличения размера списка (список вырос в 2 раза, объём в 4, список в 100 раз, объём в 10000 раз). Соответственно, увеличивается и время, необходимое на вычисления.

Answer 4

[Александр Скуснов]

Так первая же строчка неэффективная:
for i in nums - один проход по массиву
nums.count(i) - для каждого прохода ещё один проход.
Т.е. если 1e6, то вы делаете 1e12 проходов.
2 и 3 строки уже быстрые.

Answer 5

[Bright144]

попробуй это

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return sorted(set(nums), key=nums.count, reverse=True)[:k]

leetcode у нас заблокирован. По теории так скорость выполнение кода должен значительно вырасти(почти 2раза).
Самый быстрый код это тот код когда решаешь всю задачу за один цикл(это мое мнение).
У тебя тут:
цикл для d;
цикл для s;
цикл для result;
В итоге 2 лишних циклов.