La forma más eficiente de hacer coincidir los pedidos

Considere dos 2D-Array (la matriz de compra) y (la matriz de venta) donde cada elemento está asociado con una matriz de valores de coma flotante y cada uno de los valores de coma flotante, a su vez, está asociado con una matriz de enteros.$B_{ij}$$S_{ij}$$i^{th}$

Por ejemplo

B = [ 
  0001 => [ 32.5 => {10, 15, 20}, 
            45.2 => {48, 16, 19}, 
            ...,
            k1
          ], 
  0002 => [ 35.6 => {17, 35, 89}, 
            68.7 => {18, 43, 74}, 
            ...,
            k2
          ] 
] 

y de manera similar para la matriz de venta.

Esto es similar a un sistema de asociación de pedidos de una bolsa de valores

BuyOrderBook = [
                 CompanyName => [
                                 Price1 => [Qty1, Qty2...],
                                 Price2 => [Qty1, Qty2...]
                                ]
                 SecondCompany = [...]
               ]

¿Cuál es la forma más rápida conocida para resolver el siguiente problema:

Entrada: Comprar matriz , Vender matriz Problema: Decidir si hay y con y .$B$$S$
$(c_1 \Rightarrow p_1 \Rightarrow q_1) \in B$$(c_2 \Rightarrow p_2 \Rightarrow q_2) \in S$$q_1, q_2 > 0$$p_2 \geq p_1$

En resumen, ¿cuál es la mejor manera de hacer coincidir las órdenes de un intercambio?

Actualización en respuesta a comentarios

Digamos que MSFT tiene 25 acciones a $ 60 para vender y hay un comprador que está dispuesto a ofrecer $ 61 por 10 acciones de MSFT. Luego, el comprador obtiene 10 acciones a $ 60 y el libro de órdenes de compra se vacía, mientras que el libro de órdenes de venta ahora se actualiza con una nueva cantidad: 15 acciones a $ 60.

Ahora tome el caso inverso, MSFT tiene 25 acciones a $ 60 para comprar y hay un vendedor que está dispuesto a recibir $ 61 por 10 acciones de MSFT. Entonces, el intercambio no se ejecutará porque el vendedor exige un mínimo de $ 61 y el comprador ofrece un máximo de $ 60. Los pedidos ahora se almacenan y esperan hasta que se reciban nuevos pedidos.

(Este es el principio de orden límite , donde el vendedor especifica el precio mínimo al que está dispuesto a vender y el comprador especifica el precio máximo al que está dispuesto a comprar).

Después de la ejecución, el libro de órdenes de venta será (25-10)[email protected] mientras que el libro de órdenes de compra estará vacío (10-10) = 0.

Mantenga su libro de órdenes de compra como una variedad de compañías. Para cada empresa, mantenga una cola de precios prioritaria (máximo para comprar y mínimo para vender). Para cada precio, mantenga una cola de pedidos.

Para verificar las órdenes coincidentes, para cada compañía, llame find-min()y find-max()en la compañía en la matriz de venta y matriz de compra para encontrar los mejores precios de compra / venta. Si max> min, intente completar el pedido. Para completar el pedido, extraiga elementos de sus colas de compra y venta para esa compañía y precio, hasta que una de sus colas de precios esté vacía. Cuando la cola de precios esté vacía, elimine el elemento correspondiente de su cola de prioridad y vuelva a realizar la verificación.

Esta estrategia cuesta tiempo constante por pedido y por cambio de precio, donde es el número de precios para la empresa .$O(\log p_i)$$p_i$$i$