0

Boa noite galera !! Estou com o seguinte problema nesse algoritmo, o custo dele ainda está alto e eu gostaria de saber se tem como melhorar o custo dele ainda mais, pois essa é uma questão de ortografia que tenho que entregar online e infelizmente um teste deu um custo de tempo alto cerca de 3s, caso tiver alguma ideia de como poderia melhorar ficaria muito grato, ou se souber algum Levenshtein mais rápido com um custo melhor de tempo, também ficaria muito grato, vou deixa o link da questão caso queiram fazer alguns teste https://olimpiada.ic.unicamp.br/pratique/p2/2008/f2/ortografia/

n, m = [int(c) for c in input().split()]
dicionario = [0] * n
palavras = [0] * m
for i in range(n):
    n = input()
    dicionario[i] = n.lower()
for i in range(m):
    m = input()
    palavras[i] = m.lower()

def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_ += [distances[i1]]
            else:
                distances_ += [1 + min((distances[i1], distances[i1 + 1], distances_[-1]))]
        distances = distances_
    return distances[-1]

for i in range(len(palavras)):
    lis = []
    for n in dicionario:
        if len(n) <= len(palavras[i]) + 2 or len(n) < len(palavras[i]) + 2:
            if levenshteinDistance(palavras[i], n) <= 2:
                lis += [n]
        else:
            pass
    palavras[i] = lis
    print(' '.join(palavras[i]), end="")
    if palavras[i] != palavras[-1]:
        print(" ", end='')
    print('')
2
  • a criação das duas listas iniciais podem ser trabalhadas de forma a integrar os dois loops for que vem na sequencia Commented 6/11/2019 às 0:36
  • As duas listas iniciais são das entradas, como poderia fazer isso ?? Commented 6/11/2019 às 0:37

1 Resposta 1

0

seguindo a entrada e saida do exercicio, a inicialização das listas iniciais fica custosa

dicionario = [0] * n
palavras = [0] * m

oq acontece é que uma lista de posição unica é criada varias vezes, vc pode fazer uma compreensão de lista ja eliminando os loops na sequencia

dicionario = [input().lower() for x in range(n)]
palavras = [input().lower() for x in range(m)]

vc joga o loop for dentro da lista, não vai estar economizando no loop, mas sim na criação das listas inicias, 6 listas para duas

uma outra observação é que vc pode retirar o .lower(), a entrado do exercicio ja esta toda em minusculo, e a palavras com letras maiusculas e minuscula são diferentes, isso faz acrescentar mais uma operação

[input() for x in range(n)]

fica 6 chamadas de função a menos

4
  • Acho que isso não iria fazer o algoritmo sair dos 3s kkkkkkkk, eu ainda estou me perguntando que entrada é essa que dura 3s, isso não é de Deus Commented 6/11/2019 às 11:51
  • verdade, essa alteração é só uma leve otimização, talvez tambem seria vantajoso olhar os outros 4 loop no codigo, talvez posso reduzir um Commented 6/11/2019 às 13:56
  • Eu tentei reduzir mas não conseguir, num sei se dar para melhorar o algoritmo de levenshtein, acredito que possa, pois ouvir algumas pessoa dizendo que tem uma solução de O(m*n) m é a linha e n é a coluna, mas não conseguir implementar ! Commented 6/11/2019 às 19:04
  • outra forma de vc melhorar o codigo é evitar as chamadas de len, use variavel para armazenar o resultado de len que sera usado em mais de uma vez, eu acho que consultar uma variavel é mais rapido doque chamar uma função Commented 6/11/2019 às 19:56

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .