2010/3/4 Kiko kikocorre...@gmail.com:
Hola a todos.
Estoy intentando buscar los indices de un subconjunto dentro de un conjunto
y quiero saber si existe algo más eficiente que lo que he pensado.
Me explico, por ejemplo, yo tengo:
conjunto = range(1000, 1100, 1)
subconjunto = range(1000,
Daniel Garcia Moreno escribió:
Según mis conocimientos en computación, esta búsqueda es de orden n^2.
Si el primer conjunto está ordenado, puede llegar a ser de orden
n*log(n) puesto que puedes hacer una búsqueda binaria en lugar de
conjunto.index(valor). Y creo que no vas a poder optimizar
Pablo Angulo escribió:
indices = []
ultimo = 0
for v in subconjunto:
ultimo += conjunto[ultimo:].index(v)
indices.append(ultimo)
[conjunto[j] for j in indices]==subconjunto
Lamento ser pesado, pero hay que hacer un cambio:
indices = []
ultimo = 0
for v in subconjunto:
Daniel Garcia Moreno escribió:
Si la lista grande tiene N elementos y la pequeña M, puedes elegir entre
O(Mlog(N)), usando bisect. o O(N), con la técnica que te decía antes.
O puedes combinar las dos, buscar desde el último indice en adelante
pero hacerlo con busqueda binaria.
Yo diría
Olemis Lang (Simelix) escribió:
Aquí por ejemplo hay un caso que ilustra el hecho de no confiar
demasiado en las estimaciones teóricas . Las estimaciones de Pablo et
al se pueden ver afectadas por la eficiencia de la implementación del
método index (el cual no me parece que sea muy O(1) que
Kiko escribió:
tiempo de la primera opción: 0.0149998664856
for i in subconjunto:
ultimo = conjunto.index(i, ultimo+1)
indices.append(ultimo)
Los primero 25 valores de indices = [0, 3, 6, 9, 12, 15, 18, 21, 24,
27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72]
tiempo
