3

要素EのコンテナCを設計したい.

E には 2 つの属性 (優先度、名前) があり、コンテナ内のすべての要素には一意の「名前」があります

このコンテナー C での次の操作をできるだけ効率的にサポートしたいと考えています。

  1. insert:- element1(name1, priority1) をコンテナに挿入します: C.insert(element(name1, priority1))
  2. update :- name=name1 の要素の優先度を priorityNew1 として更新: C[name1] = priorityNew1
  3. delete:-name=name1 の要素を削除します: C.delete(name1)
  4. 最も優先度の高い要素の取得と削除: C.pop()
  5. 優先度が最も高い要素を取得: C.peek()

基本的には、マップとヒープの組み合わせが必要です。要素の「名前」にマップし、要素の「優先度」にヒープします。最も理想的には、すべての操作を O(1) にしたいと考えています。それ以外の場合は、O(log N) として挿入、更新、削除し、O(1) としてポップ アンド ピークすることもできます。

次の2つのアプローチを考えることができました

1) 名前でハッシュ化された要素のハッシュ マップを使用します。したがって、insert update delete は O(1) pop であり、peek は O(N) であり、コンテナー全体を検索して最高の優先度を求めます。

2) 'name' と 'priority' の 2 つの列を持つテーブル 'element' で SQLite を使用する。実行時間は SQLite の実装に基づきます。

この問題についてもっと考えを知りたいと思っています。これに関連する現実の問題に直面しています。ご意見ありがとうございます。

4

2 に答える 2

2

Boost がうまくいくかどうかはわかりませんが、Boost Mutli Index をチェックしてみてください。 http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html

優先度のインデックスを保持して、要素を挿入するだけでなく、それらをすばやく取得できるようにすることもできます。同様に、MRU/LRU の状況でブースト マルチ インデックスを使用しました。 

#include <iostream>
#include <string>
#include <algorithm>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/optional.hpp>

struct bypriority{};
struct byseq{};

struct MyElement{
    typedef int priority_type;
    typedef std::string name_type;

    name_type name;
    priority_type priority;

    MyElement(const name_type& name, const priority_type& priority):name(name),priority(priority){};
};

std::ostream& operator<<(std::ostream& os, const MyElement& e){
    os << "Name: " << e.name << " Priority: " << e.priority;
    return os;
}

using namespace boost;
using namespace boost::multi_index;

template<typename Element>
struct Container{
    typedef multi_index_container<
        Element,
        indexed_by<
            //sequenced
            sequenced<tag<byseq> >,
            //ordered by priority
            ordered_non_unique<tag<bypriority>,member<Element,typename Element::priority_type,&Element::priority>, std::greater<typename Element::priority_type>  >
        >
    > Elements;


    void insert(const Element& e){
        typename Elements::template index<byseq>::type& list_view = elements.get<byseq>();
        list_view.push_back(e);
    }

    boost::optional<Element> peek() const{  
        boost::optional<Element> res;
        typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin();
        if(it != elements.get<bypriority>().end()){
            res.reset(*it);
        }
        return res;
    }

    boost::optional<Element> pop() {
        boost::optional<Element> res;
        typename Elements::template index<bypriority>::type& priority_index = elements.get<bypriority>();
        typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin();
        if(it != elements.get<bypriority>().end()){
            res.reset(*it);
            priority_index.erase(it);
        }

        return res;
    }

    void print_in_order(std::ostream& os) const{
        typedef  typename Elements::template index<byseq>::type elements_by_sequence;
        for(typename elements_by_sequence::iterator it = elements.get<0>().begin(); it != elements.get<0>().end(); it++){
            os << *it << std::endl;
        }
    }

    protected:
    Elements elements;
};



using namespace std;
int main(int argc, char *argv[]) {

    Container<MyElement> c;

    c.insert(MyElement("Bob",10));
    c.insert(MyElement("Alice",100));
    c.insert(MyElement("Fred",20));


    c.print_in_order(std::cout);

    cout << endl << "Highest Priority is " << endl << *c.peek() << endl;

    boost::optional<MyElement> alice = c.pop();
    if(alice){
        cout << "Popped results are " << *alice << endl;
    }


    cout << endl << "Now the contents are" << endl;
    c.print_in_order(std::cout);

}

出力します:

Name: Bob Priority: 10
Name: Alice Priority: 100
Name: Fred Priority: 20

Highest Priority is 
Name: Alice Priority: 100
Popped results are Name: Alice Priority: 100

Now the contents are
Name: Bob Priority: 10
Name: Fred Priority: 20
于 2013-02-28T16:04:36.777 に答える
2

O(logN)for each 操作が許容できる場合は、明らかboost::bimapに十分です。これは両面 std::mapのように機能します。2 つを一緒に維持するか、独自のラッパーを作成することで、ほぼ同じ結果を得ることができstd::mapます (しかし、なぜそうする必要があるのでしょうか?)。セルフバランシングを使用する二分探索木には、O(logN)最小限の検索用の がありますが、これはヒープよりも効率がわずかに劣ります。

効率が本当に重要な場合は、ヒープとハッシュ マップの両方を備えた独自のコンテナーを実装する必要があります。name次に、ヒープ内でスワップするときに、ハッシュ マップ内のヒープ配列内のサブスクリプションへのマッピングを維持します。これにより、挿入、削除、再割り当ての優先度 aO(logN)と最小/最大優先度要素が に与えられO(1)ます。（これは簡単に実装できるものではありませんが、面倒でもありません）

于 2013-02-28T16:27:59.150 に答える