[erlang-questions] Question about reverse list of recursion functions

[Andrey Koleshko]

I completely understand that it’s artificial task and is not intended to be used in production. And, of course, I understand that I need to use the functions from the lists module. I just faced with the reverse issue a few times in other cases and that’s why this question has arisen. The quick sort function was just an example to demonstrate what I mean. Thanks for the “continuations” idea - it’s very helpful. Thank you, guys, for your responses. They are very impressing.
________________
Best Regards,
Andrey Koleshko
ka8725@REDACTED



> On Dec 31, 2015, at 3:09 AM, <ok@REDACTED> <ok@REDACTED> wrote:
> 
>> Hi, guys! I recently started to learn Erlang (migrating from Ruby) by
>> reading “Erlang Programming” Cesarini book. After the 3rd chapter
>> there is a task to implement quick sort and I implemented it like this:
>> https://gist.github.com/ka8725/f3fcc264e12bcefa6035
> 
> This was an exercise, so whatever you learn from is right.
> 
> In practice, you should be using the list reversal and sorting
> functions from the lists: module.
> 
> Instead of returning a compound data structure, it's often
> useful to think "continuations":
>   f(...) -> ...; f(...) -> {A,B,C}.
>   g(...) -> {A,B,C} = f(...), h(A, B. C).
> =>
>   g(...) -> f(.....).
>   f(.....) -> ...; f(.....) -> h(A, B, C, ...).
> 
> In the case of things like sorting, you can think of even and
> odd layers, working in opposite directions.  I'll leave you
> to work out the details.
> 
> Once you've eliminated reversing, the next thing would be
> to reduce concatenation.  (The wow-neat version of qsort
> in Prolog uses list differences for this purpose; Erlang
> would pass an accumulator, so
>    qsort(List, Acc) === qsort(List) ++ Acc)
> 
> However, you've missed the REALLY major point about the
> code, the reason you should never use it.
> 
> (A) It's quicksort, which has O(N**2) worst case.
>    Yes, I know the books say this will almost never happen,
>    but in practice it happens surprisingly often.
> 
>    As Bentley and McIlroy pointed out in their "Engineering
>    a Quicksort" paper, repeated values can kill a simple-
>    minded quicksort.  You need a "fat pivot", that is, you
>    need to split the list THREE ways:
> 
>    part([X|Xs], P, L, E, G, A) ->
>        if X < P -> part(Xs, P, [X|L], E, G, A)
>         ; P < X -> part(Xs, P, L, E, [X|G], A)
>         ; true  -> part(Xs, P, L, [X|E], G, A)
>        end;
>    part([], _, L, E, G, A) ->
>        sort(L, E ++ sort(G, A)).
> 
>    sort(List = [_,Pivot|_], Acc) ->
>        part(List, Pivot, [], [], [], Acc);
>    sort(List, Acc) ->
>        List ++ Acc.
> 
>    sort(List) ->
>        sort(List, []).
> 
> 
>    Oh, by the way, you will notice that this does no
>    reversal.  Why would it?  Yes, the intermediate
>    lists L and G are delivered in reverse order, but
>    we're going to *sort* them, so we don't *care* what
>    order they are in.  We would care if we were trying
>    to make a stable sorting routine, but quicksort is
>    not a stable sorting routine anyway.  Reversing a
>    list whose order you don't care about is pointless.
> 
> (B) Even with a "fat pivot" quicksort can still go
>    quadratic.  Taking the first element of the list
>    as the pivot means it WILL go quadratic if the
>    input is already sorted or nearly sorted, which turns
>    out to be quite common in practice.  This is why
>    array-based quicksorts use median-of-three pivot
>    selection and the Bentley & McIlroy version uses
>    the median of three medians of three for large enough
>    inputs.
> 
> Many people are impressed by the name "quick"sort and
> don't look into the background. When Hoare invented quick
> sort, he (a) already worked out most of the improvements
> people talk about and (b) KNEW that on a good day with the
> wind behind it quicksort would do more comparisons than
> merge sort.  BUT he needed to sort a bunch of numbers on
> a machine with an amount of memory that would disgrace a
> modern singing greeting card and just didn't have enough
> memory for workspace.  If comparisons are costly, it's
> easy for a well-written merge sort to beat quicksort.
> 
> For what it's worth, I have tested the code above but not
> benchmarked it.
> 
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20151231/65d8a443/attachment.htm>