Как я могу улучшить это решение Hackerrank, чтобы избежать тайм-аута? - PullRequest
Новая
       23

Как я могу улучшить это решение Hackerrank, чтобы избежать тайм-аута?

0 голосов
/ 03 июля 2019

Проблема: https://www.hackerrank.com/challenges/ctci-merge-sort/problem Мое решение: 

total_swaps = 0
def countInversions(a):
    global total_swaps
    total_swaps = 0
    mergesort(a)
    return total_swaps

def merge(arr, left, mid, right):
    global total_swaps
    buffer = arr[left:mid]
    arr_index = left
    arr1_index = 0
    arr2_index = mid
    while arr1_index < len(buffer) and arr2_index < right:
        if buffer[arr1_index] > arr[arr2_index]: 
            arr[arr_index] = arr[arr2_index]
            total_swaps += len(buffer) - arr1_index
            arr2_index += 1
        else:
            arr[arr_index] = buffer[arr1_index]
            arr1_index += 1
        arr_index += 1

    while arr1_index < len(buffer):
        arr[arr_index] = buffer[arr1_index]
        arr_index += 1
        arr1_index += 1

def mergesort(arr, left=0, right=None):
    if right is None:
        right = len(arr)
    if right - left <= 1:
        return
    mid = left + (right-left) // 2
    mergesort(arr, left, mid)
    mergesort(arr, mid, right)
    merge(arr, left, mid, right)

Я провалю тесты 11-13.Как я могу сделать мой код быстрее?Любые другие улучшения тоже приветствуются.

1 Ответ

1 голос
/ 04 июля 2019

Вот несколько небольших улучшений, которые вы можете попробовать, но я сомневаюсь, что это принесет много пользы:

  • вызовите mergesort(a, 0, len(a)) из countInversions() и удалите значения аргументов по умолчанию в mergesort и тест right is None.
  • избавиться от глобальной переменной и заставить mergesort() вернуть счетчик инверсий, который он вычислит, добавив возвращаемые значения рекурсивных вызовов.
  • использовать сортировку вставки на маленьких кусках, например if right - left <= 5:
...