1 votos

Efficiently Tracking Order Queue Position In a Limit Order Book Implementation

Hay muchos mensajes sobre diferentes formas de implementar libros de órdenes limitadas, aunque nunca veo ninguna discusión sobre cómo rastrear de manera eficiente la posición de una orden específica en la cola. Si quiero hacer preguntas como:

  1. ¿En qué posición está la orden x en la cola y?
  2. ¿Cuánto volumen hay delante y detrás de la orden x en la cola y?

La única forma que se me ocurre de hacer esto es actualizar cada orden en la cola con valores de seguimiento cada vez que ocurra una adición/modificación/cancelación. Pero esto implicaría iterar toda la cola cada vez. ¿Hay una forma mejor?

1voto

Diondon Puntos 1

Este es un problema clásico de suma de prefijos. Puedes:

  1. Almacenar los tamaños de las órdenes. Obtener la posición en O(n) y actualizar en O(1).
  2. Almacenar las sumas de prefijos. Obtener la posición en O(1) y actualizar en O(n).
  3. Usar un árbol de Fenwick. Hacer ambas en O(log n).

A menudo, las consideraciones prácticas favorecen el enfoque (2). ¿Por qué?

  • Usualmente obtener la posición es más urgente para la lógica de la aplicación que realizar la actualización. Puedes postergar la actualización después de calcular señales, tomar decisiones estratégicas o enviar mensajes de órdenes.
  • Las órdenes generalmente se toman desde la parte trasera de la cola y las cancelaciones suelen dominar las ejecuciones, por lo que la actualización promedio es mucho más económica que el peor caso.
  • La cola suele ser lo suficientemente corta como para que no haya muchas órdenes que recorrer.

Finanhelp.com

FinanHelp es una comunidad para personas con conocimientos de economía y finanzas, o quiere aprender. Puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X