2

謎のタイトルですみません。これが私の問題です：

class Item
{
public:
    double value;
    void recomputeValue();   // after this, will probably increase a little, 
                             // but never decrease.
    std::list<Item*> neighbors;  // relatively few items
};

これらの項目のリストを指定されたサイズにトリミングする手順を実装しようとしています。

void trimToNewSize(std::list<Item*>& items, int newSize);

実装する必要があるアルゴリズムは次のとおりです。

while (size > newSize)
{
   erase item with smallest value;
   recomputeValue() for all its neighbors;
}

私は2つのアプローチを検討しました：

1.ヒープ

すべての値からヒープを構築します。ヒープは、O(1) の最小要素を見つけて削除でき、O(n) で構築できるため、適切です。

削除するたびに、ヒープ内のすべての隣人を見つけ、ヒープ内recomputeValue()の位置を更新します。

そこで、ウィキペディアとブーストでヒープ データ構造の浅い調査を行いました 。問題は、ヒープがその中の要素をすばやく見つける方法を提供していないように見えることです。

2.ハッシュテーブル

リストを値でソートします。ポインター Item* をリンク リスト内のそれらを指すイテレーターにマッピングするハッシュ テーブルを作成します。次に、リストから一番上の (最小の) アイテムを削除するたびに、ハッシュテーブルのおかげで一定時間内にリスト内のすべての隣接アイテムを見つけます。次に、各隣人についてrecomputeValue()、リスト内の位置とハッシュテーブル内の対応する反復子を更新します。

リンクされたリストの代わりに順序付きスキップリストを使用すれば、ハッシュテーブルの必要性がなくなるかもしれません。

私はプログラミングに慣れていないので、私のアプローチはおそらくあまりにも素朴で複雑であり、アドバイスを歓迎します.

私の質問を要約すると：

  1. ＃1を実現するためにヒープで高速ルックアップを実行する方法はありますか?
  2. #2 をよりクリーンにできるように、要素の順序を維持し、迅速なルックアップを実行できるコンテナーはありますか?
  3. どのように問題を処理しますか?
4

1 に答える 1

3

これは普通の老人の仕事のように見えますstd::map< double, Item * >。として最小要素を提供し* items.begin()、隣人を再計算するには、次のようにします

typedef std::map< double, Item * > itemsByValue;
itemsByValue items;

class Item
{
public:
    double value;
    void recomputeValue();   // after this, will probably increase a little, 
                             // but never decrease.
    std::list< itemContainer::iterator > neighbors;  // relatively few items
};

for ( itemsByValue::iterator i = neighbors.begin();
      i != neighbors.end(); ++ i ) {
    Item &item = * neighbor;
    items.erase( neighbor );
    item.recomputeValue();
    items.insert( std::make_pair( item.value, & item ) );
}
于 2013-03-07T09:39:42.433 に答える