¿Existe un buen algoritmo para verificar los cambios en los datos durante un período de tiempo específico?

Question

Tenemos alrededor de 7k productos financieros cuyos precios de cierre teóricamente deberían subir y bajar dentro de un cierto rango de porcentaje durante un período de tiempo definido (por ejemplo, una semana o un mes).

Tengo acceso a un sistema interno que almacena estos precios históricos (¡no una base de datos relacional!). Me gustaría producir un informe que enumere cualquier producto cuyo precio no se haya movido en absoluto o inferior al 10% durante el período de tiempo.

No puedo simplemente comparar el primer valor (día 1) con el valor al final (día n) ya que el precio podría haber retrocedido a lo que era el último día que daría lugar a un falso positivo mientras que el precio del producto podría haber aumentado en algún punto intermedio, por supuesto.

¿Existen algoritmos establecidos para hacer esto en un tiempo de cálculo razonable?

Answer 1

Si necesita verificar esto con frecuencia (para un gran número de intervalos, como diariamente el año pasado y para el mismo conjunto de productos), puede almacenar los valores altos y bajos de cada artículo por semana/mes . Al combinar los límites semanales y/o mensuales correctos con algunos datos brutos en los bordes del intervalo, puede obtener el valor mínimo y máximo durante el intervalo.

Answer 2

No hay ninguna manera de hacer esto sin mirar todos los días.

Supongamos que los datos se ve como tal:

oooo0oooo 

Con que un día pico en el medio. No vas a atraparlo a menos que revises el día en que ocurre el aumento, en otras palabras, debes verificar todos los días.

Answer 3

Si puede agregar datos a kdb (es decir, no está limitado al acceso de lectura) puede considerar agregar el "número de días desde el último cambio de precio" como un nuevo conjunto de datos (es decir, un número por instrumento financiero) . Una tarea diaria luego tomaría la marca de hoy y la de ayer, y actualizaría los números almacenados. Del mismo modo, podría mantener los máximos y mínimos recientes (último mes, último año) en kdb. Tendría que ejecutar un trabajo sobre el conjunto de datos más grande para inicializar los valores inicialmente, pero entonces sus actualizaciones diarias implicarán mucha menos información.

Recomienda que si adopta algo como esto, tenga alguna manera de volver a ejecutar la totalidad o parte del conjunto de datos (por ejemplo, para agregar un nuevo producto).

Por último, ¿está normalizada la historia con respecto a los precios actuales? (es decir, se tienen en cuenta las revalorizaciones de splits de acciones o similares). De lo contrario, necesitarías detectar estas discontinuidades y dividirlas.

EDITAR

yo investigo usng kdb+/Q para implementar el procesamiento de señales, en lugar de la extracción de los datos en bruto a una aplicación Java. Como dices, es altamente eficiente.

Answer 4

Puede hacer esto si puede realizar un seguimiento del valor mínimo y máximo del precio durante el intervalo de tiempo; esto supone que el intervalo de tiempo no se cambia constantemente. Una forma de realizar un seguimiento de los valores mínimos y máximos de un conjunto cambiante de elementos es con dos montones colocados 'back to back': puede almacenar esto y algunos punteros necesarios para encontrar y eliminar elementos antiguos en una o dos matrices en su tienda . La idea de poner dos montones una detrás de la otra está en Knuth's Art of Computer Programming Vol 3 como Exercise 31 sección 5.2.3. Knuth llama a este tipo de bestia Priority Dequeue, y parece que se puede buscar.Min y Max están disponibles a un costo constante. El costo de modificarlo cuando llega un nuevo precio es log n, donde n es el número de elementos almacenados.