Алгоритм оптимизации

Задача следующая:

Найдите и вычислите сумму всех возможных подстрок в заданной входной мастер-строке s, из которых можно составить слово «тира» (сокращение от курса), дополнительно удалив ненужные буквы.

ПРИМЕР, возвращаемое значение 11 при вводе "tixratiyra": 1: тихратийра, 2: тихратийра, 3: тихратийра, 4: тихратийра, 5: тихратийра, 6: тихратийра, 7: тихратийра, 8: тихратийра, 9: тихратийра, 10: тихратийра, 11: тихратийра.

Я могу создать рабочий фрагмент кода, но он не будет работать достаточно быстро, он должен выполнить эту задачу за время O (n) с максимальной длиной ввода 10 ^ 5.

Мой код работает мучительно медленно:

def count(s):
    start = timeit.default_timer()

    c = "bcdefghjklmnopqsuvwxyz"
    last_char = ""
    indexes = set()
    unique_indexes = []

    last_A = s.rfind("a")
    last_R = s.rfind("r", 0, last_A)
    last_I = s.rfind("i", 0, last_R)
    last_T = s.rfind("t", 0, last_I)

    unique_tiras = ""

    for i in range(len(s)):
        char = s[i]
        if char not in c:
            if char == "t":
                if i <= last_T:
                    indexes.add("t")
                    last_char = "t"
                    unique_tiras += str(i) + "t"
            
            elif char == "i" and last_char != "i":
                if i <= last_I and "t" in indexes:
                    indexes.add("i")
                    last_char = "i"
                    unique_tiras = unique_tiras.replace("t", "i")

            elif char == "r" and last_char != "r":
                if i <= last_R and ("t" and "i") in indexes:
                    indexes.add("r")
                    last_char = "r"
                    unique_tiras = unique_tiras.replace("i", "r")

            elif char == "a":
                if i <= last_A and ("t" and "i" and "r") in indexes:
                    last_char = "a"
                    unique_tiras = unique_tiras.replace("r", f"-{i};")
                    pairs = unique_tiras.split(";")
                    unique_tiras = ""

                    for elements in pairs:
                        if "-" in elements:
                            Tindex = elements.split("-")
                            unique_indexes.append((int(Tindex[0]), int(Tindex[1])))
                            unique_tiras += Tindex[0] + "r"
                        
                        else:
                            unique_tiras += elements

    if len(unique_indexes) < 1:
        print("found no tira substrings with input '", s[0:20], "'")
        print("indexing took a total of", timeit.default_timer()-start, "s")

        return 0
    
    print("found a total of", len(unique_indexes), "tira substrings with input '", s[0:20], "'") #, which are the following:
    #print(unique_indexes)
    print("indexing took a total of", timeit.default_timer()-start, "s")

    start = timeit.default_timer()

    unique_substrings = set()

    for tiras in unique_indexes:
        begin = 0

        while begin <= tiras[0]:
            end = tiras[1]

            while end <= len(s) - 1:
                unique_substrings.add((begin, end))
                end += 1
            
            begin += 1

    print("calculating suitable substrings took a total of", timeit.default_timer()-start, "s")
    print("found suitable substrings a total of")

    return len(unique_substrings)

if __name__ == "__main__":
    print(count("ritari")) # 0
    print(count("taikurinhattu")) # 4
    print(count("ttiirraa")) # 4
    print(count("tixratiyra")) # 11 
    print(count("aotiatraorirratap")) # 42

Кажется тяжелым. Наивно, для каждой возможной подстроки len(s)+ сколько букв каждой буквы s есть (в правильном порядке)? Может быть, лучше подсчитать, сколько каждой буквы s находится в основной строке, а затем заняться математикой - вам нужно будет сохранить индексы, чтобы убедиться, что буквы в порядке. Это должно как минимум сократить пространство поиска.

wwii 03.02.2023 15:59

Если основная строка состоит из 1e5 символов, а прямо посередине находится искомая последовательность 'tira', и эти буквы больше нигде в основной строке не встречаются, сколько в ней подстроки?

wwii 03.02.2023 16:22
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
2
81
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Сам ответ не O(n). Больше похоже на O(n²). Например, для строки «xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtiraxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx»

ответ заключается в том, что вы можете выбрать 40 различных начал для вашей подстроки и 40 различных концов (всего 39 x. Таким образом, вы можете включить от 0 до 39 x в качестве префикса и от 0 до 39 x в качестве суффикса). Что приводит к 1600 возможным подстрокам.

С «тирой» посередине это примерно (n/2)².

Моя точка зрения здесь не в том, чтобы сказать «это невозможно». Возможно. Я собираюсь это сделать :D.

Я хочу сказать, что это невозможно, если перечислить все возможности. Потому что, если вы просто пробуете множество подстрок и считаете действительные, вам нужно попробовать как минимум все рабочие решения (плюс нерабочее). И даже если предположить, что вы можете проверить гипотезу за O(1) (чего вы, вероятно, не можете), это означает, что время вычисления должно быть как минимум таким же, как и результат.

Таким образом, мы должны оценить количество рабочих подстрок, фактически не перечисляя и не проверяя их.

Вот мой шанс на это

def minIndex(s, sub):
    if not sub[0] in s:
        return None,None
    i0=s.index(sub[0])
    ix=i0
    for c in sub[1:]:
        ss=s[ix+1:]
        if not c in ss:
            return None, None
        ix=ss.index(c)+ix+1
    return i0, ix


def mycount(s, sub):
    tot=0
    while True:
        a,b=minIndex(s, sub)
        if a is None:
            return tot
        tot+=(a+1)*(len(s)-b)
        s=s[a+1:]
    return tot

def count(s):
    return mycount(s, "tira")

if __name__ == "__main__":
    print(count("ritari")) # 0
    print(count("taikurinhattu")) # 4
    print(count("ttiirraa")) # 4
    print(count("tixratiyra")) # 11 
    print(count("aotiatraorirratap")) # 42

То, что я здесь делаю, это какой-то жадный алгоритм (но точный). Итак, я ищу минимальный индекс «t» в строке и минимальный индекс «a», который следует за «t» (с другими буквами между ними).

И это дает мне, используя предыдущее рассуждение на моем примере «xxxxtiraxxxxx», ряд комбинаций.

Обратите внимание, что это делается за O(b), где b — указанный индекс.

Затем, из-за возможности наличия нескольких букв «т», каждая из которых связана с потенциально разным окончанием «а», Я пересчитываю то же самое из всех возможных отправных точек после этой 1-й буквы «t». Потом после 3-го. ... Пока нет ответа.

Например, для s='xxxxxtitrairaxxxxx'minIndex(s, 'tira') есть (5,9). Это означает, что для того, чтобы «тира» начиналась с первого t, у нас есть 6 возможных отправных точек (0,1,2,3,4,5). И для каждой начальной точки у нас есть len(s)-9=9 конечных точек (что имеет смысл: после первого возможного окончания a у нас есть iraxxxxx, то есть 8 букв. Мы можем включить от 0 до 8 из них в качестве суффикса подстроки).

В дополнение к тем 6*9=54 возможностям, которые начинаются с первого t, мы должны рассмотреть и те, которые не включают. Итак, мы просто должны сделать то же самое с s='itrairaxxxxx'.

У нас есть 1 буква перед первой t. И за первой возможной a (которая не такая, как раньше: первая a была возможным окончанием раньше. Но начиная со второй t уже нет, и любая рабочая подстрока теперь должна включать и вторую a), за ней следует 5 x. Итак, это 2 возможных префикса (i или ничего) и 6 возможных суффиксов (``, x, xx, xxx, xxxx, xxxxx). Итак, 12.

Опять же, как только это будет сделано, мы пробуем то, что можем, без второго запуска t. Итак, мы повторяем попытку с 'rairaxxxxx'. Это ничего не дает. Конец расчета.

Окончательный ответ: 54+12 = 66.

Каждый этап вычислений частично повторяет всю строку. В целом это O(n).

Ну, не совсем O(n), в худшем случае. Но это потому, что я был немного ленив.

например со строкой tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttira, как есть, мой алгоритм O(n²): каждый t является итерацией в mycount цикле while. И minIndex, поскольку единственная буква a находится в самом конце, должна перебирать всю строку, чтобы найти ее индекс. Так что в таком случае это O (n²) (даже если это кажется O (n), потому что этот внутренний O(n) находится внутри .index() кода, который является внутренним, вероятно, кодом C, так что очень-очень быстро, сравните остальные чистого кода Python).

Но этого можно избежать: я мог бы запомнить положение первых i, r и a. И пересчитывать позицию индекса a только тогда, когда мы прошли этот первый i, пропуская t (и даже когда мы это делаем, также проверяем, что мы прошли первый r при поиске другого i и т. д.).

И это гарантирует, что это действительно O (n) (потому что либо вам нужно постоянно обновлять первое a, но тогда это означает, что оно близко к первому t, а общий алгоритм равен O (n) — O(n×len('tira')) чтобы быть точным ; или нет, и тогда вычисление этого .index('a') выполняется всего несколько раз, и алгоритм тоже O(n)).

В любом случае, с практической точки зрения этот алгоритм намного быстрее вашей версии, и вам не нужно перечислять и проверять возможные решения, чтобы их подсчитать. Например, для "x"*1000 + "tira" + "x"*1000 ваш код занимает 0,54 секунды, а этот — 4,5 мкс.

Для аварийного теста (наихудший сценарий для моего алгоритма) s = "t"*10000+"ira" ваш код занимает 31,7 секунды, мой — 35 мс.

Спасибо, это работает фантастически! Действительно полезно, это задание было для меня мучительно сложным по сравнению с другими в этом курсе. Большое спасибо!

poser 03.02.2023 17:13

Другие вопросы по теме