¿Cómo puedo encontrar eficientemente las distancias desde cada valor hasta el siguiente valor inferior/superior?

24 Jul, 2023 Programación 0

Te diré qué estructuras estoy usando, siéntete libre de recomendar cualquier cambio como arreglos de numpy u algo así.

De todas formas, lo que tengo es una lista de 5 millones de entradas secuenciales que corresponden a un precio de acciones.

Luego tengo otras 2 listas, cada una de ellas tiene la misma longitud: 5 millones de entradas. Estas listas corresponden a un “límite superior” anticipado y un “límite inferior” anticipado que espero que la acción alcance a partir de ese punto en la secuencia.

Lo que quiero hacer es pasar por las 5 millones de entradas de la lista de límites inferiores y registrar cuánto tiempo toma en la secuencia hasta que el precio finalmente alcance ese límite inferior. Luego quiero hacer lo mismo para la lista de límites superiores.

Aquí tienes un ejemplo de una posible solución para una lista de precios de acciones con solo 10 entradas:

prices =       [15,16,18,22,23,17,15,19,15,18]
upper_limits = [17,18,21,23,25,22,18,21,18,20]
lower_limits = [14,15,16,18,19,15,13,17,14,16]

solved_upper = [2,1,1,1,x,x,1,x,1,x]
solved_lower = [x,5,4,2,1,1,x,1,x,x]

Creo que lo he entendido correctamente, de todas formas, como puedes ver, las listas resueltas simplemente muestran cuántas entradas tenemos que examinar hasta encontrar un valor que sea >= para el límite superior, o <= para el límite inferior.

Entonces, la pregunta es, ¿cómo resolver este problema de manera razonablemente rápida para una gran cantidad de entradas? (Y en realidad, tengo 10 listas de límites superiores y 10 listas de límites inferiores… así que se necesita aún más eficiencia).

davy.ai

July 24, 2023 at 8:04 pm

Para resolver este problema de manera eficiente para una gran cantidad de entradas, podrías usar un diccionario de Python. El diccionario utilizaría el precio de la acción como clave y el valor sería el índice en la lista donde se encuentra ese precio de la acción.

Así es como podrías implementar esta solución:

def find_upper_lower_limits(prices, upper_limits, lower_limits):
    n = len(prices)
    solved_upper = [0] * n
    solved_lower = [0] * n

    # crear un diccionario para almacenar los índices de cada precio
    index_dict = {}
    for i in range(n):
        index_dict[prices[i]] = i

    # iterar por las listas de límites superior e inferior
    for limit_list, solved_list in zip([upper_limits, lower_limits], [solved_upper, solved_lower]):
        stack = []
        for i in range(n):
            while stack and limit_list[stack[-1]] <= limit_list[i]:
                index = stack.pop()
                solved_list[index] = i - index
            if not stack or limit_list[stack[-1]] > limit_list[i]:
                stack.append(i)

        while stack:
            index = stack.pop()
            solved_list[index] = n - index - 1

    return (solved_upper, solved_lower)

En esta implementación, primero creamos un diccionario llamado index_dict que utiliza el precio de la acción como clave y el índice en la lista prices como valor. Luego iteramos por las listas upper_limits y lower_limits y utilizamos una pila para llevar un seguimiento de los índices que necesitamos resolver.

Para cada índice, verificamos si el límite actual es mayor o igual que el límite en la parte superior de la pila. Si es así, sacamos el índice superior de la pila y calculamos la solución para ese índice. Continuamos sacando índices hasta que el límite en la parte superior de la pila sea mayor que el límite actual. En ese momento, agregamos el índice actual a la pila.

Después de recorrer las listas de límites y sacar elementos de la pila, nos quedan los índices que no tenían una solución porque no había un límite superior (o inferior) en los índices restantes. Para estos índices, simplemente calculamos la diferencia entre el índice y el final de la lista.

Esta implementación tiene una complejidad temporal de O(n), lo cual debería ser razonablemente rápido para listas de 5 millones de entradas. Al utilizar un diccionario para buscar rápidamente el índice de un precio de acción dado, podemos evitar hacer una búsqueda lineal en la lista prices para cada límite.

Answer

davy.ai

July 24, 2023 at 8:04 pm
Para resolver este problema de manera eficiente para una gran cantidad de entradas, podrías usar un diccionario de Python. El diccionario utilizaría el precio de la acción como clave y el valor sería el índice en la lista donde se encuentra ese precio de la acción.

Así es como podrías implementar esta solución:
```
def find_upper_lower_limits(prices, upper_limits, lower_limits):
    n = len(prices)
    solved_upper = [0] * n
    solved_lower = [0] * n

    # crear un diccionario para almacenar los índices de cada precio
    index_dict = {}
    for i in range(n):
        index_dict[prices[i]] = i

    # iterar por las listas de límites superior e inferior
    for limit_list, solved_list in zip([upper_limits, lower_limits], [solved_upper, solved_lower]):
        stack = []
        for i in range(n):
            while stack and limit_list[stack[-1]] <= limit_list[i]:
                index = stack.pop()
                solved_list[index] = i - index
            if not stack or limit_list[stack[-1]] > limit_list[i]:
                stack.append(i)

        while stack:
            index = stack.pop()
            solved_list[index] = n - index - 1

    return (solved_upper, solved_lower)
```
En esta implementación, primero creamos un diccionario llamado index_dict que utiliza el precio de la acción como clave y el índice en la lista prices como valor. Luego iteramos por las listas upper_limits y lower_limits y utilizamos una pila para llevar un seguimiento de los índices que necesitamos resolver.

Para cada índice, verificamos si el límite actual es mayor o igual que el límite en la parte superior de la pila. Si es así, sacamos el índice superior de la pila y calculamos la solución para ese índice. Continuamos sacando índices hasta que el límite en la parte superior de la pila sea mayor que el límite actual. En ese momento, agregamos el índice actual a la pila.

Después de recorrer las listas de límites y sacar elementos de la pila, nos quedan los índices que no tenían una solución porque no había un límite superior (o inferior) en los índices restantes. Para estos índices, simplemente calculamos la diferencia entre el índice y el final de la lista.

Esta implementación tiene una complejidad temporal de O(n), lo cual debería ser razonablemente rápido para listas de 5 millones de entradas. Al utilizar un diccionario para buscar rápidamente el índice de un precio de acción dado, podemos evitar hacer una búsqueda lineal en la lista prices para cada límite.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

¿Cómo puedo encontrar eficientemente las distancias desde cada valor hasta el siguiente valor inferior/superior?

Answer

davy.ai