Obteniendo el índice del elemento cercano al final de la lista

Tengo una lista ordenada que contiene objetos, y me gustaría obtener el primer índice del último valor (que se obtiene usando el método get_val) de la lista. Escribí esta función, pero me preguntaba si hay alguna forma de optimizarla aún más.

def index_last_value(tbl, get_val=lambda obj:obj): tbl_len, prev_v = len(tbl), get_val(tbl[-1]) for i,v in enumerate(reversed(tbl)): v = get_val(v) if v == prev_v: index = tbl_len-i-1 if v != prev_v or i+1 == tbl_len: return index prev_v = v class MyObject: def __init__(self, v): self.v = v tbl_1 = list(map(MyObject, [1,1])) tbl_2 = list(map(MyObject, [1,1,2,2,2])) index_last_value(tbl_1, get_val=lambda obj:obj.v) # -> 0 index_last_value(tbl_2, get_val=lambda obj:obj.v) # -> 2

EDITAR: La lista no contiene números, contiene objetos.

davy.ai

July 23, 2023 at 8:16 am

Hay algunas optimizaciones que se pueden realizar en esta función. Una de ellas es usar la búsqueda binaria en lugar de iterar a través de la lista. Esto reduciría la complejidad temporal de O(n) a O(log n). Sin embargo, para utilizar la búsqueda binaria, la lista debe estar ordenada en orden ascendente basándose en el valor devuelto por la función “get_val”.

Si la lista ya está ordenada, como se menciona en la pregunta, entonces podemos usar el módulo “bisect” en Python para realizar la búsqueda binaria. Aquí está cómo se vería la función:

from bisect import bisect_left

def index_last_value(tbl, get_val=lambda obj:obj):
    values = [get_val(obj) for obj in tbl]
    last_val = values[-1]
    index = bisect_left(values, last_val, 0, len(values))
    while index < len(values)-1 and values[index+1] == last_val:
        index += 1
    return index

La función primero crea una lista de los valores devueltos por la función “get_val” para cada objeto en la lista de entrada. Luego encuentra el índice del último valor en esta lista usando “bisect_left” (que devuelve el punto de inserción del valor si aún no está presente en la lista). Luego iteramos sobre los valores restantes en la lista para encontrar el último índice donde el valor es igual al último valor.

Este enfoque tiene una complejidad temporal de O(log n), que es mucho más rápido que la función original.

Answer

davy.ai

July 23, 2023 at 8:16 am
Hay algunas optimizaciones que se pueden realizar en esta función. Una de ellas es usar la búsqueda binaria en lugar de iterar a través de la lista. Esto reduciría la complejidad temporal de O(n) a O(log n). Sin embargo, para utilizar la búsqueda binaria, la lista debe estar ordenada en orden ascendente basándose en el valor devuelto por la función “get_val”.

Si la lista ya está ordenada, como se menciona en la pregunta, entonces podemos usar el módulo “bisect” en Python para realizar la búsqueda binaria. Aquí está cómo se vería la función:
```
from bisect import bisect_left

def index_last_value(tbl, get_val=lambda obj:obj):
    values = [get_val(obj) for obj in tbl]
    last_val = values[-1]
    index = bisect_left(values, last_val, 0, len(values))
    while index < len(values)-1 and values[index+1] == last_val:
        index += 1
    return index
```
La función primero crea una lista de los valores devueltos por la función “get_val” para cada objeto en la lista de entrada. Luego encuentra el índice del último valor en esta lista usando “bisect_left” (que devuelve el punto de inserción del valor si aún no está presente en la lista). Luego iteramos sobre los valores restantes en la lista para encontrar el último índice donde el valor es igual al último valor.

Este enfoque tiene una complejidad temporal de O(log n), que es mucho más rápido que la función original.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Obteniendo el índice del elemento cercano al final de la lista

Answer

davy.ai