[mlpack-git] [mlpack/mlpack] Heaps for mlpack! (#732)

MarcosPividori notifications at github.com
Fri Jul 22 11:47:43 EDT 2016


> +  {
> +    //! Value of this recommendation.
> +    double value;
> +    //! Item of this recommendation.
> +    size_t item;
> +    //! Trivial constructor.
> +    Candidate(double value, size_t item) :
> +        value(value),
> +        item(item)
> +    {};
> +    //! Compare the value of two candidates.
> +    friend bool operator>(const Candidate& l, const Candidate& r)
> +    {
> +      return l.value > r.value;
> +    };
> +  };

@rcurtin  , yes I have considered std::pair<> but I thought it would be clearer if we have specific structure for this (maybe value/item is clearer than first/second...). Of course, I can use std::pair<> if you think it would be better :)
However, I can see a problem with the relational operators of std::pair.
They compare the first element and, if these elements are equal, they compare the second element. So, I think we should set "first" to represent the value, and "second" to represent the index.
When we decide if inserting a new element to the list of candidates, we make a comparison with the top element: "if (c > pqueue.top())"
If we use a pair, it will insert c in the case where:

c.first == pqueue.top().first && c.second > pqueue.top().second

This is an unnecesary overhead, because we don't care on the order of the indexes, so we are inserting a new element with the same value but a greater index...

We could easily fix this by explicitly comparing the first element: "if (c.first > pqueue.top().first)"

However, I can see another possible disadvantage. Inside the implementation of the priority queue, if we use the std::pair relational operator, elements will be not only sorted by value but also by index. This can cause a bit more overhead when shifting down/up through the heap.

Maybe I became a bit obsessed with efficiency and this doesn't make a real difference...

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/pull/732/files/57dd61f1d823f209c8d0f67fa69f8a8ae0669d18#r71900589
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160722/a70b3798/attachment.html>


More information about the mlpack-git mailing list