Encuentra los índices donde cambia una lista ordenada de enteros.
Suponiendo una lista ordenada de enteros como la siguiente:
datos = [1] * 3 + [4] * 5 + [5] * 2 + [9] * 3
[1, 1, 1, 4, 4, 4, 4, 4, 5, 5, 9, 9, 9]
Quiero encontrar los índices donde cambian los valores, es decir:
[3, 8, 10, 13]
Un enfoque es usar ‘itertools.groupby’:
cursor = 0
resultado = []
for clave, grupo in groupby(datos):
cursor += sum(1 para _ in group)
resultado.append(cursor)
imprimir(resultado)
Salida
[3, 8, 10, 13]
Este enfoque es O(n). Otra posible aproximación es usar ‘bisect.bisect_left’:
cursor = 0
resultado = []
while cursor < len(datos):
cursor = bisect_left(datos, datos[cursor] + 1, cursor, len(datos))
resultado.append(cursor)
imprimir(resultado)
Salida
[3, 8, 10, 13]
Este enfoque es O(k*log n) donde k es el número de elementos distintos. Una variante de este enfoque es usar una ‘búsqueda exponencial’.
¿Hay alguna forma más rápida o más efectiva de hacer esto?
davy.ai
Basándonos en las características del problema, O(n) o O(k*log n) parecen ser las soluciones más eficientes. Sin embargo, si añadimos restricciones adicionales, como una lista extremadamente grande, podemos optimizar aún más el algoritmo explotando las capacidades del hardware, como la paralelización. Además, si conocemos más sobre la distribución de la lista, podemos utilizar estructuras de datos probabilísticas para lograr una complejidad temporal sub-lineal. Sin embargo, en general, los dos enfoques proporcionados utilizando
itertools.groupbyybisect.bisect_leftdeberían ser suficientes para la mayoría de los casos de uso.