क्या इस मेमोरी त्रुटि से बचने का कोई तरीका है?

Question

मैं वर्तमान में प्रोजेक्ट यूलर की समस्याओं के माध्यम से काम कर रहा हूं, और अब तक मैं इस समस्या के साथ एक समस्या के लिए आया हूं।

from itertools import combinations 
import time 

def findanums(n): 
    l = [] 
    for i in range(1, n + 1): 
     s = [] 
     for j in range(1, i): 
      if i % j == 0: 
       s.append(j) 
     if sum(s) > i: 
      l.append(i) 
    return l 

start = time.time() #start time 

limit = 28123 

anums = findanums(limit + 1) #abundant numbers (1..limit) 
print "done finding abundants", time.time() - start 

pairs = combinations(anums, 2) 
print "done finding combinations", time.time() - start 

sums = map(lambda x: x[0]+x[1], pairs) 
print "done finding all possible sums", time.time() - start 

print "start main loop" 
answer = 0 
for i in range(1,limit+1): 
    if i not in sums: 
     answer += i 
print "ANSWER:",answer 

मैं एक MemoryError में चलाने जब मैं इस चलाते हैं।

ट्रैस बैक:

File "test.py", line 20, in <module> 
    sums = map(lambda x: x[0]+x[1], pairs) 

मैं मैं क्या गूगल से लेकिन कोई लाभ नहीं हुआ प्राप्त करने में सक्षम किया गया है से कचरा संग्रहण को अक्षम करके यह को रोकने के लिए कोशिश की है। क्या मैं इस गलत तरीके से आ रहा हूं? मेरे सिर में यह ऐसा करने का सबसे स्वाभाविक तरीका है और मुझे इस बिंदु पर नुकसान हुआ है।

साइड नोट: मैं पीपीपी 2.0 बीटा 2 (पायथन 2.7.4) का उपयोग कर रहा हूं क्योंकि यह मेरे द्वारा उपयोग किए जाने वाले किसी अन्य पायथन कार्यान्वयन से बहुत तेज़ है, और सिसि/नम्पी मेरे सिर पर हैं क्योंकि मैं अभी भी कार्यक्रम शुरू करना और मेरे पास इंजीनियरिंग या मजबूत गणित पृष्ठभूमि नहीं है।

Answer 1

जैसा कि केविन ने टिप्पणियों में उल्लेख किया है, आपका एल्गोरिदम गलत हो सकता है, लेकिन फिर भी आपका कोड अनुकूलित नहीं है।

बहुत बड़ी सूची का उपयोग करते हैं, यह एक प्रसिद्ध, महान Stackoverflow जवाब yield की अवधारणाओं और generator समझा है generators उपयोग करने के लिए आम है - What does the "yield" keyword do in Python?

समस्या यह है कि आपके pairs = combinations(anums, 2) एक generator उत्पन्न नहीं करता है , लेकिन एक बड़ी वस्तु उत्पन्न करता है जो अधिक स्मृति उपभोग करता है।

मैं जब से तुम संग्रह इसे केवल एक बार पुनरावृत्ति, इस समारोह के लिए अपने कोड बदल गया है, आप आलसी मूल्यों का मूल्यांकन कर सकते हैं:

def generator_sol(anums1, s): 
     for comb in itertools.combinations(anums1, s): 
     yield comb 

अब pairs = combinations(anums, 2) जो एक बड़ी वस्तु उत्पन्न करने के बजाय। उपयोग:

pairs = generator_sol(anums, 2) 

फिर, lambda उपयोग करने के बजाय मैं एक generator का प्रयोग करेंगे: xrange जो अधिक उपयुक्त है पर

sums_sol = (x[0]+x[1] for x in pairs) 

एक और टिप, तो आप बेहतर देखो, यह एक सूची उत्पन्न doens't लेकिन एक xrange object जो कई मामलों में अधिक कुशल है (जैसे यहां)।

Answer 2

मुद्दा यह है कि एम्स बड़ा है - लगभग 28000 तत्व लंबे हैं। तो जोड़े 28000 * 28000 * 8 बाइट = 6 जीबी होना चाहिए। यदि आप numpy आप एक numpy.int16 सरणी के रूप में anums डाली सकता है, का इस्तेमाल किया जो मामले में परिणाम जोड़े 1.5GB होगा - अधिक प्रबंधनीय:

import numpy as np 
#cast 
anums = np.array([anums],dtype=np.int16) 
#compute the sum of all the pairs via outer product 
pairs = (anums + anums.T).ravel() 

Answer 3

मुझे सुझाव है कि आप generators उपयोग करने के लिए करते हैं। इस बदलने का प्रयास करें:

sums = map(lambda x: x[0]+x[1], pairs) 

sums = (a+b for (a,b) in pairs) 

को Ofiris समाधान भी ठीक है लेकिन संकेत मिलता है कि itertools.combinations एक सूची प्रदान जब यह गलत है। यदि आप प्रोजेक्ट यूलर समस्याओं को हल करने जा रहे हैं तो itertools documentation पर एक नज़र डालें।