Le moyen le plus efficace pour faire correspondre les commandes

Considérons deux tableaux 2D $B_{ij}$ (le tableau d'achat) et $S_{ij}$ (le tableau de vente) où chaque $i^{th}$ L'élément est associé à un tableau de valeurs à virgule flottante et chacune des valeurs à virgule flottante, à son tour, est associée à un tableau d'entiers.

Par exemple

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

et de même pour le tableau de vente.

Cela s'apparente à un système d'association d'ordres d'une bourse de valeurs / matières premières

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

Quel est le moyen le plus rapide connu pour résoudre le problème suivant:

Entrée: acheter un tableau$B$, Vendre un tableau $S$
Problème: décidez s'il y a$(c_1 \Rightarrow p_1 \Rightarrow q_1) \in B$ et $(c_2 \Rightarrow p_2 \Rightarrow q_2) \in S$ avec $q_1, q_2 > 0$ et $p_2 \geq p_1$.

En bref, quelle est la meilleure façon de faire correspondre les commandes d'un échange?

Mise à jour en réponse aux commentaires

Disons que MSFT a 25 actions @ 60 $ à vendre et qu'il y a un acheteur qui est disposé à offrir 61 $ pour 10 actions de MSFT. Ensuite, l'acheteur obtient 10 actions @ 60 $ et le carnet d'ordre d'achat devient vide tandis que le carnet d'ordre de vente est maintenant mis à jour avec une nouvelle quantité - 15 actions @ 60 $ .

Prenons maintenant le cas inverse, MSFT a 25 actions @ 60 $ à acheter et il y a un vendeur qui est disposé à recevoir 61 $ pour 10 actions de MSFT. Ensuite, la transaction ne sera pas exécutée car le vendeur exige un minimum de 61 $ et l'acheteur offre un maximum de 60 $ . Les commandes sont désormais stockées et attendent jusqu'à ce que de nouvelles commandes soient reçues.

(Il s'agit du principe de la commande à cours limité , où le vendeur spécifie le prix minimum auquel il est disposé à vendre et l'acheteur spécifie le prix maximum auquel il est disposé à acheter).

Après exécution, le carnet d'ordre de vente sera (25-10)[email protected] tandis que le carnet d'ordre d'achat sera vide (10-10) = 0.

Tenez votre carnet de commandes en tant que groupe d'entreprises. Pour chaque entreprise, gardez une file d'attente de prix prioritaire (max pour acheter et min pour vendre). Pour chaque prix, gardez une file d'attente de commandes.

Pour vérifier les commandes correspondantes, pour chaque entreprise, appelez find-min()et find-max()sur l'entreprise dans le tableau de vente et achetez le tableau pour trouver les meilleurs prix d'achat / vente. Si max> min, essayez de remplir la commande. Pour exécuter la commande, retirez les éléments de vos files d'attente d'achat et de vente pour cette entreprise et ce prix, jusqu'à ce que l'une de vos files d'attente de prix soit vide. Lorsque la file d'attente des prix est vide, supprimez l'élément correspondant de sa file d'attente prioritaire et effectuez à nouveau la vérification.

Cette stratégie coûte un temps constant par commande, et $O(\log p_i)$ par changement de prix, où $p_i$ est le nombre de prix pour l'entreprise $i$.