← Сtrl

izekia · Июль 20, 2008 10:40:44

crchemist
програма тестується на spoj.pl - там скоріше за все нема ніяких бібліотек - чистий пітон - алгоритм напевне фіговий а не бібліотеки

выше весь код написан, если алгоритм фиговый - напиши в чем
для треугольника с n строками используется n*n/2 сравнений и сложений, и я считаю это оптимальным

по поводу библиотек - буст, к примеру, там есть

crchemist · Июль 20, 2008 13:29:49

ага - алгоритм ніби нормальний - я так само колись робив на http://projecteuler.net/ Щодо оптимізації: ти спочатку зчитуєш всі дані в масив а потім рахуєш. Думаю скоріше буде зчитувати трикутник по одній лінії і ту лінію додавати одразу в результат. Плюс використовуй цикл while замість for - він мав би бути набагато швидшим. взагалі мені здається що цикл for буде набагато повільніший map - можна замість for вліпити map. Пізніше кину код

Отредактировано (Июль 20, 2008 13:37:30)

crchemist · Июль 20, 2008 16:19:27

на 10секундах на 0.5 сек швидший за твій

#!/usr/bin/env python
import sys
range_line = range(1000)
res = []

for i in range_line[:input()]:
    triangle = []

    for j in range_line[:input()]:
        line = map(int, sys.stdin.readline().split())

        if triangle:
            lst_ln = triangle[-1]
            line = map(lambda z:line[z] + max(lst_ln[z - 1 if z else z:  z + 1]), range_line[:len(line)])
        triangle.append(line)

    res.append(max(triangle[-1]))

for i in res:
    sys.stdout.write(str(i) + '\n')

izekia · Июль 20, 2008 20:28:14

crchemist
ага - алгоритм ніби нормальний - я так само колись робив на http://projecteuler.net/ Щодо оптимізації: ти спочатку зчитуєш всі дані в масив а потім рахуєш. Думаю скоріше буде зчитувати трикутник по одній лінії і ту лінію додавати одразу в результат. Плюс використовуй цикл while замість for - він мав би бути набагато швидшим. взагалі мені здається що цикл for буде набагато повільніший map - можна замість for вліпити map. Пізніше кину код

я не понимаю по-украински, сорри :)

izekia · Июль 21, 2008 08:32:59

crchemist
на 10секундах на 0.5 сек швидший за твій

#!/usr/bin/env python
import sys
range_line = range(1000)
res = []

for i in range_line[:input()]:
    triangle = []

    for j in range_line[:input()]:
        line = map(int, sys.stdin.readline().split())

        if triangle:
            lst_ln = triangle[-1]
            line = map(lambda z:line[z] + max(lst_ln[z - 1 if z else z:  z + 1]), range_line[:len(line)])
        triangle.append(line)

    res.append(max(triangle[-1]))

for i in res:
    sys.stdout.write(str(i) + '\n')

по поводу алгоритма - он немного нерабочий, так как input идет с первой строки, а не наоборот
и по поводу мапа, я делал замеры, у меня вышло что работает быстрее, чем map(f, list)

сейчас еще попробую прогнать тесты

Отредактировано (Июль 21, 2008 08:33:33)

izekia · Июль 21, 2008 08:39:11

crchemist
ага - алгоритм ніби нормальний - я так само колись робив на http://projecteuler.net/ Щодо оптимізації: ти спочатку зчитуєш всі дані в масив а потім рахуєш. Думаю скоріше буде зчитувати трикутник по одній лінії і ту лінію додавати одразу в результат. Плюс використовуй цикл while замість for - він мав би бути набагато швидшим. взагалі мені здається що цикл for буде набагато повільніший map - можна замість for вліпити map. Пізніше кину код

нашел переводчик, по поводу while, я тоже так думал, но когда сделал - разницы в результате не заметил
просто у меня на моих тестовых данных задача отрабатывается за 5.200 секунд примерно, на этой же задаче у ребят результаты меньше двух секунд, конечно может быть там инпут проще чем в моем тесте, но пока я в любом случае получаю тайм лимит

izekia · Июль 21, 2008 08:57:05

def f(x):
	return x*2

def map_f(n):
	map(f, range(n))

def for_f(n):
	[f(x) for x in range(n)]

def main():
	n = 100000
	map_f(n)
	for_f(n)

if __name__ == '__main__':
	import profile, pstats

	profile.run('main()', 'result.prof')
	pstats.Stats('result.prof').strip_dirs().sort_stats(-1).print_stats()

на этом коде у меня стабильно время выполнения for_f меньше либо равно, то есть в целом мап медленнее получается

cybergrind · Июль 21, 2008 12:29:58

мое имхо - если настолько критично быстродействие - переписать все на С или плюсы

izekia · Июль 21, 2008 12:32:59

cybergrind
мое имхо - если настолько критично быстродействие - переписать все на С или плюсы

да на с++ уже решил эту проблему, просто мне интересно как можно было добиться такого же результата на питоне

izekia · Июль 21, 2008 12:37:07

shiza
boost - это набор сишный билиотек на все случаи жизни.

Есть для питона ускоритель. Называется Psyco (http://psyco.sourceforge.net/).

да, спасибо, я его и имел в виду, просто зачем-то буст сюда приплел :)

Python-сообщество

Уведомления

#1 Июль 20, 2008 10:40:44

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

#2 Июль 20, 2008 13:29:49

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

#3 Июль 20, 2008 16:19:27

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

#4 Июль 20, 2008 20:28:14

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

#5 Июль 21, 2008 08:32:59

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

#6 Июль 21, 2008 08:39:11

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

#7 Июль 21, 2008 08:57:05

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

#8 Июль 21, 2008 12:29:58

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

#9 Июль 21, 2008 12:32:59

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

#10 Июль 21, 2008 12:37:07

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

Board footer