Súčet trojuholníkov: Codechef Ako môže byť kód optimalizovaný pre rýchlosť a veľké testovacie prípady? - python, python-3.x

Som nováčik Pythonu.

Nižšie bol problém začiatočníkov na stránke codechef.com Odkaz na problém

Problém Text:

Uvažujme o trojuholníku čísel, v ktorom ačíslo sa objaví v prvom riadku, dve čísla sa objavia v druhom riadku, tri v treťom riadku, atď. že:

• na každej ceste sa nasledujúce číslo nachádza na riadku nižšie, viac presne buď priamo pod alebo pod a jedno miesto vpravo;
• počet riadkov je prísne pozitívny, ale menší ako 100
• všetky čísla sú kladné celé čísla medzi O a 99.

vstup

V prvom riadku celé číslo n - počet testovacích prípadov (približne 1000). Potom nasleduje n testovacích prípadov. Každý testovací prípad začína počtom riadkov, po ktorých nasleduje ich obsah.

Výkon

Pre každý testovací prípad zapíšte určenú hodnotu do samostatného riadku.

Toto je nasledovné môj kód:

tempij=[]
s=0

def solve(i,j,ll):
global s
s=0
tempij=[]
if i==len(ll):
return 0
elif (i,j) in tempij:
return s
else:
tempij.append((i,j))
t1=solve(i+1,j,ll)
t2=solve(i+1,j+1,ll)
t=max(t1,t2)+ll[i][j]
s=t
return t

t=int(input())
ll=[]

for k in range(t):
ll=[]
n=int(input())
for i in range(n):
lst=[]
text=input().split()
for j in range(len(text)):
lst.append(int(text[j]))
ll.append(lst)
print(solve(0,0,ll))

Problém s týmto kódom:

Pokúsil som sa implementovať Rekurziu s Memoizáciou v súlade s ich vydavateľstvom k tomuto problému. Odkaz na úvodník

Vysvetlenie kódu (relevantná časť redakčného):

(Používam tempij na ukladanie do pamäte cache v kóde vyššie. Niečo podobné otázke SO: Otázka o memoizácii)

Hoci to funguje pre testovacie prípady uvedené ako príklad, zdá sa, že presahuje časový limit pre iné testovacie prípady.

Moja otázka: Ako môžem vylepšiť tento kód? Alebo je tam lepší spôsob?

odpovede:

1 pre odpoveď č. 1

Nie som presvedčený, že vaša memoizácia funguje solve, odfúknete svoju vyrovnávaciu pamäť a máte miestneho tempij tieňuje globálnu kópiu. Okrem toho, "naraz sa ukladá iba jedna vypočítaná hodnota s, takže aj keby to fungovalo, pravdepodobne by ste vo väčšine prípadov nezískali správnu hodnotu vo vyrovnávacej pamäti. Odhliadnuc od použitia globálnej premennej (shudder), myslím, že by ste mali použiť niečo viac ako

cache = {}

def solve(i,j,ll):
global cache
if i==len(ll):
return 0
elif (i,j) not in cache:
t1=solve(i+1,j,ll)
t2=solve(i+1,j+1,ll)
t=max(t1,t2)+ll[i][j]
cache[(i, j)] = t
return cache[(i, j)]

---

0 pre odpoveď č. 2

Uvedomil som si svoju chybu. Vďaka JCVanHamme.

Vyššie uvedený kód nebol správne ukladaný do pamäte cache, pretožedôvodov uvedených JCVanHamme. Po každom volaní som obnovoval vyrovnávaciu pamäť. Tak som sa zbavil všetkých globálnych premenných, ktoré spôsobovali problémy (pretože by museli byť znovu nastavené pre každý testovací prípad a to spôsobilo problém). Upravený kód vyzerá takto:

def solve(i,j,ll,cache):


if i==len(ll):
return 0
elif (i,j) not in cache:
t1=solve(i+1,j,ll,cache)
t2=solve(i+1,j+1,ll,cache)
t=max(t1,t2)+ll[i][j]
cache[(i, j)] = t
return cache[(i, j)]

t=int(input())
ll=[]
cache={}

for k in range(t):
ll=[]
cache={}
n=int(input())
for i in range(n):
lst=[]
text=input().split()
for j in range(len(text)):
lst.append(int(text[j]))
ll.append(lst)
print(solve(0,0,ll,cache))

Pôvodná otázka stále platí. Môže to byť vykonané rýchlejšie a lepšie pomocou samotného pythonu? Odhlásil som run-časy ľudí, ktorí používali iné jazyky ako C / C ++ a je tak nízky ako 0:08, zatiaľ čo pre python 3.x je to 0,57!

---