डॉलर के उदाहरण पर "अधिकतम-सबरेरी" की समस्या

सार क्या है?

यह आलेख बताता है कि पिछले 5 वर्षों में डॉलर / रूबल की विनिमय दर में अंतर से आप सबसे अधिक कमाई कर सकते हैं।

रूसी में, समस्या का नाम लगभग किसी सरणी में सबर्रे तत्वों के अधिकतम योग की तरह लगेगा। लेख गणना एल्गोरिथ्म प्रस्तुत करता है, साथ ही साथ इसके काम का परिणाम भी है।

मैं इस पर कैसे आया?

उन्होंने हाल ही में उत्कृष्ट सीएलआरएस पुस्तक ( थॉमस एच। कोरमेन, चार्ल्स ई। लिसेरसन, रोनाल्ड एल। रिवेस्ट और क्लिफोर्ड स्टीन को पढ़ना शुरू किया । अल्गोरिद्म, थर्ड एडिशन का परिचय। )। जैसा कि यह अनुमान लगाना मुश्किल नहीं है, पुस्तक कंप्यूटर विज्ञान के मौलिक ज्ञान को रेखांकित करती है।
पुस्तक का एक भाग इस समस्या को हल करने के लिए एल्गोरिथ्म के कार्यान्वयन का नेतृत्व करता है। ज्ञान को मजबूत करने और अपने स्वयं के हित को संतुष्ट करने के लिए, मैंने पिछले 5 वर्षों में रूबल के खिलाफ डॉलर की विनिमय दर पर डेटा पर इसे लागू करने का फैसला किया।

समस्या का सार

जैसा कि पिछले 5 वर्षों में ग्राफ से देखा जा सकता है, डॉलर बहुत बदल गया है। और यह मान लेना उचित होगा कि सुनिश्चित करने के लिए सबसे अच्छा सौदा एक न्यूनतम न्यूनतम पर खरीदना और बाद के स्थानीय अधिकतम पर बेचना होगा (जो कभी-कभी "आंख से" का पता लगाना इतना आसान नहीं होता)।



आइए इस कथन की जाँच करें।

निर्णय

सबसे सरल समाधान "हेड-ऑन जाना" होगा और सबरेज़ के सभी संयोजनों के योगों को खोजने के लिए इसे खोजें और अधिकतम खोजने के लिए उनकी तुलना करें, लेकिन यह समाधान ओ (एन ^ 2) समय को बहुत अच्छी तरह से नहीं लेगा, क्योंकि विश्वास है कि आप इसे कर सकते हैं अधिक इष्टतम।

समाधान के द्वारा, हम इनपुट सरणी को बीच में से 2 सबट्रेसेस में विभाजित करेंगे और प्रत्येक और भागों में अधिकतम योग और साथ ही उनके प्रतिच्छेदन पर देखेंगे। इस प्रक्रिया के लिए O (n lg n) की आवश्यकता होगी, जो काफी प्रभावी है।

एक उदाहरण लिखते हैं:

हम प्रारूप में एक .csv फ़ाइल में www.oanda.com/currency/historical-rates से डेटा प्राप्त करेंगे
"2011-10-02","32.1914",,,,
"2011-10-01","32.0809",,,,
"2011-09-30","31.9086",,,,
"2011-09-29","31.7294",,,,
"2011-09-28","32.0421",,,,
"2011-09-27","32.2233",,,,
"2011-09-26","32.0980",,,,
"2011-09-25","32.0673",,,,
...


अगला, हमें डेटा पढ़ने और इसे तैयार करने की आवश्यकता है:

  courses = [] reader = csv.reader(open('data.csv', 'rb'), delimiter=',', quotechar='"') prev = 0 for row in reader: #   cur = float(row[1]) #         if prev == 0: prev = cur #    value = [row[0], prev - cur, row[1]] prev = cur courses.insert(0, value) 

फ़ाइल में डेटा समय के संबंध में रिवर्स ऑर्डर में है, इसलिए इसे उलटा डालें। डेटा प्रोसेसिंग के दौरान, हम पिछले - वर्तमान दैनिक पाठ्यक्रम में अंतर खोजते हैं। हमारा काम इन अंतरों की अधिकतम मात्रा का पता लगाना होगा।

 def find_max_subarray(a, low, high): #   if high == low: return low, high, a[low][1] else: #   2  mid = (low + high) / 2 #     left_low, left_high, left_sum = find_max_subarray(a, low, mid) #     right_low, right_high, right_sum = find_max_subarray(a, mid + 1, high) # - cross_low, cross_high, cross_sum = find_crossing(a, low, mid, high) if (left_sum >= right_sum) & (left_sum >= cross_sum): return left_low, left_high, left_sum elif (right_sum >= left_sum) & (right_sum >= cross_sum): return right_low, right_high, right_sum else: return cross_low, cross_high, cross_sum 

और क्रॉस-अधिकतम खोज फ़ंक्शन (मध्य-मध्य-विभाजन से गुजरना)।

 def find_crossing(a, low, mid, high): max_left = 0 max_right = 0 left_sum = -1e308 sum = 0 #    for i in range(mid, low, -1): sum = sum + a[i][1] if sum > left_sum: left_sum = sum max_left = i max_right = 0 right_sum = -1e308 sum = 0 #    for j in range(mid + 1, high): sum = sum + a[j][1] if sum > right_sum: right_sum = sum max_right = j return max_left, max_right, left_sum + right_sum 

ठीक है, हमें वह परिणाम मिलता है जो हमें रुचता है

 min, max, sum = find_max_subarray(courses, 0, len(courses)-1) print courses[min] print courses[max] print sum 

नतीजतन, मुझे मिल गया

['2008-07-16', 0.07420000000000115, '23.1269']
['2009-02-05', 0.12059999999999604, '36.1257']
13.1194


और थोड़ा खेल, 2011 की निचली तारीख को स्थानांतरित करना

['2011-05-05', 0.006199999999999761, '27.2657']
['2011-09-26', 0.12530000000000285, '32.0980']
4.9576


सभी कोड gist.github.com/1257729 पर देखे जा सकते हैं

आपका ध्यान के लिए धन्यवाद!