How to optimize this code?

Question

A music loop is an excerpt of music that has been composed to repeat continuously (i.e., the excerpt starts again every time it reaches the end). Loops can be scanned for example using PCM. PCM, from Pulse Code Modulation, is a technique for representing analog signals, widely used in digital audio. In this technique, the signal magnitude is sampled at regular intervals of time, and the sampled values are stored in sequence. A peak in a waveform is a value of a sample representing a local maximum or minimum, i.e., a point of inflection of the waveform.

ENTREE

The input contains several test cases. The first line of a test case contains an integer N, representing the number of samples in the music loop. The second line contains integers N, separated by spaces, representing the sequence of sample magnitudes. The end of the input is indicated by a line containing only the zero number.

EXIT

For each input test case your program must print a single line, containing only an integer, the number of spikes in the music loop.

link for this problem in the URI

To solve this problem I did this program, which works but is very slow:

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) """
            

Notice I review the list loop, based on it I create a second list listaSentido which stores the sense of the wave and only then calculate the peaks. I believe that it is not necessary to create this second list. Creating and then analyzing it takes a lot of time. But how to calculate this value from the list only loop?

Answer 1

This question refers to the number problem 1089 of the category AD-HOC of the site URI.

See here the entirety of the statement.

Well, in order to solve this problem we only need to use the following code::

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)

Note that when we execute this code we receive a screen black with the blinking cursor in the corner superior esquerdo. At this point we must enter a número inteiro and press enter. At this time the 1st block if check the value of n. If the value is equal to 0, execution of the code will be terminated. Otherwise we will receive the cursor again blinking below the value of n. Right now we must type all the possible values of h, in same line, separated for a single space and, in the end, press enter. Having performed these operations the for block will go through the range(1, n + 1) performing the relevant checks. At this time the block if will verify whether h[i] is minor that its predecessor (h[i - 1]) and, also, if it is minor that his successor (h[i + 1]) and, if positive, accumulate the unit value in the variable picos. Should the condition of if is not satisfied, the code is directed to the elif. Arriving at the elif will be verified if the value of h[i] is greater that its predecessor (h[i - 1]) and, also, if it is greater that his successor (h[i + 1]) and, if positive, accumulate the unit value in the variable picos. And, finishing, will display the result.

Observing:

This code has already been tested, submitted and properly approved on the URI site. And, just for the record, this code only took 0.017 s to run on said website.

Answer 2

I don’t know very well the logic behind it, but follow my review. I believe it is more efficient, when possible give a check, please:

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)