Медленно изменяемые приоритетной очереди


Мне нужен изменяемый очередь с приоритетами (приоритеты могут быть изменены) для моего текущего проекта, и начали просто оборачивать класс по СТД::вектора и сделать/нажать/pop_heap. Однако, это не почти достаточно быстро, профилирования показывает ~70% времени на обработку тратится в очереди. Мне нужны данные о том, как исправить очереди, или если уже существует то, что может сделать это, но лучше (есть mutable_queue в Boost, но в "отложенные" каталог, например).

template <typename ValueT, typename KeyT>
class UnconsistentQueue {
    struct Elem {
        Elem(const ValueT& v_, const KeyT& p_) : v(v_), p(p_) {}
        bool operator<(const Elem& rhs) const { 
            // Note that this is reversed, since we want a lowest-first prio queue
            return rhs.p < p; 
        }
        ValueT v;
        KeyT p;
    };
public:
    typedef typename std::vector<Elem>::iterator iterator;
    typedef typename std::vector<Elem>::const_iterator const_iterator;

    void push(const ValueT& v, const KeyT& p) {
        q.push_back(Elem(v, p));
        std::push_heap(q.begin(), q.end());
    }

    void update(const ValueT& v, const KeyT& p) {
        update(v, p, q.begin());
    }
    void update(const ValueT& v, const KeyT& p, const_iterator hint) {
        iterator i = q.begin();
        if(hint->v == v)
            std::advance(i, std::distance<const_iterator>(q.begin(), hint));
        else {
            for(; i != q.end(); ++i) {
                if(i->v == v) 
                    break;
            }
        }
        if(i != q.end()) {
            i->p = p;
            std::make_heap(q.begin(), q.end());
        }
    }

    void pop() {
        std::pop_heap(q.begin(), q.end());
        q.pop_back();
    }

    const ValueT& top() const { return q.front().v; }
    const KeyT& top_key() const { return q.front().p; }

    const_iterator begin() const { return q.begin(); }
    const_iterator end() const { return q.end(); }
    const_iterator find(const ValueT& v) const {
        const_iterator i;
        for(i = q.begin(); i != q.end(); ++i) {
            if(i->v == v)
                break;
        }
        return i;
    }
    void remove(const ValueT& v) {
        const_iterator i = find(v);
        if(i != q.end()) {
            q.erase(i);
            std::make_heap(q.begin(), q.end());
        }
    }

    bool empty() const { return q.empty(); }
    void clear() { q.clear(); }
private:
    std::vector<Elem> q;
};

В моем проекте, в качестве типа ключа, закодированного в этой структуре:

template <typename CostType>
struct Key {
    bool operator<=(Key<CostType> rhs) const {
        return (k1 <= rhs.k1) || (k1 == rhs.k1 && k2 <= rhs.k2);
    }
    bool operator<(Key<CostType> rhs) const {
        return (*this <= rhs) && !(rhs <= *this);
    }
    CostType k1;
    CostType k2;
};

(Документ, который определяет алгоритм только определяет <= оператора, но мне нужны строгие слабые приказывающ, поэтому я реализовал это так. Хороший?)

Ниже приводится соответствующая часть результатов профилирования создается компания AMD CodeAnalyst

CS:EIP      Symbol + Offset                                                                                                                                                                                                                                                         64-bit  Timer samples   
0xf156c0    Key<double>::operator<=                                                                                                                                                                                                                                                         14.45           
0xf1c350    std::_Adjust_heap<UnconsistentQueue<unsigned int,Key<double> >::Elem *,int,UnconsistentQueue<unsigned int,Key<double> >::Elem>                                                                                                                                                  7.29            
0xf140d0    Key<double>::operator<                                                                                                                                                                                                                                                          6.91            
0xf1d260    UnconsistentQueue<unsigned int,Key<double> >::Elem::operator<                                                                                                                                                                                                                   6               
0xf1c250    std::_Push_heap<UnconsistentQueue<unsigned int,Key<double> >::Elem *,int,UnconsistentQueue<unsigned int,Key<double> >::Elem>                                                                                                                                                    5.64            
0xf15910    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator!=                                                                                              4.56            
0xf16570    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator==                                                                                              4.27            
0xf15160    UnconsistentQueue<unsigned int,Key<double> >::find                                                                                                                                                                                                                              4.01            
0xf16130    std::vector<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> >::end                                                                                                                                        3.99            
0xf1b0b0    std::_Make_heap<UnconsistentQueue<unsigned int,Key<double> >::Elem *,int,UnconsistentQueue<unsigned int,Key<double> >::Elem>                                                                                                                                                    3.21            
0xf16a90    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,             2.97            
0xf15b50    std::_Tree<std::_Tmap_traits<unsigned int,double,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,double> >,0> >::_Lbound                                                                                                                                   2.93            
0xf16540    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator++                                                                                              2.41            
0xf1c240    std::_Move<UnconsistentQueue<unsigned int,Key<double> >::Elem &>                                                                                                                                                                                                                1.86            
0xf16500    std::_Vector_const_iterator<std::_Vector_val<UnconsistentQueue<unsigned int,Key<double> >::Elem,std::allocator<UnconsistentQueue<unsigned int,Key<double> >::Elem> > >::operator*                                                                                               1.81            

15 functions, 408 instructions, Total: 120448 samples, 72.33% of shown samples, 32.53% of total session samples


1607
2
задан 16 августа 2011 в 05:08 Источник Поделиться
Комментарии
1 ответ

В стандартной комплектации уже имеет приоритетную очередь.

std::priority_queue

Внутренне он использует std::вектор<> (по умолчанию), но элементы в векторе организованы в бинарное дерево, для более быстрой сортировки и организации. (элемент, т. е. 0 является корнем, элемент 1,2 дети от 0 и т. д.).

Если вы хотите сделать это вручную, вы можете со своей тарой и следующих методов:

Проблема со структурой кучи это только действительно поддерживает снятие головной узел. Как только вы начинаете удаления узлов в середине нужно заново строить кучи вручную (который, кажется, ваша проблема). Согласно документации ре-дом на карте линейный (вплоть до 3n плюс ваши линейного перемещения таким образом 4Н) так o(n) времени.

Так что не похоже, что вы действительно хотите приоритетной очереди. То, что вы действительно хотите использовать функцию std::карта. Это позволяет за o(журнал(N)) вставка и удаление элементов в любом месте на карте и в контейнере поддерживается в отсортированном порядке (используя строгие слабые приказывающ). Так можно пройти по карте в порядке, если требуется.

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

Конечно будет стоить в через карту, которая является дополнительной памяти он будет использовать (вектор является очень эффективным с точки зрения использования памяти).

3
ответ дан 16 августа 2011 в 06:08 Источник Поделиться