Cuál es una estructura de datos eficiente para modelar la cartera de pedidos de precios y cantidades para asegurar:
Los detalles dependen de si está implementando para acciones (basado en órdenes) o futuros (basado en niveles). Yo recomiendo https://web.archive.org/web/20110219163448/http://howtohft.wordpress.com/2011/02/15/how-to-build-a-fast-limit-order-book/ para una visión general de una buena arquitectura para la primera.
A partir de ahí, sin embargo, he descubierto que el uso de estructuras de datos basadas en arrays en lugar de punteros proporciona un rendimiento más rápido. Esto se debe a que para las CPUs modernas con pipelining y caché, las bifurcaciones y las desreferencias (especialmente de la memoria sin caché) son los mayores asesinos del rendimiento porque introducen dependencias de datos que resultan en estancamientos de pipeline / memoria.
Si puede, también debería optimizar para el intercambio particular. Por ejemplo, resulta que, la última vez que lo comprobé, Nasdaq genera los ID de las órdenes de forma incremental empezando por un número pequeño, por lo que puedes almacenar todas las órdenes en un array gigante en lugar de en una tabla hash. Esto es realmente amigable para la caché y el TLB en comparación con una tabla de hash, ya que la mayoría de las actualizaciones tienden a suceder a las órdenes recientemente referenciadas.
Hablando desde la experiencia con la renta variable (basada en órdenes), mi arquitectura preferida es:
std::unordered_map o std::vector si se puede hacer, como en el caso del Nasdaq).O(1) para un Order Execute o Order Reduce operación. Si quieres llevar un registro de la prioridad temporal también, puedes mantener punteros a la next y previous órdenes en la cola.vector para los niveles de precios de cada libro dará lugar a la más rápida media búsqueda de precios. Buscando linealmente desde el final de la vector es en promedio más rápido que una búsqueda binaria, también, porque la mayoría de las veces el precio deseado está sólo a unos pocos niveles como máximo desde el interior, y una búsqueda lineal es más fácil en el predictor de rama, el optimizador y la caché. Por supuesto, puede haber órdenes patológicas lejos del interior del libro, y un atacante podría enviar muchas actualizaciones al final del libro para ralentizar su implementación. En la práctica, sin embargo, la mayoría de las veces esto resulta en una caché amigable, casi O(1) aplicación para insert , lookup , update y delete (con el peor de los casos O(N) memcpy). Específicamente para una actualización de la mejor oferta y demanda (BBO), se puede conseguir una implementación que calcule la actualización en sólo unas pocas instrucciones (esencialmente añadiendo o borrando un elemento del final del vector ), o unas tres desreferencias.O(1) el mejor caso de comportamiento para la inserción, la búsqueda, el borrado y la actualización con constantes muy bajas (he calculado que es, en promedio, el costo de una sola búsqueda en la memoria principal, aproximadamente 60 ns). Por desgracia, se puede obtener O(N) comportamiento en el peor de los casos, pero con baja probabilidad y aún así con muy buenas constantes debido a la facilidad de uso de la caché, el TLB y el compilador. También es muy rápido, casi de forma óptima, en el caso de las actualizaciones de BBO, que es lo que suele interesar de todos modos.Tengo un aplicación de referencia aquí para el protocolo ITCH de Nasdaq que ilustra estas técnicas y otras más. El protocolo tiene una media de poco más de 61ns / tick (unos 16 millones de ticks / segundo), ya que sólo lleva la cuenta de la cantidad en cada nivel de precios y no la cola de órdenes, y no utiliza casi ninguna asignación, además de std::vector redimensionamiento.
Gracias. ¿podría explicar un poco más la diferencia entre la cartera de pedidos basada en niveles y la basada en órdenes?
Desde Copa Quant 1 era un motor eficiente de comparación de precios y tiempos, la estructura de datos del aplicación ganadora puede ser en parte lo que está buscando.
Si no, la configuración de LANGOSTA se supone que es rápido.
Muy bien. Estaba pensando en una simple implementación basada en un array. La mejor implementación en Quant Cup hace algo similar.
Sin embargo, hay que tener en cuenta que será menos óptimo cuando los niveles de precios sean escasos y nos preocupemos por cada nivel de precios.
El primer enlace de la respuesta está muerto. Por eso desaconsejamos las respuestas con enlaces.
Recientemente me he topado con esta pregunta tras necesitar hacer esto para realizar un análisis de microestructuras en tiempo real y he echado un vistazo a las distintas implementaciones posibles. Aquí están algunos de los pros / contras de cada implementación (voy a utilizar la terminología C / C ++):
Array: Tienes un array de structs ordenados desde el principio del libro (índice 0) hasta el peor (índice N). Tienes que preasignar el array para que sea lo suficientemente grande.
La inserción es O(LOG N) : Realiza una búsqueda binaria para encontrar el punto de inserción, luego realiza un memcpy para desplazar la cola del array. Finalmente, sobrescribe el elemento en el punto de inserción.
La búsqueda es O(1) : Sus índices se corresponden directamente con los niveles de profundidad del mercado. Sólo tienes que saltar a donde quieras.
Las eliminaciones son O(LOG N) : Buscas el orden que quieres borrar, luego realizas un memcpy desplazando todo hacia atrás en 1 índice.
Las actualizaciones son, en el peor de los casos, una supresión + una inserción . En el mejor de los casos, se comprueba si la orden actualizada cambia de orden.
Pros:
Contras:
Lista de enlaces simples : El mismo concepto que un array (la cabeza de la lista enlazada es la parte superior del libro, la cola es la parte inferior del libro).
La inserción es O(N) : Tiene que buscar en la lista, actualizar el "puntero siguiente" de su nueva orden al "puntero siguiente" de la orden anterior, actualizar el "puntero siguiente" de la orden anterior para que apunte a su nueva comilla, y actualizar la cabeza/cola/longitud de la lista si procede.
La búsqueda es O(N) : La parte superior del libro es trivial O(1) ya que es la cabeza de la lista. De lo contrario, tendrá que buscar a través de la lista.
El borrado es O(N) : Tienes que buscar en la lista para encontrar el punto de destino. A continuación, intercambia dos punteros.
Las actualizaciones son un borrado + una inserción en el peor de los casos . En el mejor de los casos es O(1) suponiendo que se conozca el índice correcto (ya profundizaré en esto en esta respuesta)
Unas cuantas optimizaciones le dan un rendimiento aceptable:
Ventajas: - No se repite la copia una vez que se busca en el lugar correcto - Las actualizaciones/inserciones/consultas son muy rápidas si la mayoría de las operaciones están cerca de la cabeza de la lista
Contras:
Al final, he comprobado que la versión de matriz tiene el mejor rendimiento medio si está de acuerdo con la prioridad de precio/cantidad . Si necesita la precisión de la prioridad precio/cantidad/tiempo, las matrices son demasiado grandes.
Si te parece bien la prioridad precio/cantidad: Podemos utilizar la propiedad de que las cantidades tienden a ser muy similares para los valores para limitar el número de operaciones de copia:
Cree una matriz de 4 veces el tamaño del rango de precios posible esperado para el día (obviamente tendrá que reasignar su matriz si ocurre algo salvaje). Coloque el nivel de precios correspondiente a la apertura prevista en el centro de la matriz. Cada vez que reciba una nueva orden, el índice deseado se acercará al número de céntimos de diferencia entre este precio y el de la orden. A continuación, puede mirar hacia adelante/atrás para ver si el nivel de precio/cantidad existe. Si no existe, tendrá que desplazar la matriz mediante una copia. Pero si existe, ya está todo listo. Este enfoque de "matriz centrada" significa que después de unos minutos de citas, tendrá la gran mayoría de sus niveles de precio/cantidad definidos. Este método sólo funciona si está de acuerdo con la prioridad de precio/cantidad. Si necesita una prioridad de precio/cantidad/tiempo, probablemente deba optar por la lista enlazada.
Las inserciones y eliminaciones para las implementaciones de arrays son O(N), no O(logN) debido a las operaciones de copia para hacer el desplazamiento de memcpy. Además, dado que las operaciones suelen ocurrir en la parte superior del libro, muy a menudo estarás desplazando (es decir, cargando en la caché) todo el array.
No sé en qué contexto quieres implementar un motor de comparación (ME). Pero en mi opinión los dos buenos retos en este contexto son:
El último punto se refiere a la simulación de un día en pocos segundos.
Para responder más directamente a su pregunta, la referencia es El código de la isla de Josh Levine en foxpro . Levin's ha sido uno de los pioneros en el aumento del comercio electrónico. No es sólo una especificación ejecutable, sino un trozo de historia.
Si se asume que la mayoría de las actualizaciones se producirán cerca de la parte superior del libro (una suposición justa), una lista vinculada ordenada por niveles de precios será muy eficiente.
Puede comprobar CoralMD para ver un ejemplo de implementación de un libro de datos de mercado muy rápido y libre de basura que proporciona no sólo el global del mercado (todas las bolsas), sino también una por intercambio vista del libro. También proporciona la infra-estructura para escriba las fuentes de intercambio y a distribuir datos de mercado internamente.
Descargo de responsabilidad: Soy uno de los desarrolladores de CoralMD
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.
