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

[Joe Armstrong]

On Mon, Dec 28, 2015 at 12:56 AM, Dmitry Kolesnikov
<dmkolesnikov@REDACTED> wrote:
> 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.
>

Excellent - always measure things

> Here is the visualized results of benchmark and code.

> 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.

As an additional exercise you should measure and compare with lists:sort

Using list comprehensions for sorting is mainly for "showing off" -
it's very short and
elegant code but not efficient.

lists:sort special cases sorting short lists and has explicit
knowledge of the list
ordering so it knows if the lists is in normal or reversed order and
makes use of this
to speed things up.

I might also add that in almost 30 years of Erlang programming I have never
had to rewrite code because reversing or sorting lists was too slow.

The most usual place to find performance bottleneck has always been getting
data from the outside world into Erlang - this usually involves some
form of parsing
which involves looking at every character - once you've got you data into lists
the rest is usually very quick - getting the data into and out of
lists from the outside world is slow.

Cheers

/Joe




>
> 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
>
>