On Sat, Mar 6, 2021 at 7:07 AM David Mertz <me...@gnosis.cx> wrote: > This sounds like a very verbose repeated statement that "there may be a > use in the future." That's definitely not going to get a feature, no matter > how many times repeated. > > If this is something you actually need, write a subclass of list in Cython > or C, and add that capability. I cannot think of a time I would have used > it in the last 23 years, but maybe someone would. Put it on PyPI and > explain why it helps something. > > On Sat, Mar 6, 2021, 1:42 AM Vincent Cheong <vincentcheong6...@gmail.com> > wrote: > >> Sorry for not explaining the background of my idea. I'm involved in the >> research area of sorting algorithms. Reversals are part of sorting and >> correct me if wrong, `list.reverse()` is the fastest method to reverse an >> entire list, which is also in-place. Yet, it doesn't work for a subsection >> of it. > > The key thing is that it's very, very unlikely "research area of sorting algorithms" is going to beat Timsort.
But maybe it is. Or maybe it is for some specialized kind of data collections that tend to come with some characteristic ascending or descending runs. Even assuming that is true, and some new algorithm is good for a specific case, it's not going to be especially fast once implemented in Python, even with the hypothetical "in-place reverse of a slice". Maybe it would be faster in C or another low-level language, but not on top of the Python interpreter. So this "research" is inherently doomed to fail.... UNLESS, you do the research not by actual raw timings, but rather in the sensible way of profiling the specific number of operations in an abstracted way. For that, existing "reversal of slice" techniques are perfectly fine to profile algorithms, but with things like internal counters of operations, not as actual machine timings. I was, however, a little curious, so timed a few related things: >>> a = list(range(1_000_000)) >>> %timeit a.reverse() 450 µs ± 16 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) >>> %timeit list(reversed(a)) 7.38 ms ± 149 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) >>> %timeit a[:] = a[-1:0:-1] 14.1 ms ± 230 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) >>> %timeit a[500_000:550_000] = a[550_000-1:500_000-1:-1] 240 µs ± 1.77 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) So indeed, list(reversed()) is more than 15x slower than list.reverse(). And assigning from a reverse slice is slower still by about 2x. However, assuming you only want to reverse a moderate amount in the middle of a large list, the time remains pretty moderate. In my example, 1/2 the time of reversing the entire list. Other than subclassing list per se, you could also write a Cython or C extension that merely provided extra operations on actual lists. Maybe call it `listtools` in the spirit of `itertools` and `functools`. Some external function like `reverse_middle(a, 500_000, 550_000)` isn't a terrible thing to experiment with. And in concept, that could be as fast as is theoretically possible.
_______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/2XEG3YIPKSARXBH3ZIVZJGYKWI6QEDYD/ Code of Conduct: http://python.org/psf/codeofconduct/
