Python - Encontrar los n valores más pequeños que están separados por al menos x en una lista
Estoy intentando encontrar los n valores más pequeños en una lista donde su ubicación está separada por al menos x, teniendo en cuenta los duplicados. p.ej. Los 5 valores más pequeños que se encuentran al menos a 2 de distancia entre sí.
Ejemplo sencillo:
values = [-9995, -82, -659, -1006, -2009, 2062, -10107, -12, 13]
result: [-10107, -9995, -2009, -659, 13]
Ejemplo más complejo:
values = [-9995, -83, -82, -82, -1006, -2009, 18, 2062, -659 ,-9995, -9995]
Por ejemplo en la lista anterior:
-9995 es el valor más pequeño. -9995 vuelve a ocurrir y hay al menos 2 de diferencia con respecto al primero. El -9995 restante se ignora ya que solo está a 1 del anterior. -2009 es el tercer valor más pequeño -1006 no se considera ya que solo está a 1 de los valores anteriores. Entonces tomamos el siguiente valor más pequeño -659, ya que está al menos a 2 de los valores anteriores (suponiendo que tomamos el primero y el último -9995 e ignoramos el penúltimo) -83 no se considerad ya que está a sólo uno de -9995. entonces tomamos -82. hemos llegado a 5 números así que paramosresult: [-9995, -9995, -2009, -659, -82]
Las listas con las que estoy trabajando tienen ~1.000.000 de elementos y tengo ~1.000 listas. Generé estas listas a partir de un DataFrame de pandas (al iterar a través de groupby), por lo que sería útil si existe un enfoque numpy/pandas para optimizar este cálculo.
El intento hasta el momento es capaz de generar resultados suponiendo que no se produzcan duplicados:
def smallest_values(list_of_numbers: list, n_many: int, x_apart: int):
sorted_values = sorted(values)
small_val, small_val_loc = [], []
for val in sorted_values:
if len(small_val) <= n_many:
ind = list_of_numbers.index(val)
within_x = [i for i in range(ind-(x_apart-1), ind+x_apart)]
if not any(i in small_val_loc for i in within_x):
small_val_loc.append(ind)
small_val.append(val)
return small_val
values_simple = [-9995, -82, -659, -1006, -2009, 2062, -10107, -12, 13]
values_complex = [-9995, -83, -82, -82, -1006, -2009, 18, 2062, -659 ,-9995, -9995]
d = 2
n = 5
smallest_values(values_simple, n, d) # [-10107, -9995, -2009, -659, 13] CORRECT
smallest_values(values_complex, n, d) # [-9995, -2009, -659, -82] INCORRECT
No estoy seguro de que esté explícito lo que estás intentando optimizar. Considere la lista [1, 0, 1, 300, 500, 400] win=3. Si comienzas con cero obtienes [0, 300, 400] pero si comienzas con uno, puedes obtener [1, 1, 400]. El primero tiene el número más pequeño, pero el segundo tiene el total más pequeño. ¿Cuál es la respuesta correcta?
-Marca27/03/2021 a las 18:00
[0, 300, 400] sería el resultado correcto de mi pregunta. No estoy buscando la suma más pequeña, quiero los n números más pequeños que estén separados por al menos x. Gracias. El algoritmo comenzaría con el número más pequeño y agregaría iterativamente el siguiente número más pequeño sujeto a la restricción de que esté al menos a x de distancia en la lista fr.om los números anteriores agregados
- Ali Zaini27/03/2021 a las 18:08
¿Entonces estás diciendo que siempre tomarás el siguiente número más pequeño incluso si esa elección te obliga a tomar números más grandes más adelante? Entonces sumando -1 a lo anterior y haciendo n=4 -- [-1, 100, 1, 0, 1, 300, 500, 400], la respuesta correcta es [-1, 0, 300, 400] no [- 1, 1, 1, 400]?
-Marca27/03/2021 a las 18:14
Sí, exactamente correcto
- Ali Zaini27/03/2021 a las 18:15
¿Cuál es la lógica para tomar el último valor -9995 en un ejemplo más complejo, en lugar del penúltimo (que es el mismo valor, pero aparece antes en la lista)?
-perl27/03/2021 a las 18:15
------------------------------------
El problema clave aquí es romper los vínculos en valores duplicados, como -9995 en el ejemplo. Básicamente, debemos intentar seleccionarlos en diferente orden y verificar cuál produce la secuencia con el siguiente valor inferior (o si el siguiente valor es el mismo, entonces el siguiente, y así sucesivamente).
Una forma de hacerlo es con búsqueda recursiva:
from collections import defaultdict
# find the next smallest and return all locations of that number
# that can be used (i.e. not within d from the previously used values)
def get_next(vs, vd, d, skip):
for v in vs:
os = []
for l in vd[v]:
if not any([l>x-d and l<x+d for x in skip]):
os.append((l, v))
if len(os) > 0:
return os
return None
# recursive search
def r(vs, vd, n, d, skip=[], out=[]):
if len(out) >= n:
return out
os = []
for (l, v) in get_next(vs, vd, d, skip):
o = r(vs, vd, n, d, skip+[l], out+[v])
os.append(o)
mo = min(os)
return mo
# main func
def smallest_values(values, n, d):
vd = defaultdict(list)
for l, v in enumerate(values):
vd[v].append(l)
vs = sorted(vd.keys())
return r(vs, vd, n, d, [], [])
Pruebe con los ejemplos proporcionados:
values_simple = [-9995, -82, -659, -1006, -2009, 2062, -10107, -12, 13]
values_complex = [-9995, -83, -82, -82, -1006, -2009, 18, 2062, -659 ,-9995, -9995]
print('simple: ', smallest_values(values_simple, 5, 2))
print('complex: ', smallest_values(values_complex, 5, 2))
Salida:
simple: [-10107, -9995, -2009, -659, 13]
complex: [-9995, -9995, -2009, -659, -82]
Una prueba de tiempo en una lista de 1.000.000 de valores (800 ms, aproximadamente 15 minutos para 1.000 listas de un solo subproceso):
%%time
vs = np.random.randint(0, 1000000, 1000000)
smallest_values(vs, 5, 2)
Salida:
CPU times: user 780 ms, sys: 20.8 ms, total: 800 ms
Wall time: 800 ms
[3, 5, 6, 7, 8]
P.D. Esto encuentra la secuencia que tiene el valor más bajo anteriormente en la secuencia. Por ejemplo, preferirá [1, 2, 100] sobre [1, 3, 4] (ambos tienen 1 en la posición 1, pero la primera secuenciae tiene 2 < 3 en la posición 2). IIUC, esto es lo que se espera, según su comentario, supongo que la lógica quedaría redactada como: ¿existe una selección de los valores elegidos anteriormente que permita elegir el siguiente valor más pequeño?
2
1
Su enfoque es muy inteligente, muchas gracias. Su comprensión del enunciado del problema es correcta, debería preferirse [1,2,100]
- Ali Zaini28/03/2021 a las 17:46
¡Genial, me alegro de haberte ayudado! Resultó ser un problema muy interesante :)
-perl28/03/2021 a las 17:48
------------------------------------
Este es un trabajo complicado, nos gustaría construir una lista de índices donde la primera entrada sea el índice del valor más pequeño en list_of_numbers y cada siguiente entrada en esta index_list apunte al siguiente valor más alto en list_of_numbers manipulando este tipo de lista sería mucho más fácil y eficiente. Podríamos hacer lo siguiente:
index_map=dict()
for i in range(len(list_of_numbers)):
value=list_of_numbers[i]
if value in index_map:
index_map[value]+=[i]
else:
index_map[value]=[i]
sorted_values = sorted(index_map)
Ahora tenemos un diccionario decada valor único en list_of_numbers que se asigna a todos los índices que apuntan a él. También tenemos una lista que va desde el valor único más pequeño hasta el más grande. Ahora podemos construir nuestra index_list:
index_list=[]
for value in sorted_values:
index_list+=index_map[value]
del index_map, sorted_values
Todo lo que queda por hacer es iterar de izquierda a derecha en nuestra index_list y encontrar la primera combinación de índices que tengan el espacio apropiado. Esto es mucho más fácil y rápido de calcular en un algoritmo.
Desafortunadamente, no es posible tener una complejidad de tiempo menor que O(n) porque es necesario verificar cada entrada en list_of_numbers para encontrar la entrada más pequeña.
Hice esto usando una función recursiva, pero definitivamente puedes optimizarla y hacer que el algoritmo sea más inteligente:
def gap_selecter(numlist, n_many, gap):
if numlist==None: # Fast exit if recursion fails
return None
x=numlist[0]
speudolist=numlist[1:]
if n_many==1: # base case
return [x]
else:
for i in range(len(speudolist)):
if abs(x-speudolist[i])>=gap: #recursive step occurs here
recursion_list = gap_selecter(speudolist[i:], n_many-1, gap)
if recursion_list !=None:
return [x]+recursion_list
return None # if we find no possible list we return None
Aquí está todo junto.
def smallest_values(list_of_numbers: list, n_many: int, x_apart: int):
index_map=dict()
for i in range(len(list_of_numbers)):
value=list_of_numbers[i]
if value in index_map:
index_map[value]+=[i]
else:
index_map[value]=[i]
sorted_values = sorted(index_map)
index_list=[]
for value in sorted_values:
index_list+=index_map[value]
del index_map, sorted_values
final_indices=gap_selecter(index_list, n_many, x_apart)
if final_indices==None:
return None
final_numbers=[]
for i in final_indices:
final_numbers+=[list_of_numbers[i]]
return final_numbers
values_simple = [-9995, -82, -659, -1006, -2009, 2062, -10107, -12, 13]
values_complex = [-9995, -83, -82, -82, -1006, -2009, 18, 2062, -659 ,-9995, -9995]
d = 2
n = 5
test_simple = smallest_values(values_simple, n, d) # [-10107, -9995, -2009, -659, -12]
test_complex = smallest_values(values_complex, n, d) # [-9995, -9995, -2009, -659, -83]
2
1
Sin embargo, test_complex falla, ¿no? No debería tener -83 (si entendí correctamente el problema)
-perl27/03/2021 a las 21:14
Sí, lo siento, en el ejemplo simple debería ser [-10107, -9995, -2009, -659, 13] -12 es el siguienteo -10107 y como Perl mencionó -83 no debe elegirse
- Ali Zaini27/03/2021 a las 21:37
------------------------------------
//EDITAR: Ahh, ahora veo. La frase clave es (asumiendo que tomamos el primero y el último -9995 e ignoramos el penúltimo)
El gran problema es que no puedes elegir ningún valor duplicado (en tu ejemplo, el penúltimo -9995 de la lista). En su lugar, desea elegir valores duplicados de modo que su último elemento (¿o la suma de la lista resultante?) sea mínimo, ¿correcto?
Para mí, esto suena como un problema de optimización restringida. Ni siquiera estoy seguro de si tiene el mismo resultado dependiendo de lo que usted defina como "óptimo"." (ya sea la suma o el último elemento o algo más...)