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