On 5/18/2015 5:04 PM, Mario Figueiredo wrote:
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.
This is what I was after. Thank you Ian.
So we basically don't have a view of a list.
Actually we do if you think about things the right way. An index can be
viewed as representing the slice of a list from the indexed item to the
end. In this view, "for i in range(len(seq)):" works with progressively
shrinking slices, the same as with the recursive version of the algorithm.
The analogy is better with iterators. iter(seq) returns a seq_iterator
that initially represent a tail slice consisting of the entire sequence.
Each next(seq_iter) call return the head of the sequence and mutates
seq_iter to represent a reduced tail-slice. The effect is the same as
repeatedly stripping the head from a linked list. For statements
automate the next calls and StopIteration checks.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
