r/pythonhelp • • Nov 11 '21

How to speed up 7 nested loops?

4 Upvotes

22 comments sorted by

1

u/IncognitoErgoCvm Nov 11 '21

Unfortunately, I don't understand what your code is trying to accomplish well enough to help directly.

I believe you are looking for vectorization. Hopefully that will get you going in the right direction.

1

u/13ass13ass Nov 11 '21

The variables I and j in comp mass function don’t seem to do anything. Are you certain they are necessary? That has big O of 2n so anything you can do there to speed it up will have huge gains.

Look into using cprofiler too to find bottlenecks/“hot” loops

1

u/CraigAT Nov 11 '21

I did some maths at degree level but it being completely out of practise it's difficult to figure out what is going on.

I did find this which looks to be similar and uses a Python module SciPy which may be helpful.

https://stackoverflow.com/questions/52155783/permutation-of-symmetric-array-in-python

1

u/Goobyalus Nov 11 '21

I don't fully understand the goal, and I haven't spent that much time looking at the code, but from what I see so far, the code uses resources creating data structures that it iterates over once and discards. These can be left as generators.

You should probably not use strings to represent numbers.

1

u/Goobyalus Nov 11 '21

/u/PerfectSpeling

For example, on the initial part, your two functions can be replaced with:

def gen_longest_cycles(n:int):
    z = set()

    for p in permutations(range(1, n+1)):
        z.add(tuple(p[(k+1)%n] for j in range(n) for k in range(n) if p[k] == j + 1))

    return sorted(z)

which halves the time gen_longest_cycles takes to execute, and uses tuples of integers intead of strings.

1

u/xelf Nov 11 '21

Here's a start:

replace this:

def gen_longest_cycles_decomposed(n:int):
    z = []
    y = []

    for i in range(n):
        z.append(str(i+1))

    x = list(permutations(z,n))

    for i in range(len(x)):
        y.append(''.join(x[i]))

    return y

with this:

def gen_longest_cycles_decomposed(n:int):    
    return [''.join(x) for x in permutations(map(str,range(1,n+1)),n)]

1

u/xelf Nov 11 '21 edited Nov 12 '21

Do you think you could add some documentation as to what each function is supposed to do. I was able to reverse engineer one of them so far, but some of the others are getting really hard to decipher what you wanted to do.

like this function:

def compSelf(a:str,i:int):

return the 1-based-indexes for the sorted values in the string?

so 4234 returns 2314 ? I mean that's what it does, just not sure if that's what it's supposed to do or why.

I think you can replace it with this:

def compSelf(a:str,i:int):
    if i==1:
        return ''.join(str(x+1) for x in sorted(range(len(a)),key=a.__getitem__))
    if i==0:
        return a
    raise ValueError("comp: i == ",i," instead of 0 or 1")

How about compPair? Return the digits from the first string using the indexes from the second string?

def compPair(a:str,b:str):
    if len(a) == len(b):
        return ''.join(a[int(i)-1] for i in b)
    raise ValueError("a and b not equal length")

All around, I think you would be better off not using strings or 1-based-indexes until your final output/display as using strings and 1-based indexes adds a LOT of intermediary conversions that are slowing you down.

Still not sure what compSet is supposed to do, but this code replaces the code you had and yields the same results, but faster:

from functools import reduce
def rcompPair(a,b): return compPair(b,a)
def compSet(a:str,b:str,v:list,w:list,k:int):
    u = [ compSelf((a,b)[w[i]!=0],v[i]) for i in range(k-1,-1,-1)]
    return reduce(rcompPair, [compPair(u[1],u[0])]+u)

1

u/[deleted] Nov 12 '21

[removed] — view removed comment

1

u/xelf Nov 13 '21

That's really in depth, and to be honest a lot to take in. I've rewritten a bunch of the functions, and I'm working on compMass right now.

This function is the core of the whole file, and at the same time the hardest to explain.

Ah. Great. =D

1

u/Goobyalus Nov 15 '21

Do you have your equations written out in mathematical notation? It would be much easier to go straight from that to code.

1

u/[deleted] Nov 17 '21

[removed] — view removed comment

1

u/Goobyalus Nov 17 '21

Im wondering if you can write this out on paper or in LaTeX or something because I am struggling to parse the formatting of this and the previous message

1

u/[deleted] Nov 13 '21

[removed] — view removed comment

1

u/xelf Nov 13 '21 edited Nov 13 '21

I'd assumed that the k value would always match the length of v/w, it looks like that is not the case, I'll have to tweak it.

This is what I'm using now, and it seems to pass all the unit tests.

def compPair(a,b):
    return tuple(a[i-1] for i in b)
def rcompPair(a,b):
    return tuple(b[i-1] for i in a)
def compSet(a,b,v,w,k):
    u = [compSelf((a,b)[w[i]!=0],v[i]) for i in range(k)]
    return reduce(rcompPair, [compPair(u[k-2],u[k-1])]+u[::-1])

I also added some helper functions for final conversions:

def tup2str(tup):
    try:
        return ''.join(map(str,tup))
    except:
        print('tup2str error', tup)
def tuplist2strlist(tups):
    try:
        return [tup2str(x) for x in tups]
    except:
        print('tuplist2strlist error', tups)

Doing all the math as tuples of ints now, and only swapping to strings when needed to compare output to your functions. Everything is much faster.

1

u/throwaway8u3sH0 Nov 14 '21

You could try caching results. (It's kind of a hacky way to do it.)

At the top of the file: from functools import lru_cache

Then, above any method that does NOT use a list as input: @lru_cache

Example:

@lru_cache
def compSelf(a:str,i:int):
    if i == 0: #a^1
    .
    .
    .

This saves the most recent 128 calls to that method, so if you call it again with identical arguments, it'll return from cache instead of doing all the work again.

Adding that to the various functions cuts the time by about a factor of 8 on my machine -- it seems like you're repeating a lot of work.

But the better way is probably to use numpy to do the calculations in parallel, if that's possible. (I haven't looked in detail at the underlying math.)

1

u/[deleted] Nov 20 '21

[removed] — view removed comment

1

u/throwaway8u3sH0 Nov 20 '21

No problem. Two bits of info that might help:

  • If you find that you really want to cache a function that takes in a list, you can switch the input to a tuple. (Just surround the list with tuple() before passing it in). For technical reasons Python can't cache the former. You can switch it back to a list inside the function if needed.

  • Cached functions should be "pure" -- the return depends only on the inputs (no global variables or randomness or reading from a website or whatever) and they have no side effects (like printing or writing to a file or changing global state). A common tactic is to break up functions into the "pure" and "impure" parts, so that the pure parts can be cached.

Good luck!

1

u/skellious Nov 11 '21

i highly recommend you use numpy. it allows you to execute operations arraywise, so instead of a loop you do the operation on all the array elements simultaneously.

it handles all the multithreding and such for you, and also putting operations into C.

reimplementation with numpy will fix your time issue.

https://numpy.org/

alternatively, or indeed additionally, you can use numba to JIT your functions.

https://numba.pydata.org/