La implementación de estructuras de datos en un orden de Límite de libro

Question

Estoy trabajando en la implementación de un 'LOB' y estoy siendo muy cuidadoso acerca de la elección de mis datos-estructuras con el fin de maximizar el rendimiento.

Con F# como un ejemplo, tengo que considerar una Lista versus Matriz para la celebración de 'Ofertas' y 'Pide'.

Debido a que estas listas se actualizan muy rápido, y a las órdenes que se deben remover, agregar, actualizar de forma rápida, yo creo que 'Matriz' a causa de 'eficiente de acceso aleatorio'.

Dicho esto, las Listas (por separado-vinculado en un lenguaje funcional como F#) parecen ser más versátil, y más rápido para sumar y restar de la 'cabeza' de la lista, pero no bien necesario para acceso aleatorio?

Pensamientos, estoy en el camino correcto?

Answer 1

He aquí un blog con una visión general de algunas de las posibles implementaciones.

howtohft_howtobuildafastlimitorderbook - (espejo de la publicación original)

La publicación fue originalmente en el sitio web www.quantcup.org - este sitio es la venta, pero os dejo el roto URL para ayudar a los futuros buscadores:

Answer 2

yo no soy un F# experto, pero cuando se trata de rendimiento y la seguridad de los subprocesos intentar lista ordenada o hashset. lista ordenada si los datos debe ser ordenada (que se clasifique cuando se añade a la lista), de lo contrario hashset, sin ordenar por lo tanto un mejor rendimiento. ambos son genéricos.

además yo creo que necesita hilo de seguridad a la hora de leer/escribir/actualización de sus datos en este caso el de arriba le dará el rendimiento y la seguridad que usted necesita. si recuerdo correctamente la tabla hash darle la idénticos o cerca de los tiempos como aparece en la página proporcionada por bellamyj arriba.

Answer 3

F# te ofrece muchas estructuras de datos para colecciones, pero en la programación funcional, intenta tener inmutable estructuras de datos, tales como el F# List. Resulta bastante útil si quieres hacer algo de computación en paralelo, por ejemplo.

Usted puede echar un vistazo a mi post sobre LO que es probablemente donde usted puede preguntar a su pregunta de un modo más genérico, tales como "¿Cuál es la mejor estructura de datos a utilizar en F# si me necesitan acceso rápido a los datos?"

Answer 4

Yo no estoy familiarizado con F#. Me han puesto en práctica muchas veces en C++. Me gustaría ir con longitud fija de matrices. Fr me desempeño es de suma importancia. En C++, uno es mejor manejo de los agujeros de la asignación de memoria en el montón y se añade la complejidad de un error de caché.

Answer 5

Me gustaría realmente no molestar con F# estructuras de datos para este - muchos de ellos son realmente más lento que la ordinaria .NETO de las colecciones. Mi enfoque es el uso de SortedDictionary<price,volume> de ofertas y pregunta. De esa manera, sabrá siempre los mejores precios en el mercado.

Por supuesto, lo anterior supone que no está preocupado con el hilo de seguridad y la construcción de la cartera de pedidos en el mismo hilo, que generalmente es una sensata de la asunción.