оптимизация скорости выполнения алгоритма

Рейтинг: 0Ответов: 1Опубликовано: 28.02.2023

прошу помощи у почтеннейшей публики.

Дана строка: "abc#d##c"

каждый символ '#' в строке аналогичен бэкспейсу - удаляет символ перед ним.

Так, удалив бэкспейсы и символы перед ними из первоначальной строки получим: "ac"

Из строки 'gfh#jds###d#dsd####dasdaskhj###dhkjs####df##s##d##' получим 'gdasda'

Мое первое решение:

def clean_string(s):
    # print(s)
    start = time()
    while '#' in s:
        if s.count('#') != len(s):
            s = re.sub(r'[\w]#', '', s)
        else:
            s = ''
            break
    return s, time() - start

но оно не проходит установленный в 12000ms лимит по скоростию С замерами времени получается - 0.09 s

Решив, что дело в используемых в первом решении регулярных выражениях (я слышал, что дескать они медленные), я переписал решение уже без их, регулярок, использования:

def clean_string(s):
    start = time()
    if s.count('#') > len(s) / 2:
        return ''
    else:

        def func(s):
            d = []
            for i in range(1, len(s)):
                if s[i] == '#' and s[i-1] != '#':
                    d.append(''.join((s[i-1], s[i])))

            for i in d:
                s = s.replace(i, '')

            return s

        while '#' in s:
            s = func(s)

    return s, time() - start

Мои замеры скорости выполнения показали во втором варианте 0.0 s, но на сервисе, куда я должен отправит решение, второе решение тоже не прошло(

Прошу помощи, подскажите еще варианты решения, как еще можно ускорить выполнение скрипта?

python производительность циклы re
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

В общем, благодаря подсказке коллеги CrazyElf задача решена:

def clean_string(s):
    print(s)
    ans = []
    for i in s:
        if i != '#':
            ans.append(i)
        elif i == '#':
            try:
                ans.pop()
            except IndexError:
                continue

    return ''.join(ans)

все элементарно делалось через стек... бывает же такое, что самое простое решение не всегда самое очевидное( Еще раз благодарю коллегу за подсказку!