जब डेटा का आकार बहुत बड़ा होता जा रहा है, तो मुझे चलने वाली ग्रिड समस्या से निपटने में समस्या होती है। परियोजना विवरण: एक चींटी (0,0) से (एम, एन) तक चल रही है। हर बार, चींटी उत्तर या पूर्व चलने वाले पथ के साथ समान संभावना के साथ एक इकाई लंबाई तक यात्रा करती है जब तक कि वह (एम, एन) तक नहीं पहुंच जाती। पथ के विचलन डी को अधिकतम (x/my/n, y/nx/m) के रूप में परिभाषित करें पथ के साथ सभी बिंदु (x, y)। मेरा कोड:

import math
D = []
def all_path(x,y,m,n,d):
    temp = abs(x*1.00/m-y*1.00/n)
    if d < temp:
        d = temp
    if x == m-1 and y==n:
        D.append(d)
    elif x == m and y == n-1:
        D.append(d)
    elif x==m  and y<n-1:
        D.append(d)
    elif x<m-1 and y== n:
        D.append(d)
    else:
        all_path(x+1,y,m,n,d)
        all_path(x,y+1,m,n,d)

all_path(0,0,23,31,0)
D_ave = sum(D)/len(D)
#mean
print(round(D_ave,10))
#standard deviation
print(round(math.sqrt(sum([(d-D_ave)*(d-D_ave) for d in D])/len(D)),10))
count_1= 0
count_2 = 0
for d in D:
    if d >0.2:
        count_1+=1
        if d>0.6:
            count_2+=1
#condition propabality
print(round(count_2*1.00/count_1,10))

समस्या: जब m और n 11 और 7 की तरह छोटा है। यह ठीक काम कर रहा है। लेकिन जब m और n 23 और 31 की तरह थोड़े बड़े हो जाते हैं। मेरा कंप्यूटर दिखाता है कि मेमोरी क्षमता पर्याप्त नहीं है। मैं इसे अपने दोस्तों के कंप्यूटर पर चलाने की कोशिश करता हूं जिसमें 32 जी मेमोरी है। यह त्रुटि अभी भी है। क्या समस्या मेरे एल्गोरिदम या कुछ और से आ रही है?

1
user9983709 20 जुलाई 2018, 19:25

2 जवाब

समस्या आपके एल्गोरिदम के साथ है। all_path को कॉल करते समय आप रिकर्सन गहराई लगभग 2 ^ (max(m, n)) तक पहुंचते हैं। अपने मान m = 23 और n = 31 लेते हुए, 2^31 10^9 के क्रम का है। 32 जीबी रैम भी पर्याप्त नहीं हो सकता है क्योंकि आवश्यक मेमोरी 10^9 को स्टैक आकार से गुणा किया जाएगा।

1
yaswanth 20 जुलाई 2018, 19:42

यह समस्या की प्रकृति और आपके द्वारा चुने गए एल्गोरिथम है। अपने छोटे मामलों के लिए D की लंबाई देखें:

 m   n      len(D)
 7, 11       31824
11, 11      705432
12, 12     2704156
13, 13    10400600
14, 14    40116600

समय और स्थान की जटिलताएं प्रत्येक घातीय होती हैं, जिसका आधार स्टैक की गहराई पर 2 और मेमोरी पर 4 होता है। m=n=23 के साथ, D 10^19 फ्लोट्स के क्लोज ऑर्डर पर होगा।

मेरा सुझाव है कि आप गतिशील प्रोग्रामिंग पर गौर करें ताकि आपको यह पता चल सके कि किसी एल्गोरिथम को कैसे रिफलेक्टर किया जाए। साथ ही, चौड़ाई-प्रथम निष्पादन पर स्विच करें: अगले पर जाने से पहले उन सभी परिणामों का मिलान करें जो आपको दिए गए वर्ग में से प्राप्त करते हैं। आप इसे आसानी से एक पंक्ति, स्तंभ, या विकर्ण (चालों की मात्रा) के साथ कर सकते हैं। इस तरह, आपके पास अभी जो 2^max(m,n) है, उसके बजाय आप किसी एक समय में min(m, n) संगणना के समानांतर धागे से अधिक नहीं रख रहे हैं।

1
Prune 20 जुलाई 2018, 19:49