Efficient iteration over slice in Python

问题:

How efficient are iterations over slice operations in Python? And if a copy is inevitable with slices, is there an alternative?

I know that a slice operation over a list is O(k), where k is the size of the slice.

x[5 : 5+k]  # O(k) copy operation

However, when iterating over a part of a list, I find that the cleanest (and most Pythonic?) way to do this (without having to resort to indices) is to do:

for elem in x[5 : 5+k]:
  print elem

However my intuition is that this still results in an expensive copy of the sublist, rather than simply iterating over the existing list.

回答1:

You can use itertools.islice to get a sliced iterator from the list:

Example:

>>> from itertools import islice
>>> lis = range(20)
>>> for x in islice(lis, 10, None, 1):
...     print x
...     
10
11
12
13
14
15
16
17
18
19

Update:

As noted by @user2357112 the performance of islice depends on the start point of slice and the size of the iterable, normal slice is going to be fast in almost all cases and should be preferred. Here are some more timing comparisons:

For Huge lists islice is slightly faster or equal to normal slice when the slice's start point is less than half the size of list, for bigger indexes normal slice is the clear winner.

>>> def func(lis, n):
        it = iter(lis)
        for x in islice(it, n, None, 1):pass
...     
>>> def func1(lis, n):
        #it = iter(lis)
        for x in islice(lis, n, None, 1):pass
...     
>>> def func2(lis, n):
        for x in lis[n:]:pass
...     
>>> lis = range(10**6)

>>> n = 100
>>> %timeit func(lis, n)
10 loops, best of 3: 62.1 ms per loop
>>> %timeit func1(lis, n)
1 loops, best of 3: 60.8 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 82.8 ms per loop

>>> n = 1000
>>> %timeit func(lis, n)
10 loops, best of 3: 64.4 ms per loop
>>> %timeit func1(lis, n)
1 loops, best of 3: 60.3 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 85.8 ms per loop

>>> n = 10**4
>>> %timeit func(lis, n)
10 loops, best of 3: 61.4 ms per loop
>>> %timeit func1(lis, n)
10 loops, best of 3: 61 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 80.8 ms per loop


>>> n = (10**6)/2
>>> %timeit func(lis, n)
10 loops, best of 3: 39.2 ms per loop
>>> %timeit func1(lis, n)
10 loops, best of 3: 39.6 ms per loop
>>> %timeit func2(lis, n)
10 loops, best of 3: 41.5 ms per loop

>>> n = (10**6)-1000
>>> %timeit func(lis, n)
100 loops, best of 3: 18.9 ms per loop
>>> %timeit func1(lis, n)
100 loops, best of 3: 18.8 ms per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 50.9 us per loop    #clear winner for large index
>>> %timeit func1(lis, n)

For Small lists normal slice is faster than islice for almost all cases.

>>> lis = range(1000)
>>> n = 100
>>> %timeit func(lis, n)
10000 loops, best of 3: 60.7 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 59.6 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 59.9 us per loop

>>> n = 500
>>> %timeit func(lis, n)
10000 loops, best of 3: 38.4 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 33.9 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 26.6 us per loop

>>> n = 900
>>> %timeit func(lis, n)
10000 loops, best of 3: 20.1 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 17.2 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 11.3 us per loop

Conclusion:

Go for normal slices.

回答2:

Use:

for elem in x[5 : 5+k]:

It's Pythonic! Don't change this until you've profiled your code and determined that this is a bottleneck -- though I doubt you will ever find this to be the main source of a bottleneck.

---

In terms of speed it will probably be your best choice:

In [30]: x = range(100)

In [31]: k = 90

In [32]: %timeit x[5:5+k]
1000000 loops, best of 3: 357 ns per loop

In [35]: %timeit list(IT.islice(x, 5, 5+k))
100000 loops, best of 3: 2.42 us per loop

In [36]: %timeit [x[i] for i in xrange(5, 5+k)]
100000 loops, best of 3: 5.71 us per loop

---

In terms of memory, it is not as bad you might think. x[5: 5+k] is a shallow copy of part of x. So even if the objects in x are large, x[5: 5+k] is creating a new list with k elements which reference the same objects as in x. So you only need extra memory to create a list with k references to pre-existing objects. That probably is not going to be the source of any memory problems.

回答3:

Just traverse the desired indexes, there's no need to create a new slice for this:

for i in xrange(5, 5+k):
    print x[i]

Granted: it looks unpythonic, but it's more efficient than creating a new slice in the sense that no extra memory is wasted. An alternative would be to use an iterator, as demonstrated in @AshwiniChaudhary's answer.

回答4:

You're already doing an O(n) iteration over the slice. In most cases, this will be much more of a concern than the actual creation of the slice, which happens entirely in optimized C. Looping over a slice once you've made it takes over twice as long as making the slice, even if you don't do anything with it:

>>> timeit.timeit('l[50:100]', 'import collections; l=range(150)')
0.46978958638010226
>>> timeit.timeit('for x in slice: pass',
                  'import collections; l=range(150); slice=l[50:100]')
1.2332711270150867

You might try iterating over the indices with xrange, but accounting for the time needed to retrieve the list element, it's slower than slicing. Even if you skip that part, it still doesn't beat slicing:

>>> timeit.timeit('for i in xrange(50, 100): x = l[i]', 'l = range(150)')
4.3081963062022055
>>> timeit.timeit('for i in xrange(50, 100): pass', 'l = range(150)')
1.675838213385532

Do not use itertools.islice for this! It will loop through your list from the start rather than skipping to the values you want with __getitem__. Here's some timing data showing how its performance depends on where the slice starts:

>>> timeit.timeit('next(itertools.islice(l, 9, None))', 'import itertools; l = r
ange(1000000)')
0.5628290558478852
>>> timeit.timeit('next(itertools.islice(l, 999, None))', 'import itertools; l =
 range(1000000)')
6.885294697594759

Here's islice losing to regular slicing:

>>> timeit.timeit('for i in itertools.islice(l, 900, None): pass', 'import itert
ools; l = range(1000)')
8.979957560911316
>>> timeit.timeit('for i in l[900:]: pass', 'import itertools; l = range(1000)')

3.0318417204211983

This is on Python 2.7.5, in case any later versions add list-specific optimizations.

回答5:

I think a better way is using a c-like iteration if the 'k' is so large (as a large 'k' -like 10000000000000- even could make you wait about 10 hours to get answer in a pythonic for loop)

here is what I try to tell you do:

i = 5 ## which is the initial value
f = 5 + k ## which will be the final index

while i < f:
    print(x[i])
    i += 1

I assume this one could do it just in 5 hours (as the pythonic equivalent for loop do it for about 10 hours) for that large k that I told because it need to go from 5 to 10000000000005 just one time! every use of 'range()' of 'xrange()' or even the slicing itself (as yo mentioned above) make the program just do 20000000000000 iterations that could lead to a longer execution time i think. (as I learn using a generator method will return an iterable object that need to run the generator completely first to be made and it takes twice time to do job; One for the generator itself and another for the 'for' loop)

Edited:

In python 3 the generator method/object does not need to run first to make the iterable object for the for loop