Optimizing Treasurehunt’s Question 1 (robot)
เมื่อพิจารณาดี ๆ แล้วพบว่าตาราง list สำหรับใช้คำนวณนั้น มีลักษณะสมมาตรบางส่วน เลยปรับปรุงให้ใช้หน่วยความจำในส่วนที่สมมาตรนั้นเพียงครึ่งเดียว ทำให้ลดการใช้หน่วยความจำได้พอสมควร และการคำนวณใน list ย่อย นั้นใช้เพียง list ก่อนหน้าเท่านั้น ดังนั้นพอคำนวณได้ list ปัจจุบันแล้ว ก็ลบ list ก่อนหน้าทิ้งได้ แต่ผมไม่อยากแก้โค้ดมาก เลยเอาแค่เปลี่ยนเป็น list ว่างพอ ผลคือ
b=2000
if b>a:
a, b = b, a
d=[]
for i in range(a):
d[i:]=[[]]
if i>=b:
x = b
else:
x = i
for j in range(x+1):
if (i == 0) and (j == 0):
d[i][j:] = [0]
elif (i == 0) or (j == 0):
d[i][j:] = [1]
elif i == j:
d[i][j:] = [d[i][j-1]*2]
else:
d[i][j:] = [d[i][j-1] + d[i-1][j]]
if i>0:
d[i-1]=[]
print d[a-1][b-1]
ผลการรัน โดยใช้ time จับเวลา
415828425864924998634542842325676808706232957586556725463361909680781449739748170 786476583991009842613588566821101566552449812050519515271426829403308897930154848 139000401217874574325171349240478804805012554662232593418186105627855887297242750 191258293109799452562416018445296661723328582808673234975864811354576092306731674 226129026615041968499816993517068588780940662630054770440825519413455865220243087 597454080782838938422451159980693138755678460019308423353936671267937407109197183 261946634690754460222691463521097187455850580048349711806796515481309363032514472 631419167126959879296426641287728281408263950661584874428072352076560611103304329 056994774368533971570942013663930927771345889508878174490486498112868394435125871 368770117617083125252317200772612121394477978635381281677951466408518108004063757 181565789433577065739615351320655283808516684687687348436814782925229015434783262 936635458985024720378317210338353260437300968307371995465273889042991687076670199 592582593447226951517354719649532201876810233809966157181452417833096317816478439 040563226541144136090250318325435743209975329838676879857054480550574759550296644 05427578211111064192312240045083183062752759630345186798202023360000 real 0m6.381s user 0m5.024s sys 0m0.076s
ลองแก้ขนาดเป็น 4000×4000 คำตอบยาวมากไม่โพสต์แล้วกัน แต่จับเวลาได้
real 0m59.338s user 0m27.342s sys 0m0.148s
ทั้งหมดรันบนแล็ปท็อป AMD Turion64 2.2GHz (1 core), RAM 1GB
