Suponiendo una lista ordenada de enteros como se muestra a continuación:
data = [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 usaritertools.groupby :
cursor = 0 result = [] for key, group in groupby(data): cursor += sum(1 for _ in group) result.append(cursor) print(result)Producción
[3, 8, 10, 13] Este enfoque es O(n). Otro enfoque posible es usar bisect.bisect_left :
cursor = 0 result = [] while cursor < len(data): cursor = bisect_left(data, data[cursor] + 1, cursor, len(data)) result.append(cursor) print(result)Producción
[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 utilizar una búsqueda exponencial .
¿Hay alguna forma más rápida o más eficaz de hacer esto?
Probé el tiempo de ejecución de sus enfoques en dos conjuntos de datos y agregué un tercero usando numpy
data1 = [1] * 30000000 + [2] * 30000000 + [4] * 50000000 + [5] * 20000000 + [7] * 40000000 + [9] * 30000000 + [11] * 10000000 + [15] * 30000000 data2 = list(range(10000000)) cursor = 0 result = [] start_time = time.time() for key, group in groupby(data): cursor += sum(1 for _ in group) result.append(cursor) print(f'groupby {time.time() - start_time} seconds') cursor = 0 result = [] start_time = time.time() while cursor < len(data): cursor = bisect_left(data, data[cursor] + 1, cursor, len(data)) result.append(cursor) print(f'bisect_left {time.time() - start_time} seconds') data = np.array(data) start_time = time.time() [i + 1 for i in np.where(data[:-1] != data[1:])[0]] + [len(data)] print(f'numpy {time.time() - start_time} seconds') # We need to iterate over the results array to add 1 to each index for your expected results. Con data1
groupby 8.864859104156494 seconds bisect_left 0.0 seconds numpy 0.27180027961730957 seconds Con data2
groupby 3.602466583251953 seconds bisect_left 5.440978765487671 seconds numpy 2.2847368717193604 seconds Como mencionó, bisect_left depende en gran medida de la cantidad de elementos únicos, pero parece que usar numpy tiene un mejor rendimiento que itertools.groupby incluso con la iteración adicional en la lista de índices.
Cuando se trata de complejidad asintótica, creo que puede mejorar ligeramente la búsqueda binaria en promedio cuando aplica un enfoque de divide y vencerás más uniformemente distribuido: intente primero identificar el cambio de valor que ocurre más cerca de la mitad de la lista de entrada , dividiendo así el rango en aproximadamente dos mitades, lo que reduciría la siguiente ruta de operación de búsqueda binaria en aproximadamente uno.
Sin embargo, debido a que se trata de Python, es posible que la ganancia no se note, debido a la sobrecarga del código Python (como para yield , yield from , la recursividad, ...). Incluso podría funcionar peor para los tamaños de lista con los que trabaja:
from bisect import bisect_left def locate(data, start, end): if start >= end or data[start] == data[end - 1]: return mid = (start + end) // 2 val = data[mid] if val == data[start]: start = mid val += 1 i = bisect_left(data, val, start + 1, end) yield from locate(data, start, i) yield i yield from locate(data, i, end) data = [1] * 3 + [4] * 5 + [5] * 2 + [9] * 3 print(*locate(data, 0, len(data))) # 3 8 10Tenga en cuenta que esto solo genera índices válidos, por lo que 13 no se incluye para esta entrada de ejemplo.