Skipping iterations in a ForLoop to reduce time complexity

Question

Let's suppose I have a list of 1000 values, however, I am not interested in values between 111 and 889. Is there a way in python to entirely skip iterations of a for loop without using continue to reduce time complexity? It seems like a waste to run the for loop 1000 times when I only need to run it 222 times.

l = [1,2,3,111,5,6,7,8,9,889,12,2,111,4,5,6,889]
for i in l:
    if i == 111:
        // skip to 889
    else:
        // do stuff

There could be multiple occurrences of 111 and 889 in this list and all the values in between should be skipped. If there is no 889 after 111 the for loop should end

Does this answer your question? [Scope of python variable in for loop](https://stackoverflow.com/questions/15363138/scope-of-python-variable-in-for-loop) — OmG, Apr 21 '20 at 14:20
This is a totally different question to the one you asked before, you have to anyway traverse the list once then maybe second time you can improve time complexity. — Albin Paul, Apr 21 '20 at 14:29
is there a pattern for the occurance of 111 and 889 in your list? — Albin Paul, Apr 21 '20 at 14:30
@OmOWalker then the first time you iterate you need to traverse it entirely, second time you can used the indexes of 111 and 889 to skip using the while loop. — Albin Paul, Apr 21 '20 at 14:33
Yeah I was just wondering if there's a way to skip the initial traverse — OmO Walker, Apr 21 '20 at 14:36

Erich · Answer 1 · 2020-04-21T14:29:31.363

1

You can use a while loop.

idx = 0
while idx < 1000:
    if idx == 111:
        idx = 889
    else:
        # do stuff
        idx += 1

For your edited question, I'm afraid there is no better way than traversing the whole list by using continue since you don't know where the 889 appears in the list.

edited Apr 21 '20 at 14:29

answered Apr 21 '20 at 14:17

Erich

1,838
16
20

Sorry for confusion I fixed the question – OmO Walker Apr 21 '20 at 14:27

score 1 · Answer 2 · answered Apr 21 '20 at 14:29

You can create two slices of your iterable then chain them together to iterate through them:

import itertools as it

my_list = list(range(1000))
my_slice1 = it.islice(my_list, 0, 111)
my_slice2 = it.islice(my_list, 889, 1000)
new_iterable = it.chain(my_slice1, my_slice2)
for i in new_iterable:
    print(i)

Rushikesh · Answer 3 · 2020-04-21T14:54:46.767

You changed the question totally in between, One thing you should notice that if you have unsorted list of length, no matter whatever you do, O(n) is the best case scenario.

If list has some pattern or derived from formula, or is periodic, there might exist some minor optimization.

You can optimize little bit by using libraries like numpy, you can get good optimization only in case your input array is also numpy array, else use itertools, filter etc if you are only going with list

# with numpy
import numpy
a = numpy.array([1,2,3,111,5,6,7,8,9,889,12,2,111,4,5,6,889])
filter_array = a[numpy.logical_or(a < 111, a >889)]

#with filter
l = [1,2,3,111,5,6,7,8,9,889,12,2,111,4,5,6,889]
filter_list_gen = filter(lambda x : x > 889 or x < 111, l)
for l in filter_list_gen:
    #  do the stuff
    pass

Numpy perfect for array manupulation, you will need to run loop, plus numpy filtering loop, but it will help you have many array manupulation overall
filter id just like normal iterating, but little faster, its like lazy eval.

Skipping iterations in a ForLoop to reduce time complexity

3 Answers3