[erlang-questions] [ANN] Priority Queue Implementation

[Michael Truog]

On 11/12/2011 05:19 AM, Hynek Vychodil wrote:
> There is not need make special priority implementation in Erlang.

Oh, but there is!  I think it is nice to have efficient data structures, just to keep software efficient.  So, there is a need, especially in a language like Erlang that happens to be slower than more native code execution.  Pursuing quality can help us avoid software that just becomes slower as it grows (see http://en.wikipedia.org/wiki/Wirth%27s_law).

So, yes, there is no need to care, unless you care about quality.

> On Sat, Nov 12, 2011 at 6:06 AM, Michael Truog <mjtruog@REDACTED> wrote:
>> I was looking for a priority queue implementation where the priority is separate from the value being queued, where the order is preserved for the same priority.  That might not be a typical application of a heap to a priority queue, because it might be expected to lose order within the heap structure.  Since I want the priority to be separate from the value, the data structure I am trying to pursue is a bit different.
>>
>> On 11/11/2011 09:08 AM, Hynek Vychodil wrote:
>>> I have used this pretty raw but simple priority queue implementation
>>> for mine primes generation with true sieve:
>>>
>>> -module(pair_heap).
>>>
>>> -compile(inline).
>>>
>>> -export([new/0, insert/2, find_min/1, delete_min/1, merge/2, to_list/1,
>>>     from_list/1, insert_list/2]).
>>>
>>> new() -> [].
>>>
>>> find_min([H|_]) -> H;
>>> find_min([]) -> empty.
>>>
>>> %insert(E, H) -> merge([E], H).
>>> insert(E, []) -> [E];
>>> insert(E, [EH|SH]) when EH < E -> [EH|[[E]|SH]];
>>> insert(E, [_|_]=H) -> [E|[H]].
>>>
>>> merge([EA|_]=A, [EB|SB]) when EB < EA -> [EB|[A|SB]];
>>> merge([EA|SA], [_|_]=B) -> [EA|[B|SA]];
>>> merge([], B) -> B;
>>> merge(A, []) -> A.
>>>
>>> delete_min([]) -> [];
>>> delete_min([_|SH]) ->
>>>   merge_pairs(SH).
>>>
>>> merge_pairs([]) -> [];
>>> merge_pairs([X]) -> X;
>>> merge_pairs([A,B|T]) -> merge(merge(A,B), merge_pairs(T)).
>>>
>>> to_list([]) -> [];
>>> to_list(H) -> [find_min(H) | to_list(delete_min(H))].
>>>
>>> from_list([]) -> [];
>>> from_list(L) -> insert_list(L, new()).
>>>
>>> insert_list([E|T], H) -> insert_list(T, insert(E, H));
>>> insert_list([], H) -> H.
>>>
>>> It worked pretty well and fast for mine purposes.
>>>
>>> On Fri, Nov 11, 2011 at 4:42 PM, Jesper Louis Andersen
>>> <jesper.louis.andersen@REDACTED> wrote:
>>>> On Thu, Nov 10, 2011 at 09:12, Michael Truog <mjtruog@REDACTED> wrote:
>>>>> I previously added code that took care of that case, where two nodes needed
>>>>> to be merged that both have queues.  However, I convinced myself at the
>>>>> time, that the case would never happen.  So, the code probably needs to be
>>>>> thought-through a bit more with more testing, but my hope is that merging
>>>>> the queues isn't necessary.
>>>> I have tested (tasted, but my typo was funnier) the forbidden fruit
>>>> that is QuickCheck/PropEr. Your repository now has a pull-request in
>>>> which I add partial testing via proper_statem. It generates an
>>>> internal crash of the data structure code if we makes a bunch of
>>>> inserts and then call len(), see
>>>>
>>>> https://github.com/okeuday/pqueue/issues/4
>>>>
>>>> Only your pqueue2 implementation is affected. pqueue is not shown to
>>>> have any errors (yet). The crash is naturally in the "merge" part of the code :P
>>>>
>>>> --
>>>> J.
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>> erlang-questions@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>
>>>
>>
>
>