2

Estou aprendendo programação com Python 3.6 e participo de um site de desafios.

Preciso achar o menor número cujo valor corresponde ao seu índice numa lista. Se a lista só contiver um elemento, deve retornar o mesmo. Se houver mais de um elemento que atenda o critério deve retornar 1. Caso não haja tal elemento, deve retornar -1. Meu código funciona, mas precisa ser otimizado e executar mais rápido, abaixo de 1.5 segundos. Alguém pode ajudar? Segue abaixo o código.

Grato.

def index_equals_value(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if arr.index(number) == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
                break
    if hits == 1:
        return hit_nmbr
   else:
       return -1
1
  • O enunciado diz como serão fornecidos os valores? Talvez existam ainda mais otimizações que possam ser feitas.
    – Woss
    19/08/2018 às 15:52

2 Respostas 2

1

Seu algoritmo tem um bug importante. Da documentação:

list.index(x[, start[, end]])

Return zero-based index in the list of the first item whose value is equal to x

Isso significa que seu algoritmo só compara number com a primeira ocorrência daquele elemento na lista. Quer dizer, ele falha pro seguinte caso, por exemplo:

l = [2, 0, 2]

def index_equals_value(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if arr.index(number) == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1

print(index_equals_value(l))  # -1

Aqui o 2 na posição 2 satisfaz a condição desejada, mas a comparação sempre acontece com o índice 0, porque é lá a primeira ocorrência do número 2.

Incidentalmente, o index também é uma função muito lenta porque verifica a lista toda até encontrar o primeiro elemento passado pra ela. Quer dizer, se você procura por um número x e ele ocorre só no elemento 30000000 da lista, o index vai percorrer 30000000 elementos antes de achar e retornar, quando na verdade só precisamos saber se arr[x] == x.


Medindo tempo de execução:

# Criar lista aleatória
import random
l = [random.randint(0, 2000) for _ in range(2000)]

-

%%timeit
index_equals_value(l)  # Medir tempo de execução da função original
# 27.6 ms ± 2.54 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

-

def index_equals_value_2(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if arr[number] == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1

-

%%timeit
index_equals_value_2(l)  # Medir tempo de execução da função modificada
# 23.7 µs ± 108 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Como você pode ver, corrigir o bug também acelera a função por 3 ordens de magnitude.

Você deve agora tratar a exceção resultante de um if arr[number] == number se number for maior do que o tamanho da lista, ou implementar uma verificação para que essa checagem não aconteça. Também não queremos que números negativos sejam contados de trás pra frente, então temos que ignorá-los:

def index_equals_value_2(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for number in arr:
        if number < 0 or number >= len(arr):
            continue  # Número não pode satisfazer condição
        if arr[number] == number:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1

Como sugestão do Anderson, também podemos fazer uma solução que itera sob a lista com enumerate e compara diretamente o índice ao valor, e não temos que nos preocupar com isso:

def index_equals_value_3(arr):
    hits = 0
    if len(arr)==1:
        return arr[0]
    for ind, number in enumerate(arr):
        if number == ind:
            hits += 1
            hit_nmbr = number
            if hits > 1:
                return 1
    if hits == 1:
        return hit_nmbr
    else:
        return -1
3
  • E tem um ponto muito importante: se arr[-2] for -2 ele deve contar como ocorrência? Com o seu código isso aconteceria, mas o enunciado não deixa claro sobre isso. Sendo de um site de desafios, que possui exercícios agnósticos à linguagem, acredito que o índice seja considerado apenas entre 0 e len(arr)-1.
    – Woss
    19/08/2018 às 14:21
  • @AndersonCarlosWoss ah, boa. Não tinha pensado no caso negativo. Vale a pena fazer a checagem. O break foi resquício do copicola, vou tirar também! 19/08/2018 às 14:24
  • 1
    Provavelmente vale adicionar a solução utilizando o for i, v in enumerate(arr) para contornar o possível problema com o índice, como uma solução alternativa.
    – Woss
    19/08/2018 às 14:26
0

Tentei a solução abaixo para todos os casos levantados pelo @Pedro von Hertwig e eles funcionaram instantâneamente:

import random
random.seed(42)

def listSearch(x):
    ''' Procura o primeiro índice i tal que x[i]=i.
        Retorna -1 caso não encontre.'''
    for i in range(len(x)):
            if x[i]==i : return i
    return -1

# Caso 1: 
random.seed(2)
l = [random.randint(0, 2000) for _ in range(200000)]
l[199999]=199999
print('O índice é: ',listSearch(l)) # O índice é: 199999

# Caso 2: 
l = [0]
print('O índice é: ',listSearch(l)) # O índice é: 0

# Caso 3: 
l = [3]
print('O índice é: ',listSearch(l)) # O índice é: -1

# Caso 4: 
random.seed(42)
l = [random.randint(0, 20000000) for _ in range(200000)]
l[199999]=199999
print('O índice é: ',listSearch(l)) # O índice é: 873

# Caso 5: 
random.seed(2)
l = [random.randint(0, 2000) for _ in range(200000)]
l[0] = 199999
l[199999]=199999
print('O índice é: ',listSearch(l)) # O índice é: 199999

# Caso 6:
random.seed(2) 
l = [random.randint(0, 2000) for _ in range(200000)]
print('O índice é: ',listSearch(l)) # O índice é: -1

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 .