Árboles rojos y negros para el libro de órdenes limitadas

Question

¿Por qué se sugiere el uso de árboles negros rojos/árboles binarios equilibrados para los niveles en un libro de órdenes limitadas?

¿Por qué son algorítmicamente ideales?

Answer 1

¿Por qué se sugiere el uso de árboles negros rojos/árboles binarios equilibrados para los niveles en un libro de órdenes limitadas?

Porque la gente es poco original y sigue haciendo referencia a la misma entrada del blog.

¿Por qué son algorítmicamente ideales?

No son necesariamente ideales. De hecho, rara vez se utilizan en sistemas comerciales de producción con requisitos de baja latencia. Sin embargo, su fuente probablemente tuvo las siguientes consideraciones:

1. Se les dio más un objetivo de ingeniería que de comercio. Sin las restricciones comerciales o las consultas que se supone que hay que optimizar, una prioridad razonable es optimizar para el peor caso de tiempo de ejecución de las inserciones y eliminaciones, ya que las inserciones y eliminaciones suelen dominar las ejecuciones .
2. Diseñaban esta estructura de cartera de pedidos basándose en datos de muestra de una clase de activos con precios escasos como las acciones.

Debido a (1) y (2), debían tener en cuenta las siguientes propiedades del mercado:

3. Los nuevos precios se suelen insertar hacia el exterior del libro ya que (i) los niveles interiores tienden a ser densos y (ii) las inserciones hacia el interior son susceptibles de ser igualadas y truncadas por el libro contrario.
4. La formación de un nuevo nivel da una importante prioridad en la cola y las órdenes hacia el exterior tienen más valor temporal, por lo que es menos probable que los niveles de precios sean eliminados por cancelaciones de órdenes hacia el exterior, y más probable que sean eliminados por cancelaciones o ejecuciones hacia el interior del libro .

(3) y (4) promoverían un BST desequilibrado y alto, que tiene un tiempo de ejecución amortizado mucho peor que su forma idealizada. Hay varias formas de mitigar esto. El auto-equilibrio es una solución ingenua, ya que los árboles rojo-negro están muy implementados en las bibliotecas de contenedores y una forma sencilla de garantizar $\mathbb{O}\left(\log n\right)$ inserciones y supresiones de niveles de precios.

---

Al evaluar la estructura de datos óptima, yo tendría en cuenta los tres temas principales siguientes.

1. Empezar con el caso de uso de la empresa

Como por ejemplo:

• ¿Qué consultas deben optimizarse para su aplicación?
• La escasez del libro.
• Distribución estadística de los eventos del libro.

Por ejemplo:

• En los instrumentos de opción En el caso de los eventos de orden, es posible que haya muy pocos eventos de orden, por lo que puede ser más barato almacenar todo en arrays y recorrerlos linealmente.
• En los contratos de futuros líquidos La mayoría de los eventos sólo afectan a unos pocos cientos de niveles de precios, y las bandas de precios pueden darle un límite a los niveles que realmente le interesan, por lo que es posible preasignar los niveles en una matriz y representar los precios de los índices como un desplazamiento desde algún estado inicial en número de ticks.
• Algunas estrategias de negociación necesitan actuar muy rápidamente ante el cambio de la parte superior del libro, y pueden permitirse aplazar las inserciones o eliminaciones de nivel fuera del BBO hasta más tarde, por lo que no es importante optimizar para las inserciones o eliminaciones de nivel.

2. Comprender el protocolo de mensajería y la alimentación de datos

Por ejemplo:

1. Algunos flujos de datos son muy abundantes, por lo que podría diseñar su aplicación para que se vacíen todos los eventos de datos antes de realizar la ruta crítica de su acción comercial (por ejemplo, colocación de pedidos, actualización de modelos). La estructura óptima de la cartera de pedidos puede ser diferente si los eventos se producen por lotes.
2. Los eventos sucesivos en la alimentación de datos pueden tener un cierto orden de precios.

3. Diseño de hardware

En la práctica, cuando se opera a escalas de tiempo de acceso a la memoria o a la caché, o cuando se trata de un pequeño número de eventos en relación con el tamaño de la caché, la complejidad temporal asintótica suele desaparecer y es más importante observar la implementación real y los puntos de referencia reales, y codiseño su cartera de pedidos para la arquitectura en la que se está ejecutando.

En estos casos, una matriz simple o un vector con patrones de acceso lineales a menudo superará a cualquier estructura de datos compleja con un mejor tiempo de ejecución asintótico porque una matriz simple facilita la explotación de las optimizaciones de hardware que son más importantes:

• Localidad
• Prefetching
• Canalización de instrucciones
• Ajustar todos los datos relevantes/cualificados en menos "páginas" que tengan que ascender en la jerarquía de memoria, por ejemplo, no perseguir punteros a través de regiones no contiguas de la memoria.
• Intrínsecos SIMD.

¿Cómo se traduce esto en el diseño de libros de pedidos? Por ejemplo:

• La implementación de C++ STL de unordered_map suele tener peor rendimiento que map para la búsqueda de ID de órdenes de instrumentos con un número reducido de órdenes.
• Es posible representar cada nivel de precios con una lista intrusiva doblemente vinculada, que tiene $\mathbb{O}\left(1\right)$ búsqueda de los nodos vecinos, por lo que se puede desvincular un pedido que fue eliminado en $\mathbb{O}\left(1\right)$ . Pero a menudo se obtendrá un mejor rendimiento creando una lista enlazada de arrays preasignados, y eliminando las órdenes marcándolas con una bandera de lápida.

---

En muchas de las situaciones que he descrito anteriormente, un lista enlazada de matrices o un matriz de matrices superará a un diseño de propósito general con árboles rojo-negro de listas intrusivas doblemente enlazadas.

Answer 2

Hay una diferencia entre comprender la dinámica de la LOB y utilizar una solución algorítmica para captar esta dinámica.

Cómo evoluciona la LOB. Hace tiempo que comprendimos (véase los artículos de Jeremy Large) que una cadena de Markov sobre "imágenes" de la LOB sería un modelo interesante. Después de algunos años de modelar la dinámica de la LOB con procesos de Hawkes (véase, por ejemplo, el artículo de Emmanuel Bacry y sus coautores), y gracias al interesante impulso de Rama Cont y Adrien de Larrard, llegamos a la idea de que los procesos de Poisson heterogéneos para modelar cada evento (inserción, cancelación, mercado) eran realmente buenos. Sobre todo si las intensidades de estos procesos son funciones del estado del libro de órdenes (es decir, de las "imágenes" a las que me refería). Véase el Modelo de cola reactiva . Esto incorpora el poder de predicción del desequilibrio de la cartera de pedidos.

Cómo comprimir la dinámica. Creo que las intensidades son una buena manera de seguir la dinámica. Sólo si se quiere asociar la la mejor acción siguiente (entre insertar/cancelar/permanecer/comercializar) que de alguna manera un árbol de decisión, es decir, un árbol binario. Puede ser útil. Pero yo sugeriría apoyarse en el aprendizaje por refuerzo (ver los ejemplos de este documento ) para elegir las ramas de su árbol.

[EDITAR] Si su objetivo es implementar un motor correspondiente Pero esto es otra historia. Es algo que tuve que hacer para depurar o backtestar algoritmos de trading. Yo diría que en teoría sólo se necesita algo equivalente a una lógica de búsqueda rápida, y sí leer-árbol negro es una solución que para. Lo importante es no rehacer la búsqueda cada vez que se quiera insertar un pedido en la lista de niveles de precios, puesto que ya está ordenada. La mayoría de los lenguajes de programación ya tienen una solución para eso (en python, por qué no usar simplemente un diccionario), pero si quieres hacerlo desde cero porque realmente te preocupa la velocidad de implementación, entonces podría ser una buena idea empezar a buscar en el precio medio (y no al precio más bajo o más alto), porque tiene más inserciones y actualizaciones de pedidos alrededor de la mitad.