My draft implementation <https://github.com/s3cur3/elixir-xutil/blob/main/lib/x_util/list.ex> (and the associated @doc and test suite <https://github.com/s3cur3/elixir-xutil/blob/main/test/list_test.exs>) has been updated to match the range semantics of Enum.slice/2. Among other things, that means it has support for negative indices.
I thiiiiiiiink this represents a minimal shippable version of a list-only implementation (assuming we're okay with the name, and we're okay with making it list-only for the time being). I'd love to get some feedback on what the next steps should be. 🙏 -- Tyler Young On Sunday, September 5, 2021 at 7:38:19 PM UTC-6 Tyler Young wrote: > In the draft implementation on my GitHub > <https://github.com/s3cur3/elixir-xutil/blob/main/lib/x_util/list.ex>, > I've: > > 1. Changed the implementation to the recursive version (thanks José!). > After a bunch of benchmarking and tweaking, this is the fastest version I > could come up with on a range of sizes from 16 to 16,384. The recursive > one > is between 2 and 6% faster at worst; it's something like 40% faster at > best. (Happy to supply the benchmarking code if folks are interested.) > 2. Implemented the single-element move suggested by Zach Daniel > > > I've not yet added support for negative indices, but it's on my list. > > Re: naming, I think I agree that slide is a more intuitive name; the only > thing I'd say in favor of rotate is that it appears to be the more common > name for algorithms that look vaguely like this in other languages. In > terms of prior art, I haven't been able to find any languages that call it > slide. (That could be a failing of my search skills, though!) > > Re: supporting any enumerable, my reasoning for proposing it on List > rather Enum was specifically to avoid folks confusedly trying to index into > Map and MapSet. It'd be easy enough to provide one (ever-so-slightly > faster) specialization for lists and one for other enumerables, though. > > Re: streams, I don't know much about streams in Elixir, but I could take a > crack at implementing it. > > -- > Tyler Young > > > On Sat, Sep 4, 2021 at 6:22 PM Zach Daniel <[email protected]> wrote: > >> >> Fwiw, “slide” sounds like a much more intuitive name than rotate, to me. >> Rotate sounds like a 2d matrix operation (often commonly done on lists). >> Additionally, we should probably support a range *or* an index as the >> second argument, since moving one thing is still useful, and would be a >> good first example in the docs. >> On Saturday, September 4, 2021 at 2:04:31 PM UTC-4 José Valim wrote: >> >>> Well, for a stream you are still traversing everything, then I guess it >>> makes sense to be linear. I guess the benefit is not having to allocate a >>> new data structure. Once again we will need two algorithms, depending if >>> the end is before or after start. If before, you need to accumulate until >>> you find the slice, then you emit the slice, emit the accumulator, and then >>> continue as usual. If after, you need to emit everything, until start, then >>> accumulate the slice, and emit everything as necessary. So both operations >>> will require you to buffer, the amount of buffered content depends on the >>> end position. >>> >>> On Sat, Sep 4, 2021 at 7:34 PM [email protected] <[email protected]> wrote: >>> >>>> >>>> >>>> On Saturday, September 4, 2021 at 7:21:45 PM UTC+2 José Valim wrote: >>>> >>>>> It could definitely be implemented as a Enum or a Stream function, but >>>>> the level of complexity is definitely much higher, and reduce would force >>>>> the implementation to be linear anyway. So I am honestly not sure if it >>>>> is >>>>> worth it. >>>>> >>>> >>>> The main part of the algorithm could be written using a couple of calls >>>> to `Enum(erable).slice`. In this case, at least as long as the number of >>>> elements to be moved is small, the implementation is faster than linear >>>> (for types that support faster than linear slicing). >>>> >>>> That is, until we concatenate the results at the end to form the >>>> rotated list. So at most it is an efficiency improvement of a constant >>>> factor, but the result will still be linear. >>>> Hmm... >>>> >>>> -- >>>> >>> 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/d54e1e48-a32c-4d9c-8307-d5cb7926050cn%40googlegroups.com >>>> >>>> <https://groups.google.com/d/msgid/elixir-lang-core/d54e1e48-a32c-4d9c-8307-d5cb7926050cn%40googlegroups.com?utm_medium=email&utm_source=footer> >>>> . >>>> >>> -- >> > You received this message because you are subscribed to a topic in the >> Google Groups "elixir-lang-core" group. >> To unsubscribe from this topic, visit >> https://groups.google.com/d/topic/elixir-lang-core/LYmkUopaWN4/unsubscribe >> . >> To unsubscribe from this group and all its topics, send an email to >> [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/elixir-lang-core/8903e169-dadc-48bf-98ea-f860f1bc0891n%40googlegroups.com >> >> <https://groups.google.com/d/msgid/elixir-lang-core/8903e169-dadc-48bf-98ea-f860f1bc0891n%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> > -- 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/dff0982d-3d24-4279-a013-e7f08fb2e5cdn%40googlegroups.com.
