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: > > 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]. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/cb7fa47e-97f1-4144-93d5-a87ec452dc69%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
