I'm a mathematician. I'm wrote a small function to help me with calcluations that would be otherwise impossible to do by hand. There is a problem though: there are 7 nested loops that make it execute in minutes even for very small inputs.
The problem is the 2 deepest loops looks like this:
for i in N:
for j in N:
if int(a[j]) == i+1:
x.append(str(j+1))
continue
and:
for j in b:
i = int(j) - 1
x.append(a[i])
I have no idea what to use to optimize this. I heard I'm supposed to replace loops with library functions that execute their code in C...
I will explain what the function does.
The functions takes (v,n), where v is a vector of permutations from the symetric group S_n. They are in string form, like this: "1234" - neutral element, "2134" = (12), etc. I don't care what form they are in, I can make them be a list of integers.
The function then takes each pair of elements (a,b) from the vector and tries to generate the group S_n. It outputs how many elements were generated by each pair.
The function tries to generate S_n by:
looping through all possible pairs of vectors (v,w) containing 0 and 1 of length range(d).
(in the first vector 0 means a, 1 means b)
(in the second vector 0 means nothing, 1 means reverse function)
inside the loop it combines (denoted with *) multiple copies of a and b in accordance with the 2 vectors. For example: v = [0,0,1] and w = [0,1,0] produces a * a^-1 * b.
for k in range(d):
w.append(0)
v.append(0)
for i in range(2**(k+1)):
for j in range(2**(k+1)):
x.add(compSet(a,b,v,w,k+1)) # <- combines a and b according to (v,w)
w[0] += 1
for l in range(k+1):
if w[l] > 1:
w[l] = 0
w[l+1] += 1
v[0] += 1
for l in range(k+1):
if v[l] > 1:
v[l] = 0
v[l+1] += 1
I saw a video that showed it's thousands of times faster to use built-in numpy functions than for loops. I also found some complicated threads on 'how to make python run C code'.
Do you know how to optimize this function?
**Edit 2 XI 2021**
Newest code updated with all of the suggestions:
from functools import lru_cache
from itertools import permutations
from itertools import product
import time
import math
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)
@lru_cache
def compSelf(a:tuple,i:int):
if i==1: #a^-1
return tuple(x+1 for x in sorted(range(len(a)),key=a.__getitem__)) # This statement might be wrong.
if i==0: #a^1
return a
raise ValueError("comp: i ==",i,"instead of 0 or 1")
@lru_cache
def compPair(a:tuple,b:tuple):
return tuple(a[i-1] for i in b)
def compSet(a:tuple,b:tuple,v:list,w:list,k:int):
#k = legth of v and w
u = []
for i in range(k):
if w[i] == 0:
u.append(compSelf(a,v[i]))
else:
u.append(compSelf(b,v[i]))
x = compPair(u[k-2],u[k-1])
for i in range(k):
x = compPair(u[k - 1 - i],x)
return x
@lru_cache
def compMass(a:tuple,b:tuple,depth:int):
x = set()
e = tuple(range(1,len(b)+1))
x.add(e)
for k in range(1,depth):
v = [p for p in product([0, 1], repeat=k)]
for i in range(2**(k)):
for j in range(2**(k)):
x.add(compSet(a,b,v[i],v[j],k))
return x
def is_gen(a:tuple,b:tuple,depth:int):
return len(compMass(a,b,depth))
def is_genMass(x:list,depth:int,is_check:bool,is_clear_out:bool):
#tests all pairs in 'x' whether they generate S_n
m = len(x)
n = len(x[0])
n_factorial = math.factorial(n)
out = [[0]*m for _ in range(m)]
count = 0
max_count = 0
if is_check == True:
for i in range(m):
for j in range(m):
out[i][j] = is_gen(x[i],x[j],depth)
is_wait_for_user = False
for i in range(m):
for j in range(m):
is_divided = False
for k in range(2,n+1):
if n_factorial % out[i][j] == 0:
is_divided = True
if not is_divided:
print(tup2str(x[i]),"and",tup2str(x[j]),"don't generate a correct subgroup. Size: " + str(out[i][j]))
is_wait_for_user = True
if out[i][j] != out[j][i]:
raise Exception("is_genMass: elements ",tup2str(x[i])," and ",tup2str(x[i])," generated unequal subgroups of size ",str(out[i][j])," and ",str(out[j][i]))
if is_wait_for_user and n > 4:
input('Input to continue. ')
else:
for i in range(m):
for j in range(i,m):
out[i][j] = is_gen(x[i],x[j],depth)
if is_clear_out:
print("Non-generating pairs:")
for i in range(m):
print("--------------------")
for j in range(i,m):
if out[i][j] != n_factorial:
max_count += 1
if x[i] == x[j]:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]))
else:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]) + " and " + tup2str(x[j]))
print("Generating pairs:")
for i in range(m):
print("--------------------")
for j in range(i,m):
if out[i][j] == n_factorial:
count += 1
max_count += 1
if x[i] == x[j]:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]))
else:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]) + " and " + tup2str(x[j]))
else:
print("Non-generating pairs:")
for i in range(m):
for j in range(i,m):
if out[i][j] != n_factorial:
max_count += 1
if x[i] == x[j]:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]))
else:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]) + " and " + tup2str(x[j]))
print("Generating pairs:")
for i in range(m):
for j in range(i,m):
if out[i][j] == n_factorial:
count += 1
max_count += 1
if x[i] == x[j]:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]))
else:
print(str(out[i][j]) + "/" + str(n_factorial) + " " + tup2str(x[i]) + " and " + tup2str(x[j]))
probability = count / max_count
print("Probability: " + str(count) + "/" + str(max_count) + " = " + str(probability))
def is_genMass_Self(x:list,depth:int,is_print:bool): #todo
#tests all pairs of the same element in 'x' whether they generate S_n
m = len(x)
out = []
for i in range(m):
out.append(is_gen(x[i],x[i],depth,is_print))
if is_print == False:
print("Generating pairs:")
for i in range(m):
if out[i][0] == True:
print(out[i][1] + " " + str(x[i]) + " and " + str(x[i]))
print("Non-generating pairs:")
for i in range(m):
if out[i][0] == False:
print(out[i][1] + " " + str(x[i]) + " and " + str(x[i]))
print("WARNING: This function might be wrong.")
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)
def gen_permutations(n:int):
return sorted([tuple(p) for p in permutations(range(1, n+1))])
n = 5
depth = 5
print(tuplist2strlist(gen_longest_cycles(n)))
x = time.perf_counter()
is_genMass(gen_longest_cycles(n),depth,True,True)
x = time.perf_counter() - x
print("Time:",str(x))