Наименьший K алгоритм наименьшего выбора - O (n + k log n) против O (n log k) для k << N

Question

Я спрашиваю об этом в отношении алгоритма Top K. Я думаю, что O (n + k log n) должно быть быстрее, потому что хорошо ... например, если вы попытаетесь подключить k = 300 и n = 100000000, например, мы можем увидеть, что O (n + k log n) меньше.

Однако, когда я делаю тест с C ++, он показывает мне, что O (n log k) более чем в 2 раза быстрее. Вот полная программа бенчмаркинга:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <ctime>
#include <cstdlib>
using namespace std;

int RandomNumber () { return rand(); }
vector<int> find_topk(int arr[], int k, int n)
{
   make_heap(arr, arr + n, greater<int>());

   vector<int> result(k);

   for (int i = 0; i < k; ++i)
   {
      result[i] = arr[0];
      pop_heap(arr, arr + n - i, greater<int>());
   }

   return result;
}

vector<int> find_topk2(int arr[], int k, int n)
{
   make_heap(arr, arr + k, less<int>());

   for (int i = k; i < n; ++i)
   {
      if (arr[i] < arr[0])
      {
     pop_heap(arr, arr + k, less<int>());
     arr[k - 1] = arr[i];
     push_heap(arr, arr + k, less<int>());
      }
   }

   vector<int> result(arr, arr + k);

   return result;
}


int main()
{
   const int n = 220000000;
   const int k = 300;

   srand (time(0));
   int* arr = new int[n];

   generate(arr, arr + n, RandomNumber);

   // replace with topk or topk2
   vector<int> result = find_topk2(arr, k, n);

   copy(result.begin(), result.end(), ostream_iterator<int>(cout, "\n"));


   return 0;
}

Подход find_topk состоит в том, чтобы создать полную кучу размером n в O (n), а затем удалить верхний элемент кучи k раз O (log n). Подход find_topk2 состоит в том, чтобы создать кучу размером k (O (k)) таким образом, чтобы максимальный элемент находился сверху, а затем от k до n, сравнить, чтобы увидеть, меньше ли какой-либо элемент, чем верхний элемент, и, если это так, поп верхний элемент, и нажмите новый элемент, который будет означать n раз O (log k). Оба подхода написаны одинаково, поэтому я не верю, что какие-либо детали реализации (например, создание временных и т. Д.) Могут вызвать разницу, кроме алгоритма и набора данных (который является случайным).

Я мог бы на самом деле профилировать результаты теста и мог видеть, что find_topk на самом деле вызывал оператор сравнения гораздо больше, чем find_topk2. Но меня больше интересует обоснование теоретической сложности ... поэтому два вопроса.

1. Не обращая внимания на реализацию или тест, не ошибся ли я, полагая, что O (n + k log n) должно быть лучше, чем O (n log k)? Если я ошибаюсь, пожалуйста, объясните, почему и как рассуждать так, что я вижу, что O (n log k) действительно лучше.
2. Если я не ошибаюсь, ожидать нет 1. Тогда почему мой тест показывает иначе?

Answer 1

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

Если, например. k ~ n ^ (1/2), тогда O (n log k) становится O (n log n), а O (n + k log n) становится O (n + n ^ (1/2) log n) = O (п), что лучше.

Если k ~ log n, то O (n log k) = O (n log log n) и O (n + k log n) = O (n), что лучше. Обратите внимание, что log log 2 ^ 1024 = 10, поэтому константы, скрытые в O (n), могут быть больше, чем log log n для любого реалистического n.

Если k = константа, то O (n log k) = O (n) и O (n + k log n) = O (n), что одинаково.

Но константы играют большую роль: например, построение кучи может потребовать чтения массива 3 раза, тогда как построение очереди приоритетов длиной k по мере выполнения требует только одного прохода через массив и небольшого журнала постоянных времен K для поиска.

То, что «лучше», поэтому неясно, хотя мой быстрый анализ показал, что O (n + k log n) работает лучше при умеренных допущениях на k.

Например, если k - очень маленькая константа (скажем, k = 3), то я готов поспорить, что подход make_heap работает хуже, чем приоритетная очередь 1 для данных реального мира.

Используйте асимптотический анализ с умом и, прежде всего, профилируйте свой код, прежде чем делать выводы.

Answer 2

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

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

Answer 3

Имейте в виду, что теперь вы можете использовать std :: nth_element вместо необходимости использовать кучу и делать что-то самостоятельно.Поскольку оператором сравнения по умолчанию является std :: less <> (), вы можете сказать что-то вроде этого:

std :: nth_element (myList.begin (), myList.begin () + k, myList.end());

Теперь myList с позиций от 0 до k будет наименьшим k элементов.