On Fri, Mar 5, 2021 at 3:23 PM Steven D'Aprano <st...@pearwood.info> wrote:
> On Fri, Mar 05, 2021 at 04:27:27PM -0000, 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]*100000 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<T> 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/
