कोडवर्ड काटा - "दोहराव अनुक्रम"
मैं निम्नलिखित कोडवर्ड काटा को हल करने की कोशिश कर रहा हूं ।
हमें
seq = [0, 1, 2, 2] के रूप में एक सूची दी गई है
हमें एक फ़ंक्शन लिखना होगा जो सबसे पहले, निम्नलिखित तर्क का उपयोग करके सूची में तत्वों को जोड़ देगा।
यदि n = 3 और seq [n] = 2 के रूप में, नई सूची seq = [0, 1, 2, 2, 3, 3] होगी
यदि n = 4 और seq [n] = 3 के रूप में, नई सूची होगी seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
अगर n = 5 और seq [n] = 3 के रूप में, नई सूची seq = [0, 1, 2, 2 होगी , 3, 3, 4, 4, 4, 5, 5, 5] इत्यादि।
फिर फ़ंक्शन सूची के n-वें तत्व को वापस करेगा।
सूची के कुछ तत्व:
[0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8 , 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13 , 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17 , 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20 , 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21]
अजगर के लिए बाधा:
0 <= n <= 2 ^ 41
मेरा कोड n = 2 ^ 41 (2.2s के भीतर) सहित n के किसी भी मूल्य के लिए मेरे सिस्टम में सफलतापूर्वक चलता है। लेकिन यह कोडवर्ड में कई बार निकलता है। क्या कोई मेरे कोड को अनुकूलित करने में मेरी मदद कर सकता है? अग्रिम में धन्यवाद।
मेरा कोड:
def find(n):
arr = [0, 1, 2, 2]
if n <= 3:
return arr[n]
else:
arr_sum = 5
for i in range(3, n+1):
arr_sum += i * arr[i]
if arr_sum >= n:
x = (arr_sum - n) // i
return len(arr) + arr[i] - (x+1)
else:
arr += [i] * arr[i]
जवाब
सूची बनाने में बहुत समय लगता है। ध्यान दें कि आपका arr += [i] * arr[i]मूल्य एक ही मूल्य iको बार-बार दोहराता है । इसके repeat(i, arr[i])बजाय केवल भंडारण से यह बहुत संकुचित हो सकता है । यह लगभग 6 सेकंड में सफल होता है, अच्छी तरह से 12 सेकंड की सीमा के तहत:
from itertools import chain, repeat
def find(n):
if n <= 3:
return [0, 1, 2, 2][n]
arr = [[2]]
arr_sum = 5
arr_len = 4
for i, arr_i in enumerate(chain.from_iterable(arr), 3):
arr_sum += i * arr_i
if arr_sum >= n:
x = (arr_sum - n) // i
return arr_len + arr_i - (x+1)
arr.append(repeat(i, arr_i))
arr_len += arr_i
ध्यान दें कि n > 3मामले में, हम पहले ही नंबर 3 से शुरू करते हैं, इसे सूची में दो बार जोड़ते हैं। इस प्रकार अनुक्रम की शुरुआत [0, 1, 2, 2]हमें केवल चाहिए [2], इसलिए मैं शुरू करता हूं arr = [[2]](जो इससे छोटा है [repeat(2, 1)], और chainबुरा नहीं है)।
वैकल्पिक रूप से ... ध्यान दें कि आप arrइसका उपभोग करने की तुलना में बहुत तेजी से बढ़ा रहे हैं। N = 2 41 के लिए , आप इसे 51 मिलियन से अधिक तत्वों तक बढ़ाते हैं, लेकिन आप वास्तव में पहले 70 हजार से कम पढ़ रहे हैं। तो आप वास्तव में उस बिंदु पर सूची का विस्तार करना बंद कर सकते हैं। यह लगभग 4.7 सेकंड में सफल होता है:
def find(n):
arr = [0, 1, 2, 2]
if n <= 3:
return arr[n]
arr_sum = 5
arr_len = 4
for i in range(3, n+1):
arr_sum += i * arr[i]
if arr_sum >= n:
x = (arr_sum - n) // i
return arr_len + arr[i] - (x+1)
arr_len += arr[i]
if arr_len < 70_000:
arr += [i] * arr[i]
और ... आप, दोनों के सुधार से ऊपर गठजोड़ कर सकते हैं, यानी कि लागू if arr_len < 70_000:करने के लिए repeat-संस्करण। तब यह लगभग 4.5 सेकंड में सफल होता है।
मेरे पीसी पर बेंचमार्क परिणाम n = 2 41 के लिए :
Your original: 1.795 seconds
My first one: 0.043 seconds (42 times faster)
My second one: 0.041 seconds (44 times faster)
The combination: 0.026 seconds (69 times faster)
ओह और एक शैली टिप्पणी: आप दो बार ऐसा करते हैं:
if ...:
return ...
else:
...
elseऔर सभी शेष कोड के खरोज अनावश्यक हैं और मैं इसे से बचने चाहते हैं। मैंने उपरोक्त समाधानों में ऐसा किया है।