12

これは宿題ではありません。

最後の N 個のアイテムを最小値で保存するために、小さな「優先キュー」(現時点では配列として実装) を使用しています。これは少し遅いです - O(N) アイテムの挿入時間。現在の実装では、配列内の最大のアイテムを追跡し、配列に収まらないアイテムを破棄しますが、操作の数をさらに減らしたいと考えています。

次の要件に一致するプライオリティ キュー アルゴリズムを探しています。

  1. queue は配列として実装できますが、これはサイズが固定で、拡張できません。キュー操作中の動的メモリ割り当ては固く禁じられています。
  2. 配列に収まらないものはすべて破棄されますが、キューはこれまでに遭遇した最小の要素をすべて保持します。
  3. O(log(N)) の挿入時間 (つまり、要素をキューに追加するには、最大で O(log(N)) かかる必要があります)。
  4. (オプション) キュー内の *最大* アイテムに対する O(1) アクセス (キューには *最小* アイテムが格納されるため、最大のアイテムが最初に破棄され、操作の数を減らすためにそれらが必要になります)
  5. 実装/理解が容易。理想的には、二分探索に似たもので、一度理解すると永遠に記憶されます。
  6. 要素をソートする必要はありません。これまでに遭遇した N 最小値を維持する必要があります。それらが必要になったら、それらすべてに一度にアクセスします。したがって、技術的にはキューである必要はありません。N個の最後の最小値を保存する必要があるだけです。

最初はバイナリ ヒープを使用することを考えていました (配列を介して簡単に実装できます) が、配列がそれ以上大きくならない場合、うまく動作しないようです。リンクされたリストと配列では、物事を移動するのに余分な時間が必要になります。stl プライオリティ キューは大きくなり、動的割り当てを使用します (ただし、これについては間違っている可能性があります)。

それで、他のアイデアはありますか？

--EDIT--
STL 実装には興味がありません。STL 実装 (数人が提案) は、関数呼び出しの数が多いため、現在使用されている線形配列よりも動作が少し遅くなります。

実装ではなく、プライオリティ キューアルゴリズムに興味があります。

4

8 に答える 8

18

配列ベースのヒープは、あなたの目的には理想的です。あなたがそれらを拒否した理由がわかりません。

最大ヒープを使用します。

これまでに見た N 個の最小要素を含む N 個の要素ヒープ (配列として実装) があるとします。

要素が入ってきたら、最大 (O(1) 時間) をチェックし、それより大きい場合は拒否します。

入ってくる値が低い場合は、ルートを新しい値に変更し、この変更された値をふるいにかけます - 最悪の場合 O(log N) 時間。

選別プロセスは単純です。ルートから開始し、各ステップで、max-heap プロパティが復元されるまで、この値をより大きな子と交換します。

したがって、 std::priority_queue を使用する場合は、おそらく必要になる削除を行う必要はありません。std::priority_queue の実装によっては、メモリの割り当て/割り当て解除が発生する可能性があります。

したがって、次のようなコードを使用できます。

  • サイズ N の割り当てられた配列。
  • 表示される最初の N 個の要素を入力します。
  • heapify (これは標準的なテキストブックに記載されているはずです。これはふるい分けを使用します)。これがO(N)です。
  • 取得した新しい要素は、O(1) 時間で拒否するか、最悪の場合は O(logN) 時間でふるい分けて挿入します。

ただし、平均的には、新しい値を完全にふるいにかける必要はなく、O(logn) 平均挿入時間よりも良くなる可能性があります (ただし、私はそれを証明しようとはしていません)。

サイズ N の配列を 1 回割り当てるだけで、挿入は配列の要素を交換することによって行われるため、その後は動的なメモリ割り当てはありません。

heapify と sift-down の疑似コードがある wiki ページをチェックしてください: http://en.wikipedia.org/wiki/Heapsort

于 2010-05-29T17:35:06.213 に答える
8

一番大きなものを先頭にしstd::priority_queueて使います。新しいアイテムごとに、それがヘッド アイテムの場合は破棄し、そうでない場合はヘッド アイテムをポップして新しいアイテムを挿入します。>=

補足: 標準コンテナは、成長させた場合にのみ成長します。新しいアイテムを挿入する前に (もちろん、最大サイズに達した後) 1 つのアイテムを削除する限り、これは発生しません。

于 2010-05-29T05:15:42.887 に答える
1

私が働いているほとんどの優先キューは、リンクリストに基づいています。事前に決定された数の優先度レベルがある場合は、リンクリストの配列（優先度レベルごとに1つのリンクリスト）を使用することで、O（1）挿入を使用して優先度キューを簡単に作成できます。もちろん、同じ優先度のアイテムはいずれかのFIFOに縮退しますが、それは許容できると見なすことができます。

追加と削除は次のようになります（APIは異なる場合があります）...

listItemAdd (&list[priLevel], &item);      /* Add to tail */
pItem = listItemRemove (&list[priLevel]);  /* Remove from head */

キューの最初のアイテムを取得すると、優先度が最も高い空でないリンクリストを見つけることが問題になります。それはO（N）かもしれませんが、それをスピードアップするために使用できるいくつかのトリックがあります。

  1. 優先度キュー構造では、現在の最高の優先度を持つリンクリストへのポインタやインデックスなどを保持します。これは、アイテムが優先キューに追加または削除されるたびに更新する必要があります。
  2. ビットマップを使用して、どのリンクリストが空でないかを示します。最上位ビットの検索または最下位ビットの検索アルゴリズムと組み合わせると、通常、一度に最大32個のリストをテストできます。繰り返しますが、これは追加/削除のたびに更新する必要があります。

お役に立てれば。

于 2010-05-29T11:45:47.343 に答える
0

解決策が見つかりました（「difference」はコード内の「priority」を意味し、maxRememberedResultsは255です（任意の（2 ^ n-1）である可能性があります））。

template <typename T> inline void swap(T& a, T& b){
    T c = a;
    a = b;
    b = c;
}


struct MinDifferenceArray{
    enum{maxSize = maxRememberedResults};
    int size;
    DifferenceData data[maxSize];
    void add(const DifferenceData& val){
        if (size >= maxSize){
            if(data[0].difference <= val.difference)
                return;

            data[0] = val;

            for (int i = 0; (2*i+1) < maxSize; ){
                int next = 2*i + 1;
                if (data[next].difference < data[next+1].difference)
                    next++;
                if (data[i].difference < data[next].difference)
                    swap(data[i], data[next]);
                else
                    break;
                i = next;
            }
        }
        else{
            data[size++] = val;
            for (int i = size - 1; i > 0;){
                int parent = (i-1)/2;
                if (data[parent].difference < data[i].difference){
                    swap(data[parent], data[i]);
                    i = parent;
                }
                else
                    break;
            }
        }
    }

    void clear(){
        size = 0;
    }

    MinDifferenceArray()
        :size(0){
    }
};
  1. 最大ベースのキューを構築します（ルートが最大です）
  2. いっぱいになるまで、普通にいっぱいにします
  3. それがいっぱいになると、すべての新しい要素に対して
    1. 新しい要素がルートよりも小さいかどうかを確認します。
    2. ルート以上の場合は拒否します。
    3. それ以外の場合は、ルートを新しい要素に置き換えて、通常のヒープの「シフトダウン」を実行します。

そして、最悪のシナリオとしてO（log（N））挿入を取得します。

これは、ユーザーが「Moron」というニックネームで提供したものと同じソリューションです。返信ありがとうございます。

PSどうやら、十分に眠らずにプログラミングするのは良い考えではありませんでした。

于 2010-05-29T18:46:10.030 に答える
0

Matters Computationalは 158 ページを参照してください。実装自体は非常によくできており、読みにくくすることなく少し調整することもできます。たとえば、左の子を次のように計算する場合:

int left = i / 2;

次のように rightchild を計算できます。

int right = left + 1;
于 2010-05-29T17:38:37.777 に答える
0

優先度の量が少なく固定されている場合は、優先度ごとにリングバッファを使用できます。オブジェクトが大きい場合、これはスペースの浪費につながりますが、それらのサイズがオブジェクトに追加のポインターを格納するバリアントよりもポインター/インデックスに匹敵する場合、同じように配列のサイズが増加する可能性があります。
または、配列内で単純な単一リンク リストを使用して 2*M+1 のポインター/インデックスを格納することもできます。1 つは最初の空きノードを指し、他のペアは各優先度の先頭と末尾を指します。その場合、平均で比較する必要があります。O(1) で次のノードを取り出す前に O(M)。そして、挿入には O(1) かかります。

于 2010-05-29T05:48:31.043 に答える
0

STL プライオリティ キューを最大サイズ (おそらくプレースホルダーで初期化されたベクトルから) で構築し、挿入前にサイズを確認すると (必要に応じてアイテムを事前に削除します)、挿入操作中に動的割り当てが行われることはありません。STL の実装は非常に効率的です。

于 2010-05-29T06:45:46.120 に答える