On May 18, 2015 9:26 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. > > From the above link it seems slices work in linear time on all cases. > And this really has a big impact on certain operations. For instance, > the code below may surprise some people when they realize it doesn't > run in linear time on 3.4: > > def minimum(values): > if len(values) == 1: > return values[0] > else: > m = minimum(values[1:]) > return m if m < values[0] else values[0] > > 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?
In this case you are copying the items (or rather pointers to the items) from the list to a new list. This is inherently a O(k) operation. There are other ways to implement it. I recall the was talk of a way to get views of sequences, although this would involve keeping the original list in memory and any changes to the new list would be passed to the original (this is how numpy works) . It is also possible to do copy-on-write, which avoids altering the original list but has the same memory problems while still involving a O(k) copy operation if you want to change the list, and it is more complex to implement (this is how MATLAB works) . But to have a new list that can be edited independently requires coping something, and that will be a O(k) operation, unless you use a radically different data structure with its own limitations.
-- https://mail.python.org/mailman/listinfo/python-list
