DjangoBB LoFi version

Полная версия: Как еще можно оптимизировать следующий код?

Начало » Python для экспертов » Как еще можно оптимизировать следующий код?

1 2 3 4 5 6 7 8 9

izekia

Июль 23, 2008 02:10:54

ага, у меня 1.03 с твоей идеей получилось

import psyco
psyco.full()
from collections import defaultdict

import sys

rinput = sys.stdin.readline
routput = sys.stdout.write

def main():
	nums = defaultdict(int)
	for x in range(100):
		nums[str(x)] = x
	for caseNum in range(input()):
		rowCount=input()
		prevLine = [0,]
		for i in range(rowCount):
			lastLine = [nums[x] for x in rinput().split()]
			lastLine[0] += prevLine[0]
			lastLine[-1] += prevLine[-1]
			for j in range(1, len(lastLine) - 1):
				lastLine[j] += prevLine[j] if prevLine[j] > prevLine[j - 1] else prevLine[j - 1]
			prevLine = lastLine
		routput(str(rowCount == 0 and '0' or max(lastLine)) + '\n')

main()

izekia

Июль 23, 2008 02:26:40

да, 0.96 - это серьезно, показывай код :)

crchemist

Июль 23, 2008 02:27:51

faster 1.0 )

import psyco; psyco.full()
import sys
from cStringIO import StringIO
from array import array
fin = StringIO(sys.stdin.read())
fout = StringIO()
rinput = fin.readline
routput = fout.write
def main():
    cache = {}
    for i in range(100):
        cache[str(i)] = i
    for i in range(int(rinput())):
        num_of_rows = int(rinput())
        prev_line = [cache[rinput().rstrip()]]
        last_line = []
        for j in range(1, num_of_rows):
            last_line = [cache[x] for x in rinput().rstrip().split()]
            for z in range(len(last_line)):
                if z:
                    plx = prev_line[z if z < len(prev_line) else z - 1]
                    last_line[z] += prev_line[z - 1] >= plx and  prev_line[z - 1] or plx
                else:
                    last_line[0] += prev_line[0]
            else:
                prev_line = last_line
        else:
            routput(str(max(last_line or prev_line)) + '\n')

    fout.seek(0)
    sys.stdout.write(fout.read())
main()

izekia

Июль 23, 2008 02:33:33

пишешь буфер?
спасибо за код, надо завтра разобраться с выводом
кстати, array тебе зачем?)
и стрип убери, он со сплитом не нужен

crchemist

Июль 23, 2008 02:38:39

more faster 0.95

import psyco; psyco.full()
import sys
from cStringIO import StringIO
import gc; gc.disable()
fin = StringIO(sys.stdin.read())
fout = StringIO()
rinput = fin.readline
routput = fout.write
def main():
    cache = {}
    for i in range(100):
        cache[str(i)] = i
    for i in range(int(rinput())):
        num_of_rows = int(rinput())
        prev_line = [cache[rinput().rstrip()]]
        last_line = []
        for j in range(1, num_of_rows):
            last_line = [cache[x] for x in rinput().split()]
            for z in range(len(last_line)):
                if z:
                    plx = prev_line[z if z < len(prev_line) else z - 1]
                    last_line[z] += prev_line[z - 1] >= plx and  prev_line[z - 1] or plx
                else:
                    last_line[0] += prev_line[0]
            else:
                prev_line = last_line
        else:
            routput(str(max(last_line or prev_line)) + '\n')
    fout.seek(0)
    sys.stdout.write(fout.read())
main()

izekia

Июль 23, 2008 02:54:43

да, 0.93 - это еще веселее, у меня есть идея, только надо сначала поспать :)

crchemist

Июль 23, 2008 02:55:11

ух!!!!!! 0.93

import psyco; psyco.full()
import sys
from cStringIO import StringIO
import gc; gc.disable()

fin = StringIO(sys.stdin.read())
fout = StringIO()
rinput = fin.readline
routput = fout.write
def main():
    cache = {}
    for i in range(100):
        cache[str(i)] = i
    for i in range(int(rinput())):
        num_of_rows = int(rinput())
        prev_line = [cache[rinput().rstrip()]]
        last_line = []
        for j in range(1, num_of_rows):
            last_line = [cache[x] for x in rinput().split()]
            last_line[0] += prev_line[0]
            for z in range(1, len(prev_line)):
                plx = prev_line[z]
                last_line[z] += prev_line[z - 1] >= plx and  prev_line[z - 1] or plx

            last_line[-1] += prev_line[len(prev_line) - 1]
            prev_line = last_line

        routput(str(max(last_line or prev_line)) + '\n')
    fout.seek(0)
    sys.stdout.write(fout.read())
main()

izekia

Июль 23, 2008 23:20:07

0.92
спасибо за идею со StringIO, это намного ускоряет ввод и вывод
кстати, есть интересная задача, аналогичная, только с ограничением SUMITR

import psyco
psyco.full()
from collections import defaultdict
import sys
from cStringIO import StringIO
import gc; gc.disable()
fin = StringIO(sys.stdin.read())
fout = StringIO()
rinput = fin.readline
routput = fout.write

def main():
	nums = defaultdict(int)
	for x in range(100):
		nums[str(x)] = x
	for caseNum in range(int(rinput())):
		rowCount=nums[rinput().rstrip()]
		lastLine = prevLine = [nums[rinput().rstrip()],]
		for i in range(1, rowCount):
			lastLine = [nums[x] for x in rinput().split()]
			lastLine[0] += prevLine[0]
			lastLine[-1] += prevLine[-1]
			for j in range(1, len(lastLine) - 1):
				lastLine[j] += prevLine[j] if prevLine[j] > prevLine[j - 1] else prevLine[j - 1]
			prevLine = lastLine
		routput(str(max(lastLine)) + '\n')
	fout.seek(0)
	sys.stdout.write(fout.read())
main()

izekia

Июль 24, 2008 01:59:56

кажется это предел, давай договоримся о ничьей :)
а то спать хочется и задач еще много интересных, можно на PRIME1 повоевать :cool:

crchemist

Июль 24, 2008 12:09:52

можна швидше.
Замість
fin = StringIO(sys.stdin.read())
rinput = fin.readline
і багатьох викликів rinput()

можна:

lines = sys.stdin.readlines()

for line in lines:
……..