[Olsr-dev] Improving SPF with binary heaps

[Ferry Huberts]

Be aware that olsrd runs on many many platforms, including very small 
embedded ones.

Doing a 1/x is very much not preferred for lack of floating point 
hardware on those platforms.
Try to stick to integer math where possible.

On 13/07/15 18:01, Saulo Queiroz wrote:
> Yes,
> something like 1/priority_value (for instance) might work.
>
> On 13 July 2015 at 03:12, Henning Rogge <(spam-protected)
> <mailto:(spam-protected)>> wrote:
>
>     Hi,
>
>     just that I understand it right... you can normally only access "one
>     end" of the PQ easily... so if you want to get a "maximum queue" you
>     need some code-change... or you just have to negate the key before
>     inserting an element.
>
>     Henning
>
>     On Sun, Jul 12, 2015 at 2:56 PM, Saulo Queiroz
>     <(spam-protected) <mailto:(spam-protected)>> wrote:
>      > Yes with a little remark to functions of type first/last. We have
>     two kinds
>      > o PQs: MINimum and MAXimum. In min PQs, item priority means being
>     associated
>      > to low values (case of Dijkstra). In this case, get_first would
>     return the
>      > item with lowest number but get_last doesn't make sense. Similar
>     situation
>      > happens for max priority queues.
>      > ....
>      >
>      > the lower the priority number associated
>      >
>      > Em 12/07/2015 04:26, "Henning Rogge" <(spam-protected)
>     <mailto:(spam-protected)>> escreveu:
>      >>
>      >> On Sun, Jul 12, 2015 at 3:48 AM, Saulo Queiroz
>     <(spam-protected) <mailto:(spam-protected)>>
>      >> wrote:
>      >> >> Basics for both lists and AVL trees in OONF (which is the base of
>      >> >> OLSRv2)
>      >> >> is
>      >> >> - init
>      >> >> - insert
>      >> >> - remove
>      >> >> - get(key)
>      >> >> - get_first
>      >> >> - get_last
>      >> >>
>      >> >> and a good way to iterate over the elements of the tree/list
>     (which
>      >> >> would enable me to write iterator macros like the ones in
>      >> >>
>      >> >>
>      >> >>
>     http://olsr.org/git/?p=oonf.git;a=blob;f=src-api/common/list.h;h=a6146dcc9eb4d70ef1c2ae32b382df0460d948b0;hb=master#l315
>      >> >> ).
>      >> >>
>      >> >> Can we have the same functions for a binary heap?
>      >> >
>      >> > It is possible but i think few procedures don't sound
>     reasonable because
>      >> > binary heaps
>      >> > are Priority Queues (PQs) by nature being different from the
>     typical
>      >> > data
>      >> > structures.
>      >> > In general, one employs priority queues when all items are
>     expected to
>      >> > leave
>      >> > the structure until the end of the execution of a procedure
>     (what is
>      >> > very
>      >> > usual in the so-called "greedy algorithms" like Dijkstra). In
>     "normal"
>      >> > data
>      >> > structures, there is no problem if an item stay in the structure
>      >> > "forever".
>      >>
>      >> Okay,
>      >>
>      >> so its more like
>      >>
>      >> - insert
>      >> - remove first/last
>      >> - get first/last
>      >>
>      >> Maybe even with get and remove combined into the same function, so
>      >> that you can get the first/last element of the heap and remove it.
>      >>
>      >> Does this make more sense?
>      >>
>      >> Henning
>
>
>
>
> --
> Saulo Jorge bq
> -
> "In theory, there is no difference between practice and theory, in
> practice there is"
> -- Someone
>
>

-- 
Ferry Huberts