Your algorithm has an important bug. From the documentation:
list.index (x [ start [ end]])
Return zero-based index in the list of the first item whose value is equal to x
This means that your algorithm only compares number to with the first occurrence of that element in the list. That is, it fails the following case, for example:
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
Here, the 2 in the 2 position satisfies the desired condition, but the comparison always happens with index 0, because that is the first occurrence of the number 2.
Incidentally, index is also a very slow function because it scans the entire list until it finds the first element passed to it. I mean, if you look for a x number and it occurs only in element 30000000 in the list, the index will go through 30000000 elements before finding and returning, when in fact we just need to know if arr[x] == x .
Measuring runtime:
# 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)
As you can see, fixing the bug also speeds the function by 3 orders of magnitude.
You should now treat the exception resulting from a if arr[number] == number if number is greater than the size of the list, or implement a check so that this check does not happen. We also do not want negative numbers to be counted backwards, so we have to ignore them:
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
As Anderson's suggestion, we can also make a solution that iterates under the enumerate list and directly compares the index to the value, and we do not have to worry about it:
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
