Сортировка по проверке 2 шагах элементов в списке, и проверить точность метода


Этот код работает следующим образом : Он принимает количество теста Т. Для каждого тестового случая, он принимает длину последовательности целых чисел П и последовательность (или список) себя я.

Цель состоит в том, чтобы отсортировать список, проверяя каждые три последовательных элементов, но только сравнение заканчивается. Л[я] И Л[я+2]. Если правое полушарие меньше, чем левое, то эти две должны быть заменены. Этот алгоритм будет продолжаться, пока не могут быть заменены.

Проблема в том, мой код работает для Н < 100. Также работы Н больше, но очень медленно, превысил срок, который составляет 20 секунд.

Если список оказался отсортирован правильно, на выходе должен быть "ОК".

Если список не отсортирован, то выход должен быть первый индекс, в котором индекс элемента меньше, чем его.

Это часть Гугл код вареньем 2018 qualificatiom круглый, законченный уже.

Как оптимизировать это в Python..? Какие аргументы? Спасибо.

    T = input()

    N = []
    L = []
    output = []

    for t in range(T):

        N.append(input())
        L.append(raw_input())


    def trouble(l, n):
        repeat = True
        while repeat:

            repeat = False 
            for index in range(0,n-2):
                if l[index] > l[index+2]:
                    repeat = True
                    dum = l[index:index+3]
                    l[index] = dum[-1]
                    l[index+2] = dum[0]
                    del dum
        return l

    def search(l, n):

        for i in range(n):

            if l[i] > l[i+1]:

                return i

    for i in range(T):

        l = L[i].split()
        l = [int(num) for num in l]
        res = trouble(l, N[i])
        if res == sorted(l):
            output.append('OK')
        else:
            output.append(search(l, N[i]))

    for t in range(T):

        print('Case #'+str(t+1)+': '+str(output[t]))


134
3
задан 8 апреля 2018 в 05:04 Источник Поделиться
Комментарии
1 ответ

С помощью Python 2.7, у вас есть xrange. Улучшения в производительности может быть минимальный (но все же улучшения):


Преимущество xrange() за range() минимально (с
xrange() еще для создания ценностей, когда просил за них), кроме
когда очень большой ассортимент используется на памяти-голодали машины или когда
все элементы серии никогда не используется (например, когда цикл
обычно прекращается с перерывом).


Разделить свои \$ л \$ и использовать map как можно скорее.

L.append(map(int, raw_input().split()))


Замены в Python так же легко, как:

a, b = b, a

Не нужно выделять временный манекен (и del это позже):

if l[index] > l[index + 2]:
repeat = True
l[index], l[index + 2] = l[index + 2], l[index]


Теперь, для предела время, поскольку вы знаете, что вы на самом деле сортировка четных и нечетных индексов подсписки disjointly; соединить свой \$ л \$ и сортировать их. Затем прикрепить их как соткать их вместе.

# L has been read from user
l_even = sorted(l[::2])
l_odd = sorted(l[1::2])

а затем соединить их вместе.

4
ответ дан 8 апреля 2018 в 07:04 Источник Поделиться