On Mon, May 18, 2015 at 1:23 PM, Mario Figueiredo <mar...@gmail.com> wrote: > I'd like to understand what I'm being told about slices in > https://wiki.python.org/moin/TimeComplexity > > Particularly, what's a 'del slice' and a 'set slice' and whether this > information pertains to both CPython 2.7 and 3.4.
"Del Slice" is the operation where a slice of a list is deleted, and "Set Slice" is the operation where a slice is replaced. E.g.: >>> x = list(range(100)) >>> del x[2:98] >>> x [0, 1, 98, 99] >>> x[1:3] = [7, 6, 5, 4, 3] >>> x [0, 7, 6, 5, 4, 3, 99] > Other languages implement slices. I'm currently being faced with a Go > snippet that mirrors the exact code above and it does run in linear > time. > > Is there any reason why Python 3.4 implementation of slices cannot be > a near constant operation? The semantics are different. IIRC, a slice in Go is just a view of some underlying array; if you change the array (or some other slice of it), the change will be reflected in the slice. A slice of a list in Python, OTOH, constructs a completely independent list. It may be possible that lists in CPython could be made to share their internal arrays with other lists on a copy-on-write basis, which could allow slicing to be O(1) as long as neither list is modified while the array is being shared. I expect this would be a substantial piece of work, and I don't know if it's something that anybody has looked into. -- https://mail.python.org/mailman/listinfo/python-list
