2

私はトップ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のアプローチは、O（n）でサイズnの完全なヒープを構築してから、ヒープの最上位要素をk×O（log n）で削除することです。find_topk2のアプローチは、最大要素が一番上になるようにサイズk（O（k））のヒープを構築し、次にkからnまで、要素が一番上の要素よりも小さいかどうかを比較し、そうである場合はポップすることです。一番上の要素を押して、新しい要素をプッシュします。これは、O（log k）のn倍を意味します。どちらのアプローチもまったく同じように記述されているため、実装の詳細（一時的なものの作成など）によって、アルゴとデータセット（ランダム）以外に違いが生じる可能性はないと思います。

ベンチマークの結果を実際にプロファイリングすることができ、find_topkが実際にfind_topk2よりも何度も比較演算子を呼び出していることがわかりました。しかし、私は理論的な複雑さの推論にもっと興味があります。2つの質問です。

  1. 実装またはベンチマークを無視して、O（n + k log n）がO（n log k）よりも優れていると期待するのは間違っていましたか？私が間違っている場合は、O（n log k）が実際に優れていることがわかるように理由と理由を説明してください。
  2. 私が1を期待するのが間違っていないのなら、なぜ私のベンチマークはそうではないのですか？
4

3 に答える 3

4

変数が互いにどのようにスケーリングするかについて仮定が必要なため、いくつかの変数の Big 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 になります。 (n) の方が優れています。

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) に隠されている定数は、現実的な n の log log n よりも大きくなる可能性があることに注意してください。

k = 定数の場合、O(n log k) = O(n) と O(n + k log n) = O(n) は同じです。

ただし、定数は大きな役割を果たします。たとえば、ヒープを構築するには、配列を 3 回読み取る必要がありますが、長さ k の優先キューを構築するには、配列を 1 回通過するだけで済みます。調べる。

したがって、どちらが「より良い」かは不明ですが、私の簡単な分析では、k の穏やかな仮定の下で O(n + k log n) のパフォーマンスが向上する傾向がありました。

たとえば、k が非常に小さい定数 (k = 3 など) である場合make_heap、実際のデータでは、このアプローチが優先キュー 1 よりもパフォーマンスが悪いことに賭ける準備ができています。

漸近分析を賢明に使用し、何よりも、結論を引き出す前にコードをプロファイリングします。

于 2011-07-12T19:45:28.433 に答える
1

2つの最悪の場合の上限を比較しています。最初のアプローチでは、最悪のケースは平均的なケースとほぼ同じです。2番目のケースでは、入力がランダムである場合、少数のアイテムをヒープに渡すまでに、上位Kのいずれも置き換えられないため、新しい値を一度に破棄する可能性があります。かなり高いので、これの最悪の場合の見積もりは悲観的です。

比較とは対照的に実時間を比較している場合、大きなヒープを使用するヒープベースのアルゴリズムは、ストレージの局所性がひどいため、多くのレースに勝つことができない傾向があります。また、最新のマイクロプロセッサの一定の要因は、終了するメモリのレベルに大きく影響されます。作業中-データが実際のメモリチップ（またはさらに悪いことに、ディスク上）にあり、キャッシュのレベルがそれほど遅くないことを見つけると、大幅に遅くなります-これは、ヒープソートが本当に好きなので残念です。

于 2011-07-12T19:50:08.993 に答える
0

ヒープを使用して自分で処理する代わりに、std::nth_element を使用できるようになったことに注意してください。デフォルトの比較演算子は std::less<>() であるため、次のように言えます。

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

これで、位置 0 から k までの myList が最小の k 要素になります。

于 2015-10-09T02:17:36.373 に答える