получить максимальные значения верхнего k

Question

Теперь у меня есть выражение y=0.5*a+0.7*b+0.4*c, где 0<a,b,c<1. Предположим, что имеется таблица список для значений a,b,c, например:

(a, b, c) 
--------------- 
(0.9, 0.4, 0.6) 
(0.5, 0.8, 0.4) 
(0.7, 0.4, 0.8) 
(0.9, 0.2, 0.1) 
... 

Есть несколько быстрых способов найти топ k=3 значения для y?

Я знаю, что перебор способ перечислить каждые кортежи (a,b,c) для вычисления y, а затем найти K наибольших значений для у, но когда число кортежей огромны, кажется, что этот метод не очень эффективный. Поэтому любые другие способы приветствуются!

Answer 1

Прогулка по каждому кортежу. Когда вы его прочитаете, оцените выражение на нем и сохраните массив из трех основных значений.

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

(Что касается того, почему я предлагаю хранить верхние значения в массиве, а не что-то более увлекательное, как куча: когда k = 3, постоянные накладные расходы на все, что использует нетривиальное число команд для выполнения или для которых требуется достаточное количество памяти что вы не всегда будете получать кеш-хит, перевешивает любые асимптотические выгоды, предоставляемые структурой данных.)

Answer 2

Вам все равно придется проходить через каждый кортеж в таблице, независимо от того, что вы делаете , так что это будет как минимум операция O(n). Только для трех верхних значений вы можете запрограммировать массив размером 3 и требуемые проверки if.

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

Answer 3

Используя Быстрый выбор даст вам O (N) сложность в среднем:

1. Предполагая, что имеется п элементов и у = е (а, б, в), вычисляют массив Y длины N для каждого of (a, b, c) (добавьте индекс к (a, b, c) в Y, а также для обратной ссылки, которая вам понадобится позже).
2. Используйте QuickSelect на Y для получения статистики (N-k) -го порядка и получите результирующий Y. Элементы Y [N-k-1] до Y [N-1] будут вашими k самыми большими элементами.
3. Сортируйте Y [N-k-1] в Y [N-1], чтобы получить результат.