试图优化我的复杂函数以在多项式时间内执行

Question

我有这段代码来生成所有 2**40 个可能的二进制数，从这个二进制数中，我将尝试获取与我的 objectif 函数条件匹配的所有向量，即： 1-矩阵中的每个向量必须有20个1(1(。 2-s = s + (the index of one +1)* the rank of the one之和必须等于4970。

我写了这段代码，但需要很多时间，也许几个月，才能给出结果。现在，如果可能的话，我正在寻找另一种方法或优化此代码。

import time
from multiprocessing import Process
from multiprocessing import Pool
import numpy as np
import itertools
import numpy
CC = 20
#test if there is 20 numbers of 1
def test1numebers(v,x=1,x_l=CC):
c = 0
for i in range(len(v)):
if(v[i]==x):
c+=1
if c == x_l:
return True
else:
return False
#s = s+ the nth of 1 * (index+1)        
def objectif_function(v,x=1):
s = 0
for i in range(len(v)):
if(v[i]==x):
s = s+((i+1)*nthi(v,i))
return s
#calculate  the nth of 1 in a vecteur
def nthi(v,i):
c = 0
for j in range(0,i+1):
if(v[j] == 1):
c+=1
return c
#generate 2**40 of all possible binray numbers  
def generateMatrix(N):
l = itertools.product([0, 1], repeat=N)
return l
#function that get the number of valide vector that match our objectif function 
def main_algo(N=40,S=4970):
#N = 40
m = generateMatrix(N)
#S = 4970
c = 0
ii = 0
for i in m:
ii+=1
print("n count:",ii)
xx = i
if(test1numebers(xx)):
if(objectif_function(xx)==S):
c+=1
print('found one')
print('n',xx,'n')
if ii>=1000000:
break
t_end = time.time()     
print('time taken for 10**6 is: ',t_end-t_start)
print(c)            
#main_algo()
if __name__ == '__main__':
'''p = Process(target=main_algo, args=(40,4970,))
p.start()
p.join()'''
p = Pool(150)
print(p.map(main_algo, [40,4970]))

Answer 1

虽然你可以在可读性方面做很多改进，让你的代码更pythonic。

我建议您使用 numpy，这是处理矩阵的最快方法。 避免在"逐像素"循环中使用矩阵。使用 numpy，您可以更快地进行这些计算，并一次处理所有数据。 此外，numpy 还支持非常快速地生成矩阵。我认为你可以用更少的代码行和更快的速度制作一个随机的 [0,1] 矩阵。 另外，我建议您安装OPENBLAS，ATLAS和LAPACK，它们使线性代数计算速度相当快。

我希望这对你有所帮助。