DjangoBB LoFi version

Найти - Пользователи

Полная версия: Медленное выполнение программы

Начало » Python для новичков » Медленное выполнение программы

1 2 3

dingo

Март 29, 2012 17:52:30

Какие существуют стандартные способы ускорения программы написанной на python2.7 ?

Soteric

Март 29, 2012 19:08:18

Поиск “узких” мест, их оптимизация и распараллеливание.

slav0nic

Март 29, 2012 21:26:01

запуск на pypy - это модно

Андрей Светлов

Март 30, 2012 00:44:17

профайлер пробовали?

dingo

Март 30, 2012 21:35:32

А можно по подробней про распараллеливание и профайлер
Запустить на pypy нет возможности
Нужно написать программу которая проверяет правильность раставления скобок менять алгоритм пробовал не помогло , ограничения по времени 2сек

doza_and

Март 30, 2012 22:02:09

dingo
менять алгоритм пробовал не помогло , ограничения по времени 2сек

Какой объем текста?
Какие алгоритмы пробовали? (в вашем случае допустимо и весь алгоритм привести).

dingo

Март 30, 2012 22:12:57

объем текста от 1 до 120000 символов

f=open("brackets.in")
l=f.read()
def proverka(masiv,steck):
	bool="True"
	for q in masiv:
		if q=="(" or q=="[" or q=="{":
			steck.insert(0,q)
		else:
			if q=="]" and steck[0]=="[":
				del(steck[0])
			elif  q==")" and steck[0]=="(":
				del(steck[0])
			elif q=="}" and steck[0]=="{":
				del(steck[0])
			else:
				otvet="NO"
				bool="False"
				break
	if bool=="True":
		if len(steck)==0:
			otvet="YES"
		else:
			otvet="NO"
	return otvet
if len(l)%2==0:
	steck=[l[0]]
	otvet=proverka(l[1::],steck)
else:
	otvet="NO"
f1=open("brackets.out","w")
f1.write(otvet)
f1.close()

fata1ex

Март 31, 2012 00:09:37

bool="True"
...
if q=="(" or q=="[" or q=="{":
...
otvet="NO"
bool="False"
...
if bool=="True":

Вам пока противопоказан python :(

Да и алгоритм у вас неверный - на последовательность “(())” он работать не будет.

dingo

Март 31, 2012 11:45:03

Вы не поверите но на этой последовательности он прекрасно работает

fata1ex

Март 31, 2012 13:27:02

Да, согласен.

В таком случае пара очевидных советов:
1. Добавление элемента в начало листа намного медленнее, чем добавление в конец.
2. Непонятно, зачем вызывать del.
3. Стиль кода ужасен :(

def correct_brackets(sequence):
    open_brackets  = "({["
    close_brackets = ")}]"
    stack = []
    for bracket in sequence:
        try:
            if bracket in open_brackets:
                stack.append(bracket)
            elif open_brackets.index(stack.pop()) == close_brackets.index(bracket):
                pass
            else:
                return False
        except (ValueError, IndexError):
            return False
    if stack:
        return False
    return True

Я бы написал что-нибудь в этом роде. Можете подумать, как упростить выражение после elif. Возможно, тут лучше будет использовать словарь или еще что-нибудь. Так же можете убрать ValueError в try-except, если вам не нужна проверка на корректность скобочной последовательности в смысле набора символов.

Если грубо:

seq = "(([[{{}}]]))"
time_before = time.time()
for _ in range(100000):
    correct_brackets(seq)
print time.time() - time_before

>>> ~2.13

Со словарем и правда побыстрее:

>>> ~1.39

Извращение, конечно, но лучше мне ничего пока в голову не пришло :)

open_brackets  = {'(':1, '{':2, '[':3}
close_brackets = {')':1, '}':2, ']':3}

Как итог:

def correct_brackets(sequence):
    open_brackets       = "({["
    dict_open_brackets  = {'(':1, '{':2, '[':3}
    dict_close_brackets = {')':1, '}':2, ']':3}
    stack = []
    for bracket in sequence:
        try:
            if bracket in open_brackets:
                stack.append(bracket)
            elif dict_open_brackets[stack.pop()] == dict_close_brackets[bracket]:
                pass
            else:
                return False
        except (ValueError, IndexError):
            return False
    if stack:
        return False
    return True

in dict.keys() будет медленее обычного in seq, поэтому оставил open_brackets. Вряд ли от вас потребуют что-нибудь намного более быстрое, чем этот вариант. Удачи!