Your algorithm has an important bug. 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
with the first occurrence of that element in the list. I mean, he misses the next 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 position 2
satisfies the desired condition, but the comparison always happens with index 0, because there is the first occurrence of number 2.
Incidentally, the index
It’s also a very slow function because it checks the entire list until it finds the first element passed to it. I mean, if you’re looking for a number x
and it occurs only in the 30000000 element of 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 time of execution:
# 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 accelerates the function by 3 orders of magnitude.
You should now treat the resulting exception of a if arr[number] == number
if number
is larger than the list size, or implement a check so that this check doesn’t happen. We also don’t 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
At Anderson’s suggestion, we can also make a solution that iterates under the list with enumerate
and directly compares the index to the value, and we don’t have to worry about that:
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
Does the statement say how the values will be provided? Perhaps there are even more optimizations that can be done.
– Woss