0

Since the accepted answer for a similar question Efficient iteration over slice in Python does not offer O(1) running time, I am creating a separate question here.

Let's say we have a list l of size n, and a slice of size k << n that starts in a middle (n/2).

It is very trivial to iterate in a for-in loop optimally:

for i in range(n//2,n//2+k)
  #do something with l[i] 
  ...

However my goal is to create an iterator over the slice using standard python tools, so i could use that iterator later on for chaining, filtering, and subslicing using itertools.

Couple standard options are not really good:

iter(l[n//2:n//2+k]) will actually use O(k) extra space for a copy

itertools.islice(l, n//2, n//2+k) will use O(1) space, but O(n) extra running time to reach the slice range.

yurgis
  • 4,017
  • 1
  • 13
  • 22

2 Answers2

2

Write your own:

def turbo_slice(iterable, start, stop, step=1):
    for ii in range(start, stop, step):
        yield iterable[ii]

Or if you prefer:

def turbo_slice(iterable, start, stop, step=1):
    return map(iterable.__getitem__, range(start, stop, step))

Then:

for item in turbo_slice(l, n/2, n/2+k):
    # do something with item

I tested the performance of both implementations, they're about the same (if you must know, the first is 8% faster which surprised me a little).

John Zwinck
  • 239,568
  • 38
  • 324
  • 436
  • Seems too verbose having to define a generator function every time you need it. Feels like should be part of itertools. If there is no really other way of doing it using builtin python modules, i will accept this as an answer – yurgis Apr 19 '20 at 19:42
0

For the record, I am posting this as an improvement on top of the accepted answer. Apparently, there is a more concise way of doing this called generator expressions:

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

The expression above return a generator which can serve as an efficient iterator, and can be combined with itertools.

yurgis
  • 4,017
  • 1
  • 13
  • 22