[Python-ideas] Re: Make list.reverse() more flexible
a while ago on this list, we had a bit of discussion about having a sequence view. It started with my more focused idea for a built in slice iterator, which I wrote up some time ago here: https://github.com/PythonCHB/islice-pep Then an even more expansive idea of a general purpose View was proposed. The conversation eventually petered out. Frankly, I didn't see a lot of use-cases at the time -- but now it seems that we have some more, and some more interest. For my part, I think a general purpose View object is far more compelling than adding add-hoc functionality to various methods. For example, he's the OP's suggestion with view semantics: view(a_list)[a_slice].reverse() Pretty nifty! See the discussion for why adding a method to the Sequence ABC is problematic: it could potentially clash with folks' existing methods for non-built-in sequences -- for instance, numpy arrays already have a .view method, and it has a different meaning (or at least necessarily different semantics). So a "view" builtin and maybe a new dunder may be the way to go. Anyway, perhaps it's time to revive the conversation. Here's the old thread --Please look that over before starting a new discussion! https://mail.python.org/archives/list/python-ideas@python.org/thread/QVTGZD6USSC34D4IJG76UPKZRXBBB4MM/#JCFTPY7U2T3QZGWRG7K4LOJ3XBIYRVZZ -CHB On Sun, Mar 7, 2021 at 5:04 AM Vincent Cheong wrote: > Interesting. Just to comment, Mr. Mertz is realistic in the algorithmic > sense. Running time is highly affected by various factors. For example, > lets just assume that an insertion sort of O(N^2) time on a quantum > computer is fast enough for all kinds of task in the world. So, naturally, > there should be no problem and we should instead focus on other projects > rather than making an O(N log N) sort for the quantum machine as its > unnecessary. But, you're N^2, it won't change the fact that you're > algorithmically inefficient. You, on the other hand, are realistic in the > developmental sense. Why spend time on this instead of other things, right? > I believe in 'depends-on-situation' and a balance between thinking about > project and about algorithm, because without this project we wouldn't even > be here, likewise without the algorithm we wouldn't reach here. > > This is for discussions-sake and should have no bearing on the main idea. > > Thanks for the input. > ___ > 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/4PDBVLJPWU2B4XIGIC7IY4PYMSTTYXOP/ > Code of Conduct: http://python.org/psf/codeofconduct/ > -- Christopher Barker, PhD (Chris) Python Language Consulting - Teaching - Scientific Software Development - Desktop GUI and Web Development - wxPython, numpy, scipy, Cython ___ 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/OFXY5HTQH4OGK7I3ZMI6J5JZJMPK52PS/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Basic toolkit for async iterators
Apologies if this has already been raised at some point, but I wanted to raise the idea of a basic standard library toolkit for operations on async iterators. This would include versions of functions that are already in the standard library for non-async iterators, such as *map*, *filter*,*zip *etc. It could also include a *merge* function for async iterators, for example (this would yield items in whatever order they are yielded from from the constituent iterators). There are, of course, open source libraries providing these functions. But in general there is far too wide a range of such libraries, and it is difficult to tell which ones are best maintained. For the most basic and universally useful of operations on async iterators, it would be far better if they were part of the standard library. ___ 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/JAVMCP75ZQO5JMC2LDSCL24BOYJ7K5ZX/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Make list.reverse() more flexible
Interesting. Just to comment, Mr. Mertz is realistic in the algorithmic sense. Running time is highly affected by various factors. For example, lets just assume that an insertion sort of O(N^2) time on a quantum computer is fast enough for all kinds of task in the world. So, naturally, there should be no problem and we should instead focus on other projects rather than making an O(N log N) sort for the quantum machine as its unnecessary. But, you're N^2, it won't change the fact that you're algorithmically inefficient. You, on the other hand, are realistic in the developmental sense. Why spend time on this instead of other things, right? I believe in 'depends-on-situation' and a balance between thinking about project and about algorithm, because without this project we wouldn't even be here, likewise without the algorithm we wouldn't reach here. This is for discussions-sake and should have no bearing on the main idea. Thanks for the input. ___ 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/4PDBVLJPWU2B4XIGIC7IY4PYMSTTYXOP/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Make list.reverse() more flexible
Indeed, it's not directly related, perhaps misunderstanding, but I'm just drawing the similar idea between the two situations of not taking memory first. If you slice, you make a copy and that takes space. So, the space complexity is no longer O(1). It's just that, not that it has any direct relation to map() function. Perhaps a generator is a better analogy to use in the first place because a generator does not make a whole list first, it does not take up as much space upon creation. Thanks for the feedback. ___ 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/YWAX5T5EUXT4LFOPEQDA5IVSKXHYT3UV/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Make list.reverse() more flexible
Insightful! You mentioned terms like 'memory_view', and 'lazy slice'. You felt the pulse of the situation. But the most elegant thing (I had it a long time ago but you brought it up before, haha) is that you notice the downside of copies - you indicated how a lazy slice is the magic wand that eliminates the problem. I have thought of making slices 'lazy' as a solution which conveniently and smoothly avoids the need for a 'start' and 'stop' parameter, but I could not bring myself to float that idea up here because I already had a hunch that it is, simply said, too much to ask for, too bizarre to talk about. A slice that acts a 'view' rather than a 'copy' shares the same lazy idea as like generators yielding items only when needed and map() returns an 'slim' iterator rather than a 'bulky' list. It's like a slogan that says: 'Do only if necessary'. It gives the flexibility of what to do with the slice, not always taking up memory first. That would be intelligent, in a way. Thanks for the input! ___ 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/B4ZYSPQNN4S3OJ5YBAUX7D6IW3HZKSX7/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Make list.reverse() more flexible
06.03.21 09:52, Vincent Cheong пише: > I see. I do agree that my reply brings about that 'verbose repeated' feeling, > haha. But for the record, it's not about having something in hand now for the > future, but it's more of a paradigmatic approach to the implementation. > Python has changed for the better in terms of necessity: > > - map() returns an iterator instead of a whole list at once > - generator yields values only when needed (unlike list comprehension) > > So I thought, 'Why do we need to make a reversed copy to assign it to the > original part, when we can simply reverse the original part itself.' That's > the paradigm. Your proposition is not related to changes in map() and other builtins which return now an iterator instead of list. It is more similar to idea of adding parameters start and stop to map(), so it could be appplied to a part of the list. More general approach would allow you to write a[i:j] = a[i:j][::-1] and it would be a zero-overhead operation because slices are lazy or because the compiler recognize the pattern and generate the optimal code. But it requires a sophisticate compiler. Less sophisticate approach is using an explicit wrapper for lazy slices: a[i:j] = view(a)[i:j][::-1] ___ 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/P4BJYONTRZWSC7YWFLAFVOG35FQOQNV2/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Make list.reverse() more flexible
On Fri, Mar 5, 2021 at 3:23 PM Steven D'Aprano wrote: > On Fri, Mar 05, 2021 at 04:27:27PM -, Vincent Cheong wrote: > > > Currently, list.reverse() only works for an entire list. If one wants > > to reverse a section of it 'in-place', one needs to slicing which > > makes the space complexity no longer O(1). > > The space complexity of a list is not constant, O(1). > > The lists [] and [1]*10 do not take the same amount of space. > > I think that, perhaps, you are trying to say that reversing a list > requires no additional storage and can be done in place. > For what it's worth, that is exactly what it means for the space complexity to be constant. Space complexity of an algorithm refers to the additional storage needed to execute that algorithm, on top of the space used by the input. And so list.reverse() is O(1) in space and O(n) in time, if you hold pointer/index sizes to be O(1). (This is a big "if", and reverse is more accurately O(log n) in space, because pointers/indexes into a sequence of size n are O(log n) if you let n grow arbitrarily large.) I don't know good reading for this, maybe https://en.wikipedia.org/wiki/DSPACE#Machine_models or https://en.wikipedia.org/wiki/In-place_algorithm - What about sorting? > This is a good question! In fact most operations you might want to do with a list, you might want to do with a sub-list. There's even a bunch of methods that take start/stop already, even while there's others that don't, and no good rule of thumb for which methods have them and which don't. For example, list.index() takes optional start/stop, but list.remove() and list.count() don't. It even changes between types: bytes.count *does* support start/stop (as does str.count), even though this is not required of Sequence or even of ByteString. Speaking of which, ByteString.index() didn't have start/stop until 3.5, and... Ad-hoc start/stop parameters are annoying, but honestly it seems like the inconsistency shouldn't and doesn't block adding new start/stop parameters, since the inconsistency is already there, (Other languages that focus on avoiding copying find it more useful to use a vocabulary type that represents a sub-list -- for example, std::span in C++, &[T] in Rust, or []T in Go. (The closest thing in Python that I'm aware of is memoryview.) Once you have that kind of lazy slice, you don't need index start/stop parameters for any particular method, and the whole problem mostly vanishes in a poof of smoke.) -- Devin ___ 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/JJJH6XAAEML7WE7MAYL64KODYN2OAWG3/ Code of Conduct: http://python.org/psf/codeofconduct/