0

Есть задача написать код эффективной сортировки под конкретную задачу и этот код должен пройти тесты в котором есть определенные ограничения, например по времени выполнения и по лимиту памяти. Пока мой код не проходит по лимиту памяти. Я как понимаю память начинает много потреблять при разделении элементов на группы, но как улучшить код пока не понимаю. Я новичок и только учусь и для меня трудно даются алгоритмы, подскажите пожалуйста как можно еще улучшить код чтобы меньше потребляла памяти?

def partition(competitors, left, right):
    if right <= left:
        return
    pivot = (left + right) // 2
    part = competitors[pivot]
    begin = left
    end = right
    while begin <= end:
        while part > competitors[begin]:
            begin += 1
        while part < competitors[end]:
            end -= 1
        if begin <= end:
            competitors[begin], competitors[end] = competitors[
                end], competitors[begin]
            begin += 1
            end -= 1
    partition(competitors, left, end)
    partition(competitors, begin, right)


def transformations(competitors):
    competitors[1] = - int(competitors[1])
    competitors[2] = int(competitors[2])
    return [competitors[1], competitors[2], competitors[0]]


def quick_sort(competitors):
    partition(competitors, 0, len(competitors) - 1)
    return [line[2] for line in competitors]


if __name__ == '__main__':
    number = int(input())
    competitors = [transformations(input().split()) for _ in range(number)]
    result = quick_sort(competitors)
    print(*result, sep="\n")

1 ответ 1

2

Быстрая сортировка выполняется in-place, т.е. не требует дополнительного места для хранения массива. Ей, однако, нужно место в стеке для хранения состояния, размер этого места зависит от глубины рекурсии, и при неудачном разделении размер стека может быть сравним с размером массива. Чтобы этого избежать, можно рекурсивный вызов делать только для более короткой части, а длинную обрабатывать тут же. В таком случае глубина стека не превысит log(n)

Примерно так модифицировать ваш код (не проверял):

def partition(competitors, left, right):
    while right > left:
        pivot = (left + right) // 2
        part = competitors[pivot]
        begin = left
        end = right
        while begin <= end:
            while part > competitors[begin]:
                begin += 1
            while part < competitors[end]:
                end -= 1
            if begin <= end:
                competitors[begin], competitors[end] = competitors[
                    end], competitors[begin]
                begin += 1
                end -= 1
        if end - left < right - begin:
            partition(competitors, left, end)
            left = begin
        else:
            partition(competitors, begin, right)
            right = end
3
  • Спасибо за разъяснения! Код проверил на тесты, этот код стал быстрей работать по времени, но память на тестах показывает тоже самое что и в моем коде.
    – zheskod
    18 авг 2022 в 14:51
  • Память тратится на список competitors - это неизбежно, и, скорее всего, на его начальное создание из input. Если проверить память, не вызывая сортировку, то она будет такой же, сортировка не увеличит.
    – MBo
    18 авг 2022 в 14:56
  • Тесты я прошел успешно, я разобрался просто дело было не в коде, а в используемом компиляторе. Спасибо еще раз что помогаете
    – zheskod
    18 авг 2022 в 14:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.