How to speed up nested loops in python?

Question

I have read that we can use map function to speed up for loops. But, in my code I have nested loops and I was wondering if there is anyway to speed up my code using map function or any other method.

import copy as cpy
import time

def powerset(s):
    set =[]
    x = len(s)
    for i in range(1 << x):
         set.append([s[j] for j in range(x) if (i & (1 << j))])
    return set

def func1(Num):

    Num_set = range(1, Num + 1)
    A = []
    for i in range(1, Num + 1):
        my_set = cpy.deepcopy(Num_set)
        my_set.remove(i)
        my_subset = list(powerset(my_set))

        for j in range(0, len(my_subset)):
            name = "{r}:{s}".format(r=i, s=list(my_subset[j]))
            A.append(name)
    return A

start = time.time()
N = 10
A = func1(N)
end = time.time()
print("Run time:{t}".format(t=end - start))

The runtime of above code for N=10 is:

Run time:0.0383169651031

But the runtime for N=20 is around two minutes:

Run time:101.803981066

Any idea for speeding up the nested loop in function func1?

What this code does: Consider a number N =3. Function func1, first creates a list Num_set=[1,2,3]. Then for each element of this list say i, it generates all non-empty subsets of set(Num_set without i). For example if i=2, it adds "2,[]","2,[1]","2,[3]","2,[1,3]" to list A.

Many thanks!

"I have read that we can use map function to speed up for loops." Only in some cases and generally only marginally... Your problem here is inherently your algorithm — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Apr 19, 2018 at 1:11
the way to speed up loops in Python, is not to run those loops in Python! By that I mean let a compiled library do the heavy lifting... — Mitch Wheat
– Mitch Wheat, Commented Apr 19, 2018 at 1:12
@juanpa.arrivillaga So, it is problem specific and there is not a general way that can be used for all problems? — user491626
– user491626, Commented Apr 19, 2018 at 1:13
What are you doing? Why are you computing the powerset of 1 to (A-1), (A+1) to N for every A in 1 to N? — Dan D.
– Dan D., Commented Apr 19, 2018 at 1:15
@MitchWheat likely not going to help here, just judging by the names of the functions, this is calculating powersets, which will take exponential time. — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Apr 19, 2018 at 1:16

Dan D. · Accepted Answer · 2018-04-19 01:23:28Z

1

Well, you could at least improve the parts that can:

for i in range(1, Num + 1):
    my_set = cpy.deepcopy(Num_set)
    my_set.remove(i)
    my_subset = list(powerset(my_set))

    for j in range(0, len(my_subset)):
        name = "{r}:{s}".format(r=i, s=list(my_subset[j]))
        A.append(name)

This removes unneeded copying:

for i in range(1, Num + 1):
    # copying and then removing one item is more costly than simply making the list
    my_set = range(1, i) + range(i + 1, Num + 1)

    for s in powerset(my_set):
        name = "{r}:{s}".format(r=i, s=s)
        A.append(name)

answered Apr 19, 2018 at 1:23

Dan D.

75k15 gold badges111 silver badges129 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to speed up nested loops in python?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related