Slices time complexity

[Chris Angelico]

On Thu, May 21, 2015 at 5:51 AM, Mario Figueiredo <marfig at gmail.com> wrote:
> But no one is arguing for that. Instead, it was said that it would be
> interesting if Python offered views.

It's pretty easy, actually. (Slightly more complicated once you handle
more details like negative indexing and strides other than 1, but
still not too hard.)

class View:
    def __init__(self, seq, start=0, end=None):
        self.seq = seq
        self.start = start
        if end is None: self.end = len(seq)
        else: self.end = end
    def __getitem__(self, item):
        if isinstance(item, slice):
            start, end, _ = item.indices(self.end-self.start)
            return View(self.seq, self.start + start, self.start + end)
        if self.start + item >= self.end: raise IndexError
        return self.seq[self.start + item]

Start with any sequence (doesn't have to be a list as such) and
construct a View of it, and then all slicing and dicing happens with
index arithmetic instead of list construction. Indexing of views
transparently works on the underlying sequence, and you can coalesce a
view into a concrete list (eg to allow garbage collection of the
original) with list(v), same as you would with a range object or a
generator or any other iterable.

It's really not that hard.

ChrisA