Efficient iteration over slice in Python

Question

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.

If you're concerned about copying the slice, I guess the alternative is to iterate over the indices using `range(5, 5 + k)`. — Marius, Aug 04 '13 at 23:37
Danger! You got bad advice earlier; `itertools.islice` doesn't work the way we thought it did. If you use an `islice` starting at 1000000, Python will loop through the first 1000000 elements of your list before yielding anything. This could turn a linear-time algorithm quadratic or worse. — user2357112, Aug 08 '13 at 03:53

score 9 · Answer 1 · answered Aug 04 '13 at 23:55

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.

Ashwini Chaudhary · Accepted Answer · 2013-08-08T07:39:51.077

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.

`itertools.islice` does not work this way! It is built for slicing arbitrary iterables, and it will not attempt to use `__getitem__`. If you try to use an `islice` starting at `1000000`, `islice` will loop through the first `1000000` items of your list before yielding anything, utterly destroying your performance. — user2357112, Aug 08 '13 at 03:41
@user2357112 I've added some timing comparisons, can you explain how can this be **quadratic** or **worse**? Timing results are in favour of `islice`. — Ashwini Chaudhary, Aug 08 '13 at 04:13
Quadratic time would be if you tried to iterate over a large number of small slices of a list from the beginning to the end; your runtime would be quadratic in the number of slices instead of linear in the size of the list. — user2357112, Aug 08 '13 at 04:23
What's `lis`, and what Python version is this? My timing results are the opposite of yours. — user2357112, Aug 08 '13 at 04:23
@user2357112 `lis` is `range(10**6)`. This is IPython shell, py2.7.4. — Ashwini Chaudhary, Aug 08 '13 at 04:32
`islice` can win when the slice is bigger than the part that comes before it, but if `start` is much bigger than `stop - start`, performance tanks. See timing data in my (revised) answer. — user2357112, Aug 08 '13 at 04:39
Look again. Regular slice is taking microseconds. `islice` is taking milliseconds. — user2357112, Aug 08 '13 at 05:46
@user2357112 Duh! facepalm, Guess I need some sleep. BTW, thanks learned something new today. — Ashwini Chaudhary, Aug 08 '13 at 07:35
That is a very good point! Thanks for going through the trouble of checking this :) — WaelJ, Aug 11 '13 at 12:41

Óscar López · Answer 3 · 2013-08-05T00:05:47.307

4

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.

edited Aug 05 '13 at 00:05

answered Aug 04 '13 at 23:38

Óscar López

232,561
37
312
386

Another issue with index based approach is `IndexError`. – Ashwini Chaudhary Aug 04 '13 at 23:44
I believe that for such a simple usage scenario, a simpler answer is the best. Not everything has to be fancy and pythonic, with iterators and slices and comprehensions etc. for those of us that come from a C-like background, sometimes a good old index-based traversal will work just fine – Óscar López Aug 04 '13 at 23:51
3

This is actually the slowest solution. You can try it out with `timeit`. Iterators and slices aren't fancy at all; they're basic, core Python features. – user2357112 Aug 05 '13 at 00:02
@user2357112 well, that's eye-opening! – Óscar López Aug 05 '13 at 00:06

user2357112 · Answer 4 · 2013-08-08T04:39:46.060

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.

score 0 · Answer 5 · answered Apr 24 '20 at 22:16

The accepted answer does not offer an efficient solution. It is in order of n, where n is a slice starting point. If n is large, it is going to be a problem. The followup conclusion ("Go for normal slices") is not ideal either, because it uses extra space in order of k for copying.

Python provides a very elegant and efficient solution to the slicing problem called generator expression that works as optimal as you can get: O(1) space and O(k) running time:

(l[i] for i in range(n,n+k))

It is similar to list comprehension, except that it works lazily and you can combine it with other iterator tools like itertools module or filters. Note the round parenthesis enclosing the expression.

score 0 · Answer 6 · answered Jan 01 '22 at 11:43

For iterating through subarray (for creating subarray see unutbu's answer) slicing is slightly faster than indexing in worst case (l[1:]).

10 items
========
Slicing:  2.570001e-06 s
Indexing: 3.269997e-06 s

100 items
=========
Slicing:  6.820001e-06 s
Indexing: 1.220000e-05 s

1000 items
==========
Slicing:  7.647000e-05 s
Indexing: 1.482100e-04 s

10000 items
===========
Slicing:  2.876200e-04 s
Indexing: 5.270000e-04 s

100000 items
============
Slicing:  3.763300e-03 s
Indexing: 7.731050e-03 s

1000000 items
=============
Slicing:  2.963523e-02 s
Indexing: 4.921381e-02 s

Benchmark code:

def f_slice(l):
    for v in l[1:]:
        _x = v

def f_index(l):
    for i in range(1, len(l)):
        _x = l[i]

from time import perf_counter
def func_time(func, l):
    start = perf_counter()
    func(l)
    return perf_counter()-start

def bench(num_item):
    l = list(range(num_item))
    times = 10
    t_index = t_slice = 0
    for _ in range(times):
        t_slice += func_time(f_slice, l)
        t_index += func_time(f_index, l)
    print(f"Slicing:  {t_slice/times:e} s")
    print(f"Indexing: {t_index/times:e} s")

for i in range(1, 7):
    s = f"{10**i} items"
    print(s)
    print('='*len(s))
    bench(10**i)
    print()

ARF · Answer 7 · 2013-08-05T03:02:55.007

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

This is actually slower! Time it and see. – user2357112 Aug 08 '13 at 04:07 — user2357112, Aug 08 '13 at 04:07

Efficient iteration over slice in Python

7 Answers7

Update:

Conclusion:

Linked