Maneira mais eficiente de atender pedidos

Considere duas 2D (a matriz de compra) e (a matriz de venda) em que cada elemento está associado a uma matriz de valores de ponto flutuante e a cada valor de ponto flutuante, por sua vez, está associado a uma matriz de números inteiros.$B_{ij}$$S_{ij}$$i^{th}$

Por exemplo

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
          ] 
] 

e similarmente para a matriz de venda.

Isso é semelhante a um sistema de associação de pedidos de uma bolsa de valores / mercadorias

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

Qual é a maneira mais rápida conhecida de resolver o seguinte problema:

Entrada: Comprar série , array Sell Problema: Decida wether existem e com e .$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$

Em resumo, qual é a maneira mais complicada de corresponder aos pedidos de uma troca?

Atualização em resposta a comentários

Vamos dizer que a MSFT tem 25 ações a US $ 60 a serem vendidas e existe um comprador que está disposto a oferecer US $ 61 por 10 ações da MSFT. Em seguida, o comprador recebe 10 compartilhamentos a $ 60 e o livro de pedidos de compra fica vazio enquanto o livro de pedidos de venda agora é atualizado com nova quantidade - 15 compartilhamentos a $ 60.

Agora, pelo contrário, a MSFT tem 25 ações a $ 60 a serem compradas e há um vendedor disposto a receber $ 61 por 10 ações da MSFT. A negociação não será executada porque o vendedor está exigindo um mínimo de US $ 61 e o comprador está oferecendo um máximo de US $ 60. Os pedidos agora são armazenados e aguardam até que novos pedidos sejam recebidos.

(Esse é o princípio da ordem limite , em que o vendedor especifica o preço mínimo pelo qual está disposto a vender e o comprador especifica o preço máximo pelo qual está disposto a comprar).

Após a execução, o livro de pedidos de venda será (25-10)[email protected] enquanto o livro de pedidos de compras estará vazio (10-10) = 0.

Mantenha seu livro de pedidos de compra como uma variedade de empresas. Para cada empresa, mantenha uma fila de preços prioritária (máx. Para compra e mín. Para venda). Para cada preço, mantenha uma fila de pedidos.

Para verificar se há ordens correspondentes, para cada empresa, chamada find-min()e find-max()sobre a empresa na matriz vender e comprar matriz para encontrar os melhores preços de compra / venda. Se max> min, tente atender o pedido. Para atender ao pedido, retire os elementos de suas filas de compra e venda para essa empresa e preço, até que uma das filas de preços esteja vazia. Quando a fila de preços estiver vazia, exclua o elemento correspondente da fila de prioridade e execute a verificação novamente.

Essa estratégia custa tempo constante por pedido e por alteração de preço, em que é o número de preços da empresa .$O(\log p_i)$$p_i$$i$