尝试优化我的复数函数以在多项式时间内执行 [英] Trying to optimize my complex function to excute in a polynomial time

问题描述

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

I have this code that generate all the 2**40 possible binary numbers, and from this binary numbers, i will try to get all the vectors that match my objectif function conditions which is: 1- each vector in the matrix must have 20 of ones(1). 2- the sum of s = s + (the index of one +1)* the rank of the one must equal 4970.

我写了这段代码，但是要花费很多时间才能得出结果.现在，我正在寻找一种替代方法，或者在可能的情况下对此代码进行优化.

i wrote this code but it will take a lot of time maybe months, to give the results. Now, i am looking for an alternative way or an optimization of this code if possible.

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]))

推荐答案

尽管您可以在

While you could make a lot of improvements in readability and make your code more pythonic.

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

I recommend that you use numpy which is the fastest way of working with matrixes. Avoid working with matrixes on a "pixel by pixel" loop. With numpy you can make those calculations faster and with all the data at once. Also numpy has support for generating matrixes really fast. I think that you could make a random [0,1] matrix in less lines of code and quite faster. Also i recommend that you install OPENBLAS, ATLAS and LAPACK which make linear algebra calculations quite faster.

希望对您有帮助.

这篇关于尝试优化我的复数函数以在多项式时间内执行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！