पायथन

Question

में सेगमेंट पेड़ कार्यान्वयन segment tree का उपयोग कर this समस्या को हल कर रहा हूं लेकिन मुझे समय सीमा त्रुटि मिलती है। नीचे न्यूनतम क्वेरी के लिए मेरा कच्चा कोड है और मेरे कोड में min से max बदलकर उपरोक्त समस्या हल हो सकती है। मुझे नहीं पता कि मैं अपने कोड के प्रदर्शन में सुधार कैसे कर सकता हूं। क्या आप इसके प्रदर्शन के मुद्दों के साथ मेरी मदद कर सकते हैं?

t = [None] * 2 * 7  # n is length of list 


def build(a, v, start, end): 
    ''' 
    A recursive function that constructs Segment Tree for list a. 
    v is the starting node 
    start and end are the index of array 
    ''' 

    n = len(a) 
    if start == end: 
     t[v] = a[start] 
    else: 
     mid = (start + end)/2 
     build(a, v * 2, start, mid)  # v*2 is left child of parent v 
     # v*2+1 is the right child of parent v 
     build(a, v * 2 + 1, mid + 1, end) 
     t[v] = min(t[2 * v], t[2 * v + 1]) 
    return t 

print build([18, 17, 13, 19, 15, 11, 20], 1, 0, 6) 

inf = 10**9 + 7 


def range_minimum_query(node, segx, segy, qx, qy): 
    ''' 
    returns the minimum number in range(qx,qy) 
    segx and segy represent the segment index 

    ''' 
    if qx > segy or qy < segx:  # query out of range 
     return inf 
    elif segx >= qx and segy <= qy: # query range inside segment range 
     return t[node] 
    else: 
     return min(range_minimum_query(node * 2, segx, (segx + segy)/2, qx, qy), range_minimum_query(node * 2 + 1, ((segx + segy)/2) + 1, segy, qx, qy)) 

print range_minimum_query(1, 1, 7, 1, 3) 

# returns 13 

क्या इसे इसे लागू किया जा सकता है?

Answer 1

भाषा के विकल्प

सबसे पहले, आप शायद कक्षा की विद्यार्थी अगर आप पारित कभी नहीं होगा पायथन का प्रयोग करें। यदि आप यहां पिछले सभी समाधानों की स्थिति देखते हैं, http://www.spoj.com/status/GSS1/start=0, आप देखेंगे कि हर लगभग स्वीकृत समाधान सी ++ में लिखा गया है। मुझे नहीं लगता कि आपके पास सी ++ का उपयोग करने के अलावा कोई विकल्प है। ध्यान दें कि समय सीमा 0.115s-0.230s है। यह "केवल-के-सी/सी ++" समय सीमा है। उन समस्याओं के लिए जो अन्य भाषाओं में समाधान स्वीकार करेंगे, समय सीमा एक "गोल" संख्या होगी जैसे 1 सेकंड। पाइथन इस प्रकार के पर्यावरण में सी ++ की तुलना में लगभग 2-4x धीमी है।

सेगमेंट ट्री कार्यान्वयन मुद्दे ...?

दूसरा, मुझे यकीन नहीं है कि आपका कोड वास्तव में सेगमेंट पेड़ का निर्माण कर रहा है या नहीं। विशेष रूप से, मुझे समझ नहीं आता क्यों इस लाइन है:

t[v]=min(t[2*v],t[2*v+1]) 

मैं यकीन है कि एक खंड पेड़ दुकानों में एक नोड अपने बच्चों का योग है, तो आपके कार्यान्वयन सही करने के लिए करीब है, तो, मैं यह लगता है बजाय पढ़ना चाहिए

t[v] = t[2*v] + t[2*v+1] 

यदि आपका कोड "सही" है, तो मैं सवाल होगा कि कैसे आप रेंज [x_i, y_i] भीतर अधिक से अधिक अंतराल राशि पा रहे हैं यदि आप भी अंतराल रकम की दुकान नहीं है।

Iterative सेगमेंट ट्री

तीसरा, एक खंड पेड़ iteratively लागू किया जा सकता। यहां C++: http://codeforces.com/blog/entry/18051 में एक ट्यूटोरियल है।

सेगमेंट पेड़ इस बात के लिए काफी तेजी से होना चाहिए नहीं है ...

अंत में, मुझे समझ नहीं आता कि कैसे एक खंड पेड़ इस समस्या के लिए मदद करने के लिए जा रहा है। एक सेगमेंट पेड़ आपको log(n) में किसी श्रेणी की राशि से पूछताछ करने देता है। यह समस्या किसी भी सीमा के अधिकतम संभव योग के लिए पूछती है। मैंने एक सेगमेंट पेड़ के बारे में नहीं सुना है जो "न्यूनतम सीमा सीमा" या "अधिकतम क्वेरी को रेंज" की अनुमति देता है।"

एक निष्क्रिय समाधान ओ (एन^3) होगा (सभी एन^2 संभव प्रारंभ और अंत बिंदुओं को आजमाएं और ओ (एन) संचालन में योग की गणना करें) 1 क्वेरी के लिए। और, यदि आप सेगमेंट पेड़ का उपयोग करते हैं , आप ओ (एन) के बजाय ओ (लॉग (एन)) में योग प्राप्त कर सकते हैं। यह केवल आपको ओ (एन^2 लॉग (एन)) तक गति देता है, जो एन = 50000 के लिए काम नहीं कर सकता है।

वैकल्पिक एल्गोरिथ्म

मैं तो आप इसके बजाए, जो हे (एन) क्वेरी के साथ में चलता है पर विचार करना चाहिए:। http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ सी/C++ यह लिखें और के रूप में एक टिप्पणीकार सुझाव आईओ के साथ कुशल हो

Answer 2

आप जेनरेटर के साथ प्रयास कर सकते हैं क्योंकि आप कई सीमाओं के आसपास जा सकते हैं। हालांकि आपने एक डेटासेट प्रदान नहीं किया जो आपके प्रदर्शन को स्पष्ट रूप से दिखाता है - क्या आप एक समस्याग्रस्त डेटासेट प्रदान कर सकते हैं?

यहाँ आप कोशिश कर सकते हैं:

t=[None]*2*7 
inf=10**9+7 

def build_generator(a, v, start, end): 
    n = len(a) 

    if start == end: 
     t[v] = a[start] 
    else: 
     mid = (start + end)/2 
     next(build_generator(a, v * 2, start, mid)) 
     next(build_generator(a, v * 2 + 1, mid + 1, end)) 
     t[v] = min(t[2 * v], t[2 * v + 1]) 
    yield t 



def range_minimum_query_generator(node,segx,segy,qx,qy): 
    if qx > segy or qy < segx: 
     yield inf 
    elif segx >= qx and segy <= qy: 
     yield t[node] 
    else: 
     min_ = min(
      next(range_minimum_query_generator(node*2,segx,(segx+segy)/2,qx,qy)), 
      next(range_minimum_query_generator(node*2+1,((segx+segy)/2)+1,segy,qx,qy)) 
     ) 
     yield min_ 

next(build_generator([18,17,13,19,15,11,20],1,0,6)) 
value = next(range_minimum_query_generator(1, 1, 7, 1, 3)) 
print(value) 

संपादित

वास्तव में है कि अपने मुद्दों को ठीक नहीं कर सकते। एक और तरीका है (के रूप में जनरेटर पर अपने ट्यूटोरियल में डी Beazley द्वारा वर्णित - timecode 2h00 चारों ओर https://www.youtube.com/watch?v=D1twn9kLmYg&t=9588s) किसी भी प्रत्यावर्तन सीमा वैकल्पिक हल के लिए नहीं है