Aller au contenu
Criée

Le carnet, une structure triée

Deux côtés triés par prix puis par rang, agrégés en niveaux, et le coût des structures possibles.

Leçon 311 min

À la fin de cette leçon

  • Écrire la clé de tri prix puis rang de chaque côté du carnet
  • Lire la vue agrégée et la fourchette renvoyées par le moteur
  • Estimer le coût d’une insertion, tableau trié ou niveaux et recherche dichotomique
Dans cette leçon5

Un carnet d'ordres est « l'ensemble de tous les ordres actifs d'un marché à l'instant t » (Gould et al., 2013, section 2.1). Pour un développeur, c'est d'abord une structure de données : deux listes triées, une par côté, avec une clé de tri précise. Tout le moteur repose sur ce tri.

La clé de tri

La règle d'exécution est la priorité par le prix, puis par le temps : à prix égal, l'ordre arrivé le premier passe devant (AMF, « Choisir et passer un ordre de bourse »). L'ordre au marché est prioritaire sur l'ordre à prix limité (RG BVMAC 2025, art. 159).

Priorité prix puis temps

Règle de tri du carnet : le meilleur prix d'abord ; à prix égal, l'ordre arrivé le premier.

Le « meilleur prix » n'a pas le même sens des deux côtés. Côté achats, le meilleur est le plus haut ; côté ventes, le plus bas. La clé de tri est donc un couple [prix, rang], avec un sens de tri qui dépend du côté. Voici la fonction du moteur :

export function trierCote(ordres: Ordre[], sens: Sens): Ordre[] {
  const cle = (o: Ordre) =>
    o.limite === null ? (sens === 'achat' ? Infinity : -Infinity) : o.limite
  return [...ordres].sort((a, b) => {
    const pa = cle(a)
    const pb = cle(b)
    if (pa !== pb) return sens === 'achat' ? pb - pa : pa - pb
    return a.rang - b.rang
  })
}

Deux détails méritent l'attention. L'ordre au marché reçoit un prix fictif infini (+∞ à l'achat, -∞ à la vente) : il passe ainsi devant tous les ordres limités, sans cas particulier dans le comparateur. Et [...ordres] copie le tableau avant de trier, car Array.prototype.sort trie en place.

Deux camps face à face. À gauche, cinq caisses vertes d’acheteurs ; à droite, cinq caisses corail de vendeurs, de longueurs différentes selon la quantité proposée. En haut, les deux meilleurs prix : une main de chaque côté se tend vers l’autre, séparées par un petit vide, la fourchette.
Un carnet d’ordres comme un étal : les meilleurs prix en haut, face à face

Le tri, ordre après ordre

Envoyez les ordres un à un. À droite de chaque ligne, la clé [prix, rang] explique sa place. Regardez D, au même prix que A mais arrivé après, et G, l'ordre au marché.

Trier un carnet, ordre après ordre0/7

Carnet vide. Envoyez le premier ordre.

Achats

clé : prix décroissant, puis rang croissant

  1. vide

Ventes

clé : prix croissant, puis rang croissant

  1. vide

De mémoire : côté ventes, deux ordres à 10 100, rangs 2 et 6, et un ordre à 10 050, rang 5. Dans quel ordre sont-ils servis ?

Du carnet à l'écran : agréger par niveau

Un écran de cotation n'affiche pas les ordres un par un, mais des niveaux de prix : à chaque prix, la quantité totale et le nombre d'ordres. La revue de Gould appelle profondeur la somme des quantités à un prix donné, et fourchette l'écart entre le meilleur prix vendeur et le meilleur prix acheteur (section 2.1).

const carnet = new Carnet()
carnet.passer({ id: 'A', sens: 'achat', quantite: 40, limite: 9950 })
carnet.passer({ id: 'D', sens: 'achat', quantite: 15, limite: 9950 })
carnet.passer({ id: 'E', sens: 'vente', quantite: 20, limite: 10050 })

carnet.vue()
// { achats: [{ prix: 9950, quantite: 55, ordres: 2 }],
//   ventes: [{ prix: 10050, quantite: 20, ordres: 1 }] }
carnet.fourchette()
// { achat: 9950, vente: 10050, ecart: 100 }

Par défaut, vue() montre cinq niveaux. Le projet de 2008 prévoyait de diffuser les cinq meilleures limites agrégées (Instruction n°2, section 5) ; la valeur est un paramètre, pas une règle actuelle.

Un niveau de prix a sa propre vie : il naît avec le premier ordre à ce prix, grossit, recule quand un meilleur prix arrive, fond sous les exécutions, puis disparaît avec son dernier ordre. Suivez le niveau 9 950, encadré de jaune, et la file d'ordres qu'il contient.

La vie d’un niveau de prix1/6

Côté achats, vue()

9 95040 · 1 ordre(s)
A 40 · r1

Niveau 9 950

{
prix: 9950
quantite: 40
ordres: 1
}

carnet.passer({ id: 'A', achat, 40, 9950 })

9 950 : 40 titres

Le niveau naît avec un premier ordre.

Le coût de ce choix

Le moteur pédagogique stocke chaque côté dans un tableau non trié et appelle trierCote à chaque ordre entrant : O(n log n) par ordre, pour n ordres en attente. C'est lisible et suffisant pour quelques centaines d'ordres. Un moteur de production organiserait plutôt chaque côté en niveaux de prix triés, chaque niveau tenant une file « premier arrivé, premier servi » :

// Esquisse : un niveau = une file FIFO ; les niveaux restent triés
interface NiveauPrix { prix: number; file: Ordre[] }
interface Cote { niveaux: NiveauPrix[] } // achats : prix décroissant

Insérer revient alors à trouver le niveau (recherche dichotomique, O(log p) pour p niveaux) puis à ajouter en fin de file, O(1).

Nous n'avons trouvé aucune source fiable décrivant la structure de données du carnet de la BVMAC ou d'une autre plateforme. Les deux structures ci-dessus sont des choix de conception du moteur pédagogique, présentés pour leur coût, pas comme la façon dont fonctionne un système réel.

Plus loin

La clé [prix, rang] repose sur le rang entier choisi dans la leçon Modéliser un ordre. Reste à savoir ce que coûte ce tri, et ce qu'il ne protège pas.

Le coût réel d'un ordre. Dans le moteur pédagogique, passer trie le côté opposé à chaque ordre entrant (trierCote copie puis trie, O(n log n)), et chaque appel à vue() ou à fourchette() trie les deux côtés. Sur une séance de m ordres, le coût total croît comme m × n log n. Avec des niveaux déjà triés, trouver la place d'un prix devient une recherche dichotomique :

// Côté achats : niveaux triés par prix décroissant
function indexNiveau(niveaux: { prix: number }[], prix: number): number {
  let bas = 0
  let haut = niveaux.length
  while (bas < haut) {
    const milieu = (bas + haut) >> 1
    if (niveaux[milieu]!.prix > prix) bas = milieu + 1
    else haut = milieu
  }
  return bas
}

const niveaux = [{ prix: 10100 }, { prix: 10000 }, { prix: 9950 }]
indexNiveau(niveaux, 10000) // 1 : le niveau existe, l'ordre va en fin de file
indexNiveau(niveaux, 10050) // 1 : niveau neuf, inséré entre 10 100 et 10 000
indexNiveau(niveaux, 9900)  // 3 : niveau neuf, en dernière position

Pas à pas, pour 10 050 :

  1. bas = 0, haut = 3, milieu = 1 : 10 000 n'est pas supérieur à 10 050, donc haut = 1.
  2. milieu = 0 : 10 100 est supérieur à 10 050, donc bas = 1.
  3. bas === haut : la boucle s'arrête, l'indice vaut 1.

L'indice seul ne dit pas si le niveau existe : comparez niveaux[i]?.prix au prix cherché. Et insérer dans un tableau décale tout ce qui suit, O(p) ; un arbre équilibré évite ce décalage. Ce sont des choix de conception, sans source sur les plateformes réelles (voir l'encadré ci-dessus).

Un piège : ordres() rend les objets internes. trierCote copie le tableau, pas les ordres qu'il contient :

const c = new Carnet()
c.passer({ id: 'A', sens: 'achat', quantite: 40, limite: 9950 })
c.ordres().achats[0]!.quantite = 0 // un écran qui « corrige » un affichage
c.vue()        // { achats: [{ prix: 9950, quantite: 0, ordres: 1 }], ventes: [] }
c.fourchette() // { achat: 9950, vente: null, ecart: null }

Un niveau à quantité nulle apparaît dans la vue, et la fourchette affiche un meilleur achat qui n'existe plus. C'est la limite connue n° 1 de la fiche du contrat du moteur. Écrivez le test qui la révèle (modifier un ordre renvoyé, puis vérifier que vue() n'a pas changé) : il sera rouge, et c'est voulu.

De mémoire : pourquoi la clé de tri utilise-t-elle un rang entier plutôt qu'une heure ? Et que coûte, dans le moteur pédagogique, l'arrivée d'un ordre face à n ordres en attente ?

À toi de jouer

Côté ventes, quel ordre limité est le meilleur ?

1Côté ventes, quel ordre limité est le meilleur ?

Pourquoi trierCote donne-t-il un prix infini à l'ordre au marché ?

2Pourquoi trierCote donne-t-il un prix infini à l'ordre au marché ?

Deux achats au même prix : lequel passe devant ?

3Deux achats au même prix : lequel passe devant ?

Que renvoie fourchette() quand un côté est vide ?

4Que renvoie fourchette() quand un côté est vide ?

Dans le moteur, modifier un ordre renvoyé par ordres()...

5Dans le moteur, modifier un ordre renvoyé par ordres()...

Niveaux 10 100, 10 000 et 9 950 côté achats : où indexNiveau place-t-il 10 050 ?

6Niveaux 10 100, 10 000 et 9 950 côté achats : où indexNiveau place-t-il 10 050 ?

À lire ensuite : Gould et al., « Limit order books », Quantitative Finance, 2013

Une question ? Posez-la à votre enseignant, ou à un assistant IA en lui donnant le titre de cette leçon.

Partager :WhatsAppLinkedIn

Pour aller plus loin