[erlang-questions] [ANN] Priority Queue Implementation

[Michael Truog]

Perhaps you perceive quality as an academic type of quality, where all descriptions are short so they can be consumed quickly and easily.  I agree the code for pqueue.erl is long, however, that is a price for efficiency in that case.  So, it really depends on how you judge quality.  When you consider data structures as stable building blocks for higher-level logic, you might realize that data structures source code never really changes that much once it is acceptable.  So, even if the source code is dense, it isn't something that needs to be modified... quite the contrary, it shouldn't need modifications since it is meant to be a stable building block.  You are welcome to try and create something more efficient with a smaller amount of code.  That might achieve the quality you think is missing.

On 11/12/2011 04:03 PM, Hynek Vychodil wrote:
> Keeping separate implementations for each edge cases even they do same
> thing will never help improve quality of code. DRY
>
> On Sat, Nov 12, 2011 at 8:14 PM, Michael Truog <mjtruog@REDACTED> wrote:
>> 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
>>>>>>
>>>
>>
>
>