[erlang-questions] Question about reverse list of recursion functions
Andrey Koleshko
ka8725@REDACTED
Thu Dec 31 01:37:04 CET 2015
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>
More information about the erlang-questions
mailing list