Find values in a list that are equal to the index they are in. How to optimize?

Asked

Viewed 180 times

2

I am learning programming with Python 3.6 and participate in a challenge site.

I need to find the smallest number whose value corresponds to its index in a list. If the list contains only one element, it should return the same. If there is more than one element that meets the criterion, it must return 1. If there is no such element, it must return -1. My code works, but needs to be optimized and run faster, below 1.5 seconds. Can anyone help? Follow the code below.

Grateful.

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
  • Does the statement say how the values will be provided? Perhaps there are even more optimizations that can be done.

2 answers

1

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
  • And there’s a very important point: whether arr[-2] for -2 it should count as occurrence? With its code this would happen, but the statement does not make clear on this. Being from a site of challenges, which has agnostic exercises to the language, I believe that the index is considered only between 0 and Len(arr)-1.

  • @Andersoncarloswoss ah, good. I hadn’t thought about the negative case. It’s worth checking. The break was trace of the copicola, I will take also!

  • 1

    Probably worth adding the solution using the for i, v in enumerate(arr) to circumvent the possible problem with the index, as an alternative solution.

0

I tried the solution below for all cases raised by @Pedro von Hertwig and they worked instantly:

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

Browser other questions tagged

You are not signed in. Login or sign up in order to post.