Почему один код быстрее, чем другой, даже если итераций больше? - PullRequest
Новая
       50

Почему один код быстрее, чем другой, даже если итераций больше?

3 голосов
/ 02 марта 2012

Мой код короткий и имеет меньшее количество итераций, чем другие, но все же он получает ошибку превышения лимита времени, в то время как другой код принят на codechef.com.Коды являются решением проблемы «неоднозначной перестановки» на codechef.com. Почему этот код: 

def inverse(data,x):

    temp=[]

    for i in range(x):
        temp.append(0)
    for i in range(x):
        temp[data[i]-1]=i+1
    return temp

def main():

    while 1:
        x=input()
        if not x:
            return
        data=raw_input().split(' ')
        for i in range(len(data)):
            data[i]=int(data[i])
        temp = inverse(data,x)
        if temp==data:
            print 'ambiguous'
        else:
            print 'not ambiguous'

if __name__ == "__main__":
    main()

быстрее, чем этот код: 

while True:

    output=[]
    n= input()
    if n==0: break
    caseList= raw_input().split()
    amb=1
    for i in range(1, n+1):
        output.append(str(caseList.index(str(i))+1))

    if output==caseList:
        print ("ambiguous")
    else:
        print ("not ambiguous")

Пожалуйста, помогите мне ...

Ответы [ 3 ]

3 голосов
/ 02 марта 2012

Я так понимаю, ваш второй код не находится внутри функции.

Доступ к локальным переменным в функции значительно быстрее, чем к глобальным переменным.Это означает, что код, выполняемый в глобальной области видимости, всегда будет работать медленнее.

2 голосов
/ 02 марта 2012

Когда появляется такая постоянная разница во времени, мы не говорим о чем-то, что в 2 или 3 раза медленнее - если один метод проходит, а другой всегда отключается, это огромная разница во времени - обычно привязанная к алгоритмусложность.

Хотя первый код имеет много места для улучшения (например, использование xrange вместо range), в конечном массиве результат обновляется произвольным доступом, прямо по индексу, вычисленному какdata[i] - 1 - во втором фрагменте вы используете caseList.index(str(i)) для извлечения каждого индекса.Метод «index» lisr выполняет линейный поиск в списке, начиная с начала.Это может показаться небольшим, но когда это делается для каждого элемента в списке, ваш алгоритм, который был O (N), становится O (N²) - что значительно увеличивает скорость во второй форме.

1 голос
/ 02 марта 2012

Похоже, что вы используете строки, где другой код использует целые, что несколько замедлит вас.

...