kitscribe
@kitscribe
Хаброжитель

Как можно улучшить алгоритм, чтобы он быстрее работал?

Есть алгоритм по поиску следующего большего числа в пермутациях этого числа. Но он недостаточно быстрый.
Как можно его улучшить?

Код
import itertools

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)
  • Вопрос задан
  • 293 просмотра
Решения вопроса 1
@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 использовать.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы