TransWikia.com

Como otimizar esse código?

Stack Overflow em Português Asked by yoyo on December 23, 2020

Um loop musical é um trecho de música que foi composto para repetir continuamente (ou seja, o trecho inicia novamente toda vez que chega ao final). Loops podem ser digitalizados por exemplo utilizando PCM. PCM, do inglês Pulse Code Modulation, é uma técnica para representação de sinais analógicos, muito utilizada em áudio digital. Nessa técnica, a magnitude do sinal é amostrada a intervalos regulares de tempo, e os valores amostrados são armazenados em sequência. Um pico em uma forma de onda é um valor de uma amostra que representa um máximo ou mínimo local, ou seja, um ponto de inflexão da forma de onda.

ENTRADA

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um inteiro N, representando o número de amostras no loop musical. A segunda linha contém N inteiros, separados por espaços, representando a sequência de magnitudes das amostras.
O final da entrada é indicado por uma linha que contém apenas o número zero.

SAÍDA

Para cada caso de teste da entrada seu programa deve imprimir uma única linha, contendo apenas um inteiro, o número de picos existentes no loop musical.

link para esse problema no URI

Para resolver esse problema fiz esse programa, que funciona, mas é muito lento:

while True:
    n = int(input())

    if n == 0:
        break

    loop = list(map(int, input().split()))  """ criando lista a partir dos inputs """
    listaSentido = []  """ lista para armazenar o sentido da onda, +1 para crescente -1 para decrescente """

    for i in range(len(loop)): """ por se tratar de um loop, o ultimo elemento da lista se relaciona ao primeiro
                                   assim, verifico se o elemento que estou analisando é o último """
        if i + 1 < len(loop):

            if loop[i] > loop[i + 1]: """ Sendo o valor seguinte menor, temos sentido decrescente, e adicionamos -1 """
                cente = -1            """ à lista auxiliar, caso contrário, adicionamos +1 """
                listaSentido.append(cente)
            else:
                cente = 1
                listaSentido.append(cente)
        else:                                 """ quando chego ao último elemento da lista, o comparo com o primeiro """
            if loop[(len(loop)-1)] > loop[0]:
                listaSentido.append(-1)
            else:
                listaSentido.append(1)

        inversao = 0                          """ estabeleço um contador para monitorar a quantidade de vezes que o sentido mudou """
        for i in range(len(listaSentido)):    """ pois quando o sentido muda, certamente há um pondo de inflexão """
            if i + 1 < len(listaSentido):
                if listaSentido[i] != listaSentido[i + 1]:  """ sempre cuidando para que o último elemento seja comparado com o primeiro """
                    inversao += 1
            else:
                if listaSentido[len(listaSentido)-1] != listaSentido[0]:
                    inversao += 1
    
    print(inversao) """ no fim, o valor armazenado em inversão é correspondente ao número de picos (máximos e mínimos) """
            

Reparem que eu analiso a lista loop, baseado nela eu crio uma segunda lista listaSentido que armazena o sentido da onda e só então calculo os picos. Acredito que não seja necessária a criação dessa segunda lista. Criar e depois analisá-la consome muito tempo. Mas como calcular esse valor apenas pela lista loop?

2 Answers

Esta questão se refere ao problema de número 1089 da categorial AD-HOC do site URI.

Veja aqui a íntegra do enunciado.

Pois bem, para resolvermos esta questão basta utilizarmos o seguinte código:

while True:
    n = int(input())
    if n == 0:
        break
    h = [int(x) for x in input().split()]
    h.append(h[0])
    h.append(h[1])
    picos = 0
    for i in range(1, n + 1):
        if h[i] < h[i - 1] and h[i] < h[i + 1]:
            picos += 1
        elif h[i] > h[i - 1] and h[i] > h[i + 1]:
            picos += 1
    print(picos)

Observe que quando executamos este código recebemos uma tela preta com o cursor piscando no canto superior esquerdo. Neste momento devemos digitar um número inteiro e pressionar enter. Neste momento o 1º bloco if verificará o valor de n. Caso o valor seja igual a 0, será encerrada a execução do código. Caso contrário, receberemos novamente o cursor piscando abaixo do valor de n. Neste momento devemos digitar todos os possíveis valores de h, na mesma linha, separados por um só espaço e, no final, pressionar enter. Tendo realizado estas operações o bloco for irá percorrer o range(1, n + 1) realizando as verificações pertinentes. Neste momento o bloco if verificará se h[i] é menor que seu antecessor (h[i - 1]) e, também, se é menor que o seu sucessor (h[i + 1]) e, caso positivo, acumulará o valor da unidade na variável picos. Caso a condição do if não seja satisfeita, o código é direcionado para o elif. Chegando no elif será verificado se o valor de h[i] é maior que seu antecessor (h[i - 1]) e, também, se é maior que seu sucessor (h[i + 1]) e, caso positivo, acumulará o valor da unidade na variável picos. E, finalizando, exibirá o resultado.

Observação:

Este código já foi testado, submetido e devidamente aprovado no site URI. E, só para constar, este código levou apenas 0.017 s para ser executado no referido site.

Correct answer by Solkarped on December 23, 2020

Não sei muito bem a lógica por trás disso, mas segue minha revisão. Acredito que esteja mais eficiente, quando possível dê uma conferida, por favor:

while True:
    n = int(input())
    if n == 0:
        break
    loop = list(map(int, input().split()))
    i = i0 = loop.pop(0)
    cente = None
    inversao = 0
    for i2 in loop:
        ultimo_cente = cente
        cente = i2 > i
        if cente != ultimo_cente:
            inversao += 1
        i = i2
    if cente != (i < i0):
        inversao += 1
    print(inversao)

Answered by Rfroes87 on December 23, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP