8.5. heapq — File de priorité basée sur un tas

Code source : Lib/heapq.py

Ce module expose une implémentation de l’algorithme de file de priorité, basée sur un tas.

Les tas sont des arbres binaires pour lesquels chaque valeur portée par un nœud est inférieure ou égale à celle de ses deux fils. Cette implémentation utilise des tableaux pour lesquels tas[k] <= tas[2*k+1] et tas[k] <= tas[2*k+2] pour tout k, en commençant la numérotation à zéro. Pour contenter l’opérateur de comparaison, les éléments inexistants sont considérés comme porteur d’une valeur infinie. L’intérêt du tas est que son plus petit élément est toujours la racine, tas[0].

L’API ci-dessous diffère de la file de priorité classique par deux aspects : (a) l’indiçage commence à zéro. Cela complexifie légèrement la relation entre l’indice d’un nœud et les indices de ses fils mais est alignée avec l’indiçage commençant à zéro que Python utilise. (b) La méthode pop renvoie le plus petit élément et non le plus grand (appelé « tas-min » dans les manuels scolaires ; le « tas-max » étant généralement plus courant dans la littérature car il permet le classement sans tampon).

Ces deux points permettent d’aborder le tas comme une liste Python standard sans surprise : heap[0] est le plus petit élément et heap.sort() conserve l’invariant du tas !

Pour créer un tas, utilisez une liste initialisée à [] ou bien utilisez une liste existante et transformez la en tas à l’aide de la fonction heapify().

Les fonctions suivantes sont fournies :

heapq.heappush(heap, item)

Introduit la valeur item dans le tas heap, en conservant l’invariance du tas.

heapq.heappop(heap)

Extraie le plus petit élément de heap en préservant l’invariant du tas. Si le tas est vide, une exception IndexError est levée. Pour accéder au plus petit élément sans le retirer, utilisez heap[0].

heapq.heappushpop(heap, item)

Introduit l’élément item dans le tas, puis extraie le plus petit élément de heap. Cette action combinée est plus efficace que heappush() suivie par un appel séparé à heappop().

heapq.heapify(x)

Transforme une liste x en un tas, sans utiliser de tampon et en temps linéaire.

heapq.heapreplace(heap, item)

Extraie le plus petit élément de heap et introduit le nouvel élément item. La taille du tas ne change pas. Si le tas est vide, une exception IndexError est levée.

Cette opération en une étape est plus efficace qu’un appel à heappop() suivi d’un appel à heappush() et est plus appropriée lorsque le tas est de taille fixe. La combinaison pop/push renvoie toujours un élément du tas et le remplace par item.

La valeur renvoyée peut être plus grande que l’élément item ajouté. Si cela n’est pas souhaitable, utilisez plutôt heappushpop() à la place. Sa combinaison push/pop renvoie le plus petit élément des deux valeurs et laisse la plus grande sur le tas.

Ce module contient également trois fonctions génériques utilisant les tas.

heapq.merge(*iterables, key=None, reverse=False)

Fusionne plusieurs entrées ordonnées en une unique sortie ordonnée (par exemple, fusionne des entrées datées provenant de multiples journaux applicatifs). Renvoie un iterator sur les valeurs ordonnées.

Similaire à sorted(itertools.chain(*iterables)) mais renvoie un itérable, ne stocke pas toutes les données en mémoire en une fois et suppose que chaque flux d’entrée est déjà classé (en ordre croissant).

A deux arguments optionnels qui doivent être fournis par mot clef.

key spécifie une key function d’un argument utilisée pour extraire une clef de comparaison de chaque élément de la liste. La valeur par défaut est None (compare les éléments directement).

reverse, une valeur booléenne. Si elle est True, la liste d’éléments est triée comme si toutes les comparaisons étaient inversées.

Modifié dans la version 3.5: Ajout des paramètres optionnels key et reverse.

heapq.nlargest(n, iterable, key=None)

Return a list with the n largest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key, reverse=True)[:n].

heapq.nsmallest(n, iterable, key=None)

Return a list with the n smallest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in iterable (for example, key=str.lower). Equivalent to: sorted(iterable, key=key)[:n].

Les deux fonctions précédentes sont les plus efficaces pour des petites valeurs de n. Pour de grandes valeurs, il est préférable d’utiliser la fonction sorted(). En outre, lorsque n==1, il est plus efficace d’utiliser les fonctions natives min() et max(). Si vous devez utiliser ces fonctions de façon répétée, il est préférable de transformer l’itérable en tas.

8.5.1. Exemples simples

Un tri par tas peut être implémenté en introduisant toutes les valeurs dans un tas puis en effectuant l’extraction des éléments un par un :

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Ceci est similaire à sorted(iterable) mais, contrairement à sorted(), cette implémentation n’est pas stable.

Les éléments d’un tas peuvent être des n-uplets. C’est pratique pour assigner des valeurs de comparaison (par exemple, des priorités de tâches) en plus de l’élément qui est suivi :

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

8.5.2. Notes d’implémentation de la file de priorité

Une file de priorité est une application courante des tas et présente plusieurs défis d’implémentation :

  • Stabilité du classement : comment s’assurer que deux tâches avec la même priorité sont renvoyées dans l’ordre de leur ajout ?

  • La comparaison des couples (priorité, tâche) échoue si les priorités sont identiques et que les tâches n’ont pas de relation d’ordre par défaut.

  • Si la priorité d’une tâche change, comment la déplacer à sa nouvelle position dans le tas ?

  • Si une tâche en attente doit être supprimée, comment la trouver et la supprimer de la file ?

Une solution aux deux premiers problèmes consiste à stocker les entrées sous forme de liste à 3 éléments incluant la priorité, le numéro d’ajout et la tâche. Le numéro d’ajout sert à briser les égalités de telle sorte que deux tâches avec la même priorité sont renvoyées dans l’ordre de leur insertion. Puisque deux tâches ne peuvent jamais avoir le même numéro d’ajout, la comparaison des triplets ne va jamais chercher à comparer des tâches entre elles.

Le problème restant consiste à trouver une tâche en attente et modifier sa priorité ou la supprimer. Trouver une tâche peut être réalisé à l’aide d’un dictionnaire pointant vers une entrée dans la file.

Supprimer une entrée ou changer sa priorité est plus difficile puisque cela romprait l’invariant de la structure de tas. Une solution possible est de marquer l’entrée comme supprimée et d’ajouter une nouvelle entrée avec sa priorité modifiée :

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

8.5.3. Théorie

Les tas sont des tableaux pour lesquels a[k] <= a[2*k+1] et a[k] <= a[2*k+2] pour tout k en comptant les éléments à partir de 0. Pour simplifier la comparaison, les éléments inexistants sont considérés comme étant infinis. L’intérêt des tas est que a[0] est toujours leur plus petit élément.

L’invariant étrange ci-dessus est une représentation efficace en mémoire d’un tournoi. Les nombres ci-dessous sont k et non a[k] :

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

Dans l’arbre ci-dessus, chaque nœud k a pour enfants 2*k+1 et 2*k+2. Dans les tournois binaires habituels dans les compétitions sportives, chaque nœud est le vainqueur des deux nœuds inférieurs et nous pouvons tracer le chemin du vainqueur le long de l’arbre afin de voir qui étaient ses adversaires. Cependant, dans de nombreuses applications informatiques de ces tournois, nous n’avons pas besoin de produire l’historique du vainqueur. Afin d’occuper moins de mémoire, on remplace le vainqueur lors de sa promotion par un autre élément à un plus bas niveau. La règle devient alors qu’un nœud et les deux nœuds qu’il chapeaute contiennent trois éléments différents, mais le nœud supérieur « gagne » contre les deux nœuds inférieurs.

Si cet invariant de tas est vérifié à tout instant, alors l’élément à l’indice 0 est le vainqueur global. L’algorithme le plus simple pour le retirer et trouver le vainqueur « suivant » consiste à déplacer un perdant (par exemple le nœud 30 dans le diagramme ci-dessus) à la position 0, puis à faire redescendre cette nouvelle racine dans l’arbre en échangeant sa valeur avec celle d’un de ses fils jusqu’à ce que l’invariant soit rétabli. Cette approche a un coût logarithmique par rapport au nombre total d’éléments dans l’arbre. En itérant sur tous les éléments, le classement s’effectue en O(n log n) opérations.

Une propriété agréable de cet algorithme est qu’il est possible d’insérer efficacement de nouveaux éléments en cours de classement, du moment que les éléments insérés ne sont pas « meilleurs » que le dernier élément qui a été extrait. Ceci s’avère très utile dans des simulations où l’arbre contient la liste des événements arrivants et que la condition de « victoire » est le plus petit temps d’exécution planifié. Lorsqu’un événement programme l’exécution d’autres événements, ceux-ci sont planifiés pour le futur et peuvent donc rejoindre le tas. Ainsi, le tas est une bonne structure pour implémenter un ordonnanceur (et c’est ce que j’ai utilisé pour mon séquenceur MIDI ☺).

Plusieurs structures ont été étudiées en détail pour implémenter des ordonnanceurs et les tas sont bien adaptés : ils sont raisonnablement rapides, leur vitesse est presque constante et le pire cas ne diffère pas trop du cas moyen. S’il existe des représentations qui sont plus efficaces en général, les pires cas peuvent être terriblement mauvais.

Les tas sont également très utiles pour ordonner les données sur de gros disques. Vous savez probablement qu’un gros tri implique la production de séquences pré-classées (dont la taille est généralement liée à la quantité de mémoire CPU disponible), suivie par une passe de fusion qui est généralement organisée de façon très intelligente 1. Il est très important que le classement initial produise des séquences les plus longues possibles. Les tournois sont une bonne façon d’arriver à ce résultat. Si, en utilisant toute la mémoire disponible pour stocker un tournoi, vous remplacez et faites percoler les éléments qui s’avèrent acceptables pour la séquence courante, vous produirez des séquences d’une taille égale au double de la mémoire pour une entrée aléatoire et bien mieux pour une entrée approximativement triée.

Qui plus est, si vous écrivez l’élément 0 sur le disque et que vous recevez en entrée un élément qui n’est pas adapté au tournoi actuel (parce que sa valeur « gagne » par rapport à la dernière valeur de sortie), alors il ne peut pas être stocké dans le tas donc la taille de ce dernier diminue. La mémoire libérée peut être réutilisée immédiatement pour progressivement construire un deuxième tas, qui croit à la même vitesse que le premier décroît. Lorsque le premier tas a complètement disparu, vous échangez les tas et démarrez une nouvelle séquence. Malin et plutôt efficace !

Pour résumer, les tas sont des structures de données qu’il est bon de connaître. Je les utilise dans quelques applications et je pense qu’il est bon de garder le module heap sous le coude. ☺

Notes

1

Les algorithmes de répartition de charge pour les disques, courants de nos jours, sont plus embêtants qu’utiles, en raison de la capacité des disques à réaliser des accès aléatoires. Sur les périphériques qui ne peuvent faire que de la lecture séquentielle, comme les gros lecteurs à bandes, le besoin était différent et il fallait être malin pour s’assurer (bien à l’avance) que chaque mouvement de bande serait le plus efficace possible (c’est-à-dire participerait au mieux à l”« avancée » de la fusion). Certaines cassettes pouvaient même lire à l’envers et cela était aussi utilisé pour éviter de remonter dans le temps. Croyez-moi, les bons tris sur bandes étaient spectaculaires à regarder ! Depuis la nuit des temps, trier a toujours été le Grand Art ! ☺