मैं एमआईटी ओपन कोर्स वेयर quizes में से कुछ के माध्यम से पढ़ रहा है और वे एक सवाल है कि इस तरह से चला जाता है था:इन 2 कार्यों के बीच गति अंतर इतना बड़ा क्यों है?
6) दो कार्यों नीचे निर्दिष्ट है कि एक "लगता है कि एक नंबर खेल खेलने के लिए उपयोग किया जाता है पर विचार करें। "
def cmpGuess(guess):
"""Assumes that guess is an integer in range(maxVal). returns -1 if guess is < than the magic number, 0 if it is equal to the magic number and 1 if it is greater than the magic number."""
def findNumber(maxVal):
"""Assumes that maxVal is a positive integer. Returns a number, num, such that cmpGuess(num) == 0."""
Write a Python implementation of findNumber that guesses the magic number defined by cmpGuess. Your program should have the lowest time complexity possible. """
यहाँ मेरी कार्यान्वयन है:
def find(maxVal):
ceiling = maxVal
floor = 0
while 1:
med = ((ceiling + floor)/2)
res = cmp(med)
if res == 1:
ceiling = med
elif res == -1:
floor = med
else:
return med
और यहाँ उत्तर पुस्तिका कार्यान्वयन जनसंपर्क है शिक्षक द्वारा ovided:
def findNumber(maxVal):
""" Assumes that maxVal is a positive integer. Returns a number, num, such that cmpGuess(num) == 0 """
s = range(0, maxVal)
return bsearch(s, 0, len(s) -1)
def bsearch(s, first, last):
if (last-first) < 2:
if cmp(s[first]) == 0:
return first
else:
return last
mid = first + (last -first)/2
if cmp(s[mid]) == 0:
return s[mid]
if cmp(s[mid]) == -1:
return bsearch(s, first, mid -1)
return bsearch(s, mid + 1, last)
यह सीएमपी हमारे दोनों कार्यों द्वारा इस्तेमाल किया समारोह है, कल्पना के अनुसार:
def cmp(guess):
if guess > num:
return 1
elif guess < num:
return -1
else: return 0
एक प्रमुख अंतर यह है कि मेरी समाधान पुनरावृत्ति है और शिक्षक की कि पुनरावर्ती है । मैंने अधिकतम कार्यों = 1000,000 के साथ हमारे दोनों कार्यों के 1000 रन का समय दिया। यहाँ समय का टुकड़ा है:
t = timeit.Timer('find(1000000)', 'from __main__ import find,cmp')
t1 = timeit.Timer('findNumber(1000000)', 'from __main__ import findNumber,bsearch')
print str(t.timeit(1000))
print str(t1.timeit(1000))
मेरे रन ले लिया: 0.000621605333677s चलाने शिक्षकों ले लिया: 29.627s
यह संभवतः सही नहीं हो सकता। मैंने लगातार कई बार समय दिया, और सभी मामलों में दूसरा समारोह हास्यास्पद 30 के परिणामों के साथ आया। मैंने एमआईटी द्वारा प्रदान किए गए दस्तावेज़ से सीधे समाधान फ़ंक्शन चिपकाया। कोई विचार?
पहला प्रश्न (मुझे लगता है कि आपने पहले इसे चेक किया है, लेकिन आइए सुनिश्चित करें): क्या दोनों सही उत्तर देते हैं? जैसा कह रहा है: यदि इसे सही नहीं होना है, तो मैं इसे 0 के रूप में कम कर सकता हूं। – delnan
's = रेंज (0, maxVal)' ??? शिक्षक के समाधान के लिए 'ओ (अधिकतम) 'स्पेस की आवश्यकता होती है। – Bolo
हाँ, दोनों सही हैं, एक दूसरे के मुकाबले धीमी गति के आदेश हैं। – Steve