List.swap

[Wiebe-Marten Wijnja]

I recently was in need of swapping the values at two positions in a list.

Of course, linked lists are not the best data type to use when you have to swap elements a lot, but I believe that it is a rather common problem that you have a list, and you need to swap the positions of two elements.

As implementing an efficient version of this function is not trivial, I tried a couple of approaches, and wanted to share the results here.

I think it might be useful to add this functionality to the List module.

I've benchmarked four different solutions; 

1. The naïve approach of using Enum.fetch! and List.replace_at. This runs in O(4n) and as could be seen from the benchmarks, it is rather slow.

2. An approach using maps and Enum.with_index and a for-comprehension to transform a list into an index-keyed map on which the replacements are in O(log n). Of course, the three transformation steps make this function more expensive (so time complexity is something like O(3n+3log(n)). In the benchmark this was the slowest solution.

3. An approach using plain recursion to build up a map. (I expect that the time complexity is somewhat akin O(2n+3log(n)) ) This is slightly faster than (2) but still slower than the final solution.

4. An approach where the input list is split at the given indices, and the final result is built back up by taking the heads/tails of these different split segments. I believe this solution to be O(2n), and this is indeed the fastest during my benchmarking.

Of course, my approach is not extremely scientific, so you might want to test this out for yourself. The code including the benchmark setup I used can be found on Github.

This is the source code of the fastest solution:

  def split_swap(list, pos_a, pos_a), do: list 

  def split_swap(list, pos_a, pos_b) when pos_a < pos_b do

    {initial, rest} = Enum.split(list, pos_a)

    {between, tail} = Enum.split(rest, pos_b - pos_a)

    a = hd(between)

    b = hd(tail)

    initial ++ [b] ++ tl(between) ++ [a] ++ tl(tail)

  end

  def split_swap(list, pos_a, pos_b) when pos_b < pos_a, do: split_swap(list, pos_b, pos_a)

Is it a good idea to add this as a function called e.g. `swap` to the List module?

Sincerely,

~Wiebe-Marten

[Wiebe-Marten Wijnja]

I really hope that someone will take some time to look at this and write a reply.

Can we add List.swap to the standard library?

~Wiebe-Marten

[Michał Muskała]

Hello,

To be honest I’m not convinced it’s a good idea. The fact that doing this is relatively hard today, shows that the list is probably not the best type to do such things. Making it easy might promote bad data patterns in applications.

Michał.

-- 
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/72111b12-90fe-46a4-be51-3883d1ec84fb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[José Valim]

I really hope that someone will take some time to look at this and write a reply.

I have mentioned this in another thread but the lack of discussion is a feedback itself. It seems very few developers see themselves needing this feature, which means it likely does not justify it being part of the standard library.

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Director of R&D 

[Sergii Boiko]

Hi Wiebe-Marten,

swap operation for lists is quite expensive - O(n). Usually, you would want to have this swap for implementing some kind of algorithm on the whole list. But applying such algorithm for a list will be O(n^2) due to the complexity of swap itself. Thus, I second Michał, it's not a good idea to provide it in stdlib.

Usually, it's just need to be done in a different way.

On Thursday, July 7, 2016 at 4:24:52 PM UTC+2, Wiebe-Marten Wijnja wrote:

[Wiebe-Marten Wijnja]

Thank you very much for your replies.

I have mentioned this in another thread but the lack of discussion is a feedback itself. It seems very few developers see themselves needing this feature, which means it likely does not justify it being part of the standard library.

This is true, lack of discussion is a kind of feedback. However, this type of feedback is very implicit; there are multiple possible reasons for there not to be any discussion. Besides the possibility of the feature being a not-so-useful idea, it might be that the people that often talk about things just weren't online this day, or that my explanation was unhelpfully cryptic, etc.

So therefore I asked if someone would like to explicitly answer the yes/no usefulness question.

To be honest I’m not convinced it’s a good idea. The fact that doing this is relatively hard today, shows that the list is probably not the best type to do such things. Making it easy might promote bad data patterns in applications.

Thank you! This is a very clear argument to not include this function in the standard library. 

I think that the best course of action will be to create a tiny Hex.pm library with this function in it, so people that are in need of it will be able to find it, but it won't promote bad data patterns to people that can opt for a solution that does not involve lists.


Thank you very much for your time and effort, Michał, Jose, and Serggii. :-)

Sincerely,

~Wiebe-Marten

On Thursday, July 7, 2016 at 4:24:52 PM UTC+2, Wiebe-Marten Wijnja wrote: