Ответы пользователя по тегу Алгоритмы
  • Как можно улучшить алгоритм, чтобы он быстрее работал?

    @qid00000000
    Мало что знаю, но информацию найду в гугле
    Переписал часть кода на свой говнокод:

    spoiler

    import itertools
    import time
    import numpy as np
    
    number = 1020
    
    print("Входное число: ",number)
    
    t1 = time.time()
    def next_bigger(n):
        nlst = list(str(n))
    
        for i in range(len(nlst) - 1, -1, -1):
            tempLst1 = nlst[:i]
            tempLst2 = nlst[i:]
    
            vs = list(itertools.permutations(tempLst2, len(tempLst2)))
    
            temp = [int("".join(tempLst1 + list(x))) for x in vs if int("".join(tempLst1 + list(x))) > n]
            if len(temp) >= 1:
                return min(temp)
    
    print("Часть 1: %s"%str(next_bigger(number)))
    
    
    t2 = time.time()
    
    
    def nb(n):
        numlist = np.array(list(str(n)),dtype=int)
        
        i = -1
        while i > -len(numlist) and numlist[i-1] >= numlist[i]:
            i -= 1
            if -len(numlist) == i:
                return None
        
        nextnum = i
        for j in range(i,0,1):
            if numlist[i-1] <numlist[j] and numlist[nextnum] > numlist[j]:
                nextnum = j
        
        numlist[i-1],numlist[nextnum] = numlist[nextnum],numlist[i-1]
        tail = np.array(numlist[i:])
        tail.sort()
        return ''.join(np.array(numlist[:i],dtype=str)) + ''.join(np.array(tail,dtype=str))
    
    print("Часть 2: %s"%str(nb(number)))
    
    
    t3 = time.time()
    
    print("Время выполнения первой части кода: %s\nВремя выполнения второй части кода: %s"%(str(t2-t1),str(t3-t2)))



    Вот тест:
    $ python3.8 permut.py 
    Входное число:  1020
    Часть 1: 1200
    Часть 2: 1200
    Время выполнения первой части кода: 5.14984130859375e-05
    Время выполнения второй части кода: 0.00011038780212402344
    
    $ python3.8 permut.py 
    Входное число:  100000020100000
    Часть 1: 100000021000000
    Часть 2: 100000021000000
    Время выполнения первой части кода: 0.010196208953857422
    Время выполнения второй части кода: 0.00019025802612304688


    Можно заметить, что на больших числах, ваш код сдает позиции.

    Можно преобразования переписать через использование map, но мне удобно numpy использовать.
    Ответ написан
    1 комментарий