Скорость сортировки по системе Radix

Я реализовал алгоритм сортировки по основанию в Python 3. Сначала он находит максимальное количество цифр в списке, затем меняет их на строки и добавляет 0. Например, [7, 23, 107, 1, 53] к [‘007’, ‘023’, ‘107’, ‘001’, ‘053’]. Затем я создаю новую матрицу, [[] * 10]. Я добавляю числа с последней цифрой 0 в lst[0], числа с последней цифрой 1 в lst[1]и т. д. Затем я сглаживаю матрицу в список и рекурсию с lst и с позицией на единицу меньше предыдущей (в данном случае с предпоследней цифры). Могу я получить совет, как его улучшить? Вот мой код:

def radix_sort(lst):
    '''list -> list'''

    #finds maximum number of digits in list
    num_of_digits = max([len(str(x)) for x in lst])

    #Adds 0s to the front of the number if necessary and changes it to a string
    for x in range(len(lst)):
        lst[x] = '0' * (num_of_digits - len(str(lst[x]))) + str(lst[x])

    #helper function to sort based on the position
    def helper(lst, pos):
        '''list, int -> list'''
        #places numbers with 0 in the position in the ans[0], 1 in the position in ans[1], etc.
        ans = [[] for _ in range(10)]
        
        #adding numbers to the position in ans
        for x in lst:
            ans[int(x[pos])].append(x)
        
        #flattened list, reusing lst to save memory
        lst = []
        for x in ans:
            for y in x:
                lst.append(y)
        
        #we have sorted the whole list
        if pos == 0:
            return lst
        
        #recurse again with smaller position
        return helper(lst, pos - 1)

    #changing the strings to integers and returning
    return [int(x) for x in helper(lst, num_of_digits - 1)]

        #flattened list, reusing lst to save memory
        lst = []

Это не экономит память. Вызывающий текущий helper call по-прежнему имеет ссылку на «старый» список, поэтому он останется в памяти в дополнение к этому новому списку. У вас будет один список для каждого уровня звонка. Чтобы действительно сэкономить память, вы можете сделать lst.clear() вместо этого, чтобы на всех уровнях использовался один и тот же список.

Чтобы еще больше сэкономить память, сделайте del ans, x, y после того, как вы восстановили lst от них, прежде чем позвонить helper рекурсивно, иначе они также останутся в памяти, снова один раз на уровень вызова.

Например для lst = ['1' * 800] * 1000эти улучшения изменили пиковое использование памяти с более 15 МБ до менее 0,5 МБ в этом моем тесте:

import tracemalloc

lst = ['1' * 800] * 1000
tracemalloc.start()
radix_sort(lst)
peak = tracemalloc.get_traced_memory()[1]
print(peak)

Или просто делайте это итеративно, а не рекурсивно, тогда у вас, скорее всего, не возникнет этих проблем, и вам не придется беспокоиться об ошибках ограничения рекурсии из-за большого количества.

Вот итеративный вариант с несколькими другими изменениями:

def radix_sorted(lst):
    '''list -> list'''
    lst = list(map(str, lst))
    width = max(map(len, lst))
    lst = [s.rjust(width, '0') for s in lst]
    for i in range(width)[::-1]:
        buckets = [[] for _ in range(10)]
        for s in lst:
            buckets[int(s[i])].append(s)
        lst = [s for b in buckets for s in b]
    return list(map(int, lst))