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 <zachary.s.dan...@gmail.com> 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 w...@resilia.nl <w...@resilia.nl> 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 elixir-lang-co...@googlegroups.com. >>> >> 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 > elixir-lang-core+unsubscr...@googlegroups.com. > 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 elixir-lang-core+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/CAPGekiV41prr7_U0HX_%2B03UDtnRtkAO%2BLf_Wi6PS0srd_E6vAQ%40mail.gmail.com.
