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ł. > On 12 Jul 2016, at 22:19, Wiebe-Marten Wijnja <[email protected]> > wrote: > > 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 > > On Thursday, July 7, 2016 at 4:24:52 PM UTC+2, Wiebe-Marten Wijnja wrote: > 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 <https://github.com/Qqwy/elixir_benchmark_list_swap>. > > 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 > > -- > 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 [email protected] > <mailto:[email protected]>. > To view this discussion on the web visit > https://groups.google.com/d/msgid/elixir-lang-core/72111b12-90fe-46a4-be51-3883d1ec84fb%40googlegroups.com > > <https://groups.google.com/d/msgid/elixir-lang-core/72111b12-90fe-46a4-be51-3883d1ec84fb%40googlegroups.com?utm_medium=email&utm_source=footer>. > For more options, visit https://groups.google.com/d/optout > <https://groups.google.com/d/optout>. -- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/6512868B-2D05-4D32-A5C9-C7B0E9F8A4FD%40muskala.eu. For more options, visit https://groups.google.com/d/optout.
signature.asc
Description: Message signed with OpenPGP using GPGMail
