Какой самый быстрый алгоритм для нахождения k-максимальных элементов последовательности с использованием stl-контейнеров

Question

Мне нужен самый быстрый алгоритм для нахождения k-максимальных элементов последовательности с использованием c ++ любых stl-контейнеров. Мои идеи: использовать список или вектор, отсортировать их, получить первые k-элементы. в этом случае количество операций равно n * log (n). n - количество элементов. Но я думаю, что это не самый лучший.

Answer 1

Метод, использующий std :: частичный_сорт, может быть лучшим ответом.

Также обратите внимание на std::nth_element, который просто получает элемент в n-й позиции справа (и разделяет последовательность на «меньше» до и «больше» послеэтот n-й элемент

Так что, если вы действительно заинтересованы в только первые k элементов ( без какого-либо конкретного внутреннего порядка ), то nth_element определенно принимаетбисквит

Answer 2

Я думаю, что лучший подход - использовать вектор для хранения результата и строить кучу в нем при прохождении ввода.Как только размер кучи достигает k, вы больше его не увеличиваете (и просто продолжаете всплывать, начиная с позиции k-1).

Когда ввод завершен, куча уже является ответом (предположим,Вас не просили вернуть их по порядку.)

Если, однако, k > n/2, то, вероятно, лучше хранить те, которые всплыли из кучи размером n - k (однако это предполагает, что вызаранее знать количество элементов n и не только k.

Answer 3

Можно сделать это за линейное время, используя алгоритм выбора , который принимает O(n) в худшем случае, а затем один раз пройдя вектор и выбрав точно те элементы, которые как минимум столь же великикак (nk) -статистическая статистика (и ведется подсчет того, сколько элементов вы взяли, так что вы берете ровно k и не более).Однако Cppreference говорит о том, что std::nth_element в среднем занимает линейное время, а не худший случай.Я объясню, как сделать это немного медленнее, но, вероятно, проще, используя кучи.Это решение требует времени O(max(n,k*log(k))) в худшем случае для извлечения верхних k элементов вектора размером n.

. Вы начинаете с создания max-heap со всеми элементами n, что занимает O (n) времени с std::make_heap.

. Теперь мы хотим извлечь из этой кучи k верхние элементы, но мы должны быть умными, когда делаем это.Если мы извлечем максимальный элемент k раз, это будет стоить нам O(log(n)) каждый раз, то есть всего O(k*log(n)), что не достигает нашей цели.

Вместо этого мы не будем касаться этого n-размер кучи и создать отдельную максимальную кучу, которую я называю «кучей ожидания».Эта ожидающая куча начинается только с максимального элемента в исходной куче, и для получения верхних k элементов вы повторяете следующую процедуру k раз: извлеките верхний элемент из ожидающей кучи и добавьте в него двух его потомков.Размер ожидающей кучи увеличивается на единицу на каждом шаге, поэтому он ограничен k.Поскольку мы делаем k извлечения и 2k вставки (при условии, что вы используете двоичную кучу), это будет стоить нам не больше, чем 3*k*log(k).

Answer 4

Я бы использовал std::make_heap для построения кучи из вашего массива или вектора значений, что потребует O(n) времени. Затем вы можете многократно проверять верхний элемент кучи и извлекать его k раза (используя std::pop_heap), что потребует O(k * log n) времени.

Общая сложность времени выполнения будет O(k * log n), что лучше, чем O (n * log k), потому что n больше, чем k. Как вы и спросили, все это уже доступно в <algorithm>, поэтому реализация очень проста.

Answer 5

К сожалению, я не могу найти исходный код, который я написал для этого, но проверьте это:

http://en.wikipedia.org/wiki/Radix_sort

Answer 6

Используя QuickSelect , вы можете найти их в O (n) наихудшем случае, используя «умный» вариант поворота, описанный на вики-странице (не отсортированный: это элементы, которые предшествуют k-му элементу в конечный порядок, вызванный алгоритмом).

Вы не можете победить O (n) (потому что вы должны «дотронуться» до всех элементов, чтобы убедиться, что выбранный вами элемент - k-й), поэтому это лучшее, что вы можете достичь.

Answer 7

РЕДАКТИРОВАТЬ: Если вам не важен порядок максимальных элементов, вы можете использовать nth_element для разбиения вектора, как отмечено @sehe. Это O(n).

В противном случае, если вы заботитесь о заказе:

Используйте std::partial_sort для вектора ваших данных, чтобы отсортировать первые k элементов. Это будет работать в O(n log k).

Поочередно сложите ваши данные и снимите k предметов. Это все еще O(n log k), но я верю с более высокими константами.

Если производительность представляет собой проблему, оба подхода подходят и используются быстрее для вашего набора данных.

Answer 8

Принимая случайные несортированные данные, я думаю, что самым быстрым является создание отсортированного связанного списка, зацикливание на исходном контейнере и для каждого элемента, если оно больше минимального значения в векторе результатов, подключите его (в правильном отсортированном месте). Если список теперь содержит больше, чем k элементов удаляют самое низкое значение.

Худший случай (отсортированный оригинальный контейнер) означает O(k*n), лучший случай O(n).