python:大規模データの計算速度を最速にしたい

Question

##やりたいこと
学校から出された問題で、
以下の問題の条件を満たすための計算速度を底上げしたい

問題：以下の問に答えよ
2以上7以下の互いに素な素数が3つ存在している
それら3つの素数の累乗積を小さい順に並べよ
そして指定番号の数字を表示せよ

「但し、順に並べた数字は1000個目まで考慮し、
実行時間は16.0s未満とする」

例）素数　2 3 7
数列上で8番目の数字

203070=1
213070=2
203170=3
223070=4
213170=6
203071=7
233070=8
20327****0=9
8番目の数字は9

これの1000番目の数字を時間内に求めたい

##環境
jupyter6.0.0
python3.7.4
##やったこと
考え方として、累乗の数を変化させるのではなく3つの素数のうちどれかで割り切れるか、を素数1個1個で試す形にしました。
理由としては累乗の数を増減させた場合、以下の事故が起きる可能性が出てくると考えたからです
例）上記の霊でまず累乗を0から1まで絞る->出てくる数字　1 2 3 6 14 21 42
次に累乗を1から2まで試す->出てくる数字 4 9 12 .. =>先に出た数字よりも小さいものが出てきてしまう為
数字の順がめちゃくちゃになる

よって以下のソースコードで
素数 2 3 5
指定番号　750番目
にすると実行時間　43.425915002822876
になりました

import time

def warizan(cur,sosu):
#割り切れなくなるまで割り算を行う
    while(True):
        if cur%sosu==0:
            cur=cur/sosu
        else:
            break
    return int(cur)


    
def while_math(a,sosu_list):
#数字の末尾が偶数かどうかや全ての桁の数字を足して3で割れるかどうかを試している
    cur=a
    pre_result=str(cur)
    matubi=int(pre_result[len(pre_result)-1])
    
    if 2 in sosu_list :
        if matubi%2==0:
            cur=warizan(cur,2)
    
    if 3 in sosu_list:
        pre_result=[int(x) for x in  str(cur)]
        _all=sum(pre_result)
        if _all%3==0:
            cur=warizan(cur,3)
        
    if 5 in sosu_list :
        if matubi%5==0:
            cur =warizan(cur,5)
                  
    if 7 in sosu_list:
        cur=warizan(cur,7)
    if cur==1:
        return a
    else :return 0

#---ここまでで関数定義

input_math=input()
math_list=list(input_math.split(" "))
sosu_list=[]

[sosu_list.append(int(math_list[i])) for i in range(0,3)]
result_idx=int(math_list[3])
sosu_list.sort()
result_list=[]
a=1
start=time.time()
while(True):
    if len(result_list)>=result_idx:
        break
    result=while_math(a,sosu_list)
    if result!=0:
        result_list.append(result)
    a+=1
end=time.time()-start
#print(result_list)
#[print(result_list[i]) for i in range(0,100)]
print("経過時間",end)
print(result_list[result_idx-1])
    

恐らくもっと良い計算方法があると思うのですが、これが限界でした
どうかよろしくお願いします

Answer 1

累乗積は最低限各素数を0～9乗まで組み合わせれば1000個は求まります。
ただし、それらだけで小さい順から1000個得られるとは限りません。

そこで、以下を順番に求めます。

まず0～9乗までの結果をソートして先頭1000個を得ます（結果A）。
同様に0～(9+1)乗までの分を求めます（結果B）。
結果AとBの1000個が一致すれば求めたい1000個が得られたと考えられます。
一致しなければ0～(9+2)乗の分を求めていき、前回0～(9+1)乗の分と比較していきます。

以上を繰り返すと[2,3,5]で27乗、[2,3,7]で29乗で一致するので、その先頭1000個から任意の位置の値を得ることができます。
itertoolsを使えば29乗まで求めても1秒もかかりません。

Comments

[zenobread]

ご回答ありがとうございます。
お話がおよそ理解できたと思うので一度やってみます。

[zenobread]

なぜか質問内容を編集できなかった為此方にコードを書かせていただきます。
仰られた通りの計算にすると正しい計算が出来たと思われるのですが、実行時間が10秒を超えてしまいました。何か改善点はありますでしょうか。
また、調べてcache_sys関数という名前で計算結果をキャッシュしようとしたのですが、jupyterのメモリ上限を超えてしまいました。お時間があればこちらの問題についてもcan110さんの所見を伺いたいと思います。

---以下コード

import time
import copy

def cache_sys(func):
#計算結果をdictionaryで保存
cache={}
def inner(*args):
if args not in cache:
cache[args]=warizan(*args)
return cache[args]
return inner

#@cache_sys
def warizan(a,b,c):
return a*b*c

input_math=input()
math_list=list(input_math.split(" "))
sosu_list=[]
#235の場合2は3と1差であるから2乗で追い抜く、2は5と3差であるから3乗で追い抜く
#257
[sosu_list.append(int(math_list[i])) for i in range(0,3)]
result=int(math_list[3])
result_idx=9+1
sosu_list.sort()
result_list=[]
result_list2=[]
start=time.time()
end_bool=False

while(True):
if time.time()-start>16.0:
print("規定時間を超えました",time.time()-start)
break
end_bool=False
if len(result_list)==0:
for a in range(0,result_idx):
for b in range(0,result_idx):
for c in range(0,result_idx):
result_list.append(warizan(sosu_list[0]**a,sosu_list[1]**b,sosu_list[2]**c))
result_list.sort()
result_idx+=1

if len(result_list2)==0:
for a in range(0,result_idx):
for b in range(0,result_idx):
for c in range(0,result_idx):
result_list2.append(warizan(sosu_list[0]**a,sosu_list[1]**b,sosu_list[2]**c))
result_list2.sort()
#print(result_list,result_list2)
for idx in range(0,result-1):
# print(idx)
if result_list[idx]!=result_list2[idx]:
end_bool=True
result_list=copy.copy(result_list2)
result_list2.clear()
break
else:
continue
if end_bool==True:
continue

end=time.time()-start
print(end)
print(len(result_list))
print(result_list.index(81716054175))
#[print(result_list[i]) for i in range(0,1000)]

[can110]

累乗の組み合わせを多重for文でおこなっているようですが、おそらくitertools.productを使うと速くなります。

[zenobread]

実行できました、ありがとうございます。最後にもう一点だけ,jupyterのkernelが落ちたのはdictionaryに割くメモリが不足したからでしょうか

[can110]

cache_sys関数の動作は把握できていないので何とも云えませんが、その可能性はあると思います。
ただ、今回の処理でいえば、キャッシュすべきは前回の累乗和の先頭1000個分だけでよいです。
たとえば９乗まで計算した結果1000個(A)をキャッシュしておき10乗の累乗和を求めて先頭1000個(B)を得ます。AとBが不一致なら A=Bに代入して11乗分を計算するような流れでよいはずです。

[zenobread]

遅くなりました。理解致しました。長い間お付き合いいただきありがとうございます。