Как я могу оптимизировать этот код Python для сортировки большого ввода? - PullRequest
Новая
       8

Как я могу оптимизировать этот код Python для сортировки большого ввода?

0 голосов
/ 04 сентября 2018

Я пытаюсь решить эту проблему на HackerRank, которая требует, чтобы вы отсортировали список целых чисел и выяснили, сколько раз число было перемещено, чтобы разместить в правильном порядке возрастания (взятки в контексте проблемы).

Мой код проходит 8 из 12 тестовых случаев, но завершается неудачно, если ввод слишком велик с ошибкой тайм-аута. Похоже, это общий показатель на HackerRank, что код слишком медленный для решения проблемы. Так есть ли способ оптимизировать этот код, чтобы он быстрее работал на больших наборах данных? 

def minimum_bribes(queue):
"""Returns the minimum number of bribes people in a queue accepted."""

# Variable to keep track of bribes
bribes = 0

# Check if queue is too chaotic
for i in queue:
    index = queue.index(i)
    if i - index > 3:
        return "Too chaotic"

# Use a bubble sort to find number of bribes
for i in range(len(queue) - 1):
    for j in range(len(queue) - 1 - i):
        if queue[j] > queue[j + 1]:
            queue[j], queue[j + 1] = queue[j + 1], queue[j]
            bribes += 1

return bribes


# Number of test cases
t = int(input())
results = []

for _ in range(t):

    # Number of people
    n = int(input())
    # Final State of queue
    q = list(map(int, input().rstrip().split()))

    # Add bribe counts to results array
    results.append(minimum_bribes(q))

# Print results
for result in results:
    print(result)

1 Ответ

0 голосов
/ 05 сентября 2018

Я бы порекомендовал использовать цикл while для проверки условия: если в предыдущей итерации не было подкачки, запускать новую итерацию подкачки не нужно. 

def minimumBribes(queue): 

     for i in queue:
            index = queue.index(i)
            if (i - index) > 3:
            print("Too chaotic")
            return    

    n = len(queue)
    swap =0
    swapped = True
    j =0    
    while swapped:
        j+=1
        swapped = False
        for i in range(n-j):
            if queue[i] > queue[i+1]:
                queue[i], queue[i+1] = queue[i+1], queue[i]
                swap +=1
                swapped = True

    print(swap)
    return swap
...