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

[Dmitry Kolesnikov]

Hello Joe,

Thank you for pointing this out! I was wrong! lists:foldr look lucrative but tuple creation kills performance.

I’ve played around with various versions of quick sort implementations, measured its performance on list of 10K elements. I’ve tried to replace tuple accumulator with list accumulator but … As the conclusion, the original implementation that uses lists:reverse/1 is the best one in terms of performance.

Here is the visualized results of benchmark and code.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: summary.png
Type: image/png
Size: 254310 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20151228/fedbb2cd/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qsort.erl
Type: application/octet-stream
Size: 2154 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20151228/fedbb2cd/attachment.obj>
-------------- next part --------------


Please note that graph shows time in microseconds event the label says (ms). 
The legend is following:
sortl  - quick sort uses lists:reverse
sortf  - quick sort uses lists:foldr and tuple as accumulator
sortfl - quick sort uses lists:foldr and list [Lesser|Bigger] as accumulator 
sortx  - quick sort uses list replacement using [Lesser|Bigger] as accumulator 

I think the sortl is the fastest because it uses tail-recursion while other using normal recursion. 

Best Regards, 
Dmitry


> On Dec 27, 2015, at 11:57 PM, Joe Armstrong <erlang@REDACTED> wrote:
> 
> On Sun, Dec 27, 2015 at 11:12 AM, Dmitry Kolesnikov
> <dmkolesnikov@REDACTED> wrote:
>> Hello,
>> 
>> The reverse is acceptable if you are using lists:reverse/1 (this is built-in function written in C).
>> 
>> There is an alternative, you can use lists:foldr function to avoid unnecessary reverse operation:
> 
> Which introduces an unnecesary tuple construction and deconstruction
> which may or may not be faster...
> 
> At the end of the day an algorithm is fast enough or not so - you have to
> measure to find out. You should choose the simplest correct algorithm
> that is sufficiently fast.
> 
> Cheers
> 
> /Joe
> 
> 
>> 
>> ```
>> 
>> divide_to_lesser_and_bigger(List, X) ->
>>   lists:foldr(fun(E, Acc) -> lesser_or_bigger(E, X, Acc) end, {[], []}, List).
>> 
>> lesser_and_bigger(E, X, {Lesser, Bigger}) when E < X ->
>>   {[E|Lesser], Bigger};
>> lesser_and_bigger(E, _, {Lesser, Bigger}) ->
>>   {Lesser, [E|Bigger]}.
>> 
>> ```
>> 
>> - Dmitry
>> 
>> 
>> 
>>> On Dec 27, 2015, at 5:38 AM, Andrey Koleshko <ka8725@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
>>> It works well, but I have a question that doesn’t allow to sleep me - is it normal practice to do `reverse` every time when you have an list with opposed direction after a few recursions calls? Is there are other practice to avoid it? Thanks!
>>> ________________
>>> Best Regards,
>>> Andrey Koleshko
>>> ka8725@REDACTED
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>> 
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions