Qu’est-ce que cela signifie-t-il donc, alors, hein ?

C’est une manière de décrire l’ordre de grandeur de temps que va prendre un algo pour s’exécuter pour un nombre “n” d’éléments.

Par exemple, si je fais ceci en Python :

elements = [1, 2, 3]
for x in elements:
    print(x)
## 1
## 2
## 3

Ici, j’ai 3 éléments, donc n = 3. Mon algorithme va tous les utiliser une fois, mais pas plus d’une. Il va donc faire un nombre d’opérations proportionnel au nombres d’éléments. On note ce type de comportement O(n). Cela signifie que le temps de traitement de mon code suit à peu près “n”.

Je dis à peu près car le nombre d’éléments n’est pas uniquement ce qui va rentrer en compte. La taille des éléments, l’état de la machine au moment de l’exécution et tout un tas d’autres paramètres vont être des facteurs. Mais, globalement, je peux donner une évaluation convenable du temps que le code va prendre en notant le temps de traitement d’un seul élément, et en le multipliant par le nombre total d’éléments.

La notation O(truc), que l’on prononce “Oh de truc”, sert juste à indiquer quel type de comportement un algo a : est-ce qu’il prend du temps par rapport au nombre d’éléments ? Si oui à quel point ?

“A quel point” est une question importante, car si mon algo est celui ci:

elements = [1, 2, 3]
for x in elements:
    print()
    for i in elements:
        print(i, end="")
## 123
## 123
## 123

Alors, si n est grand, non seulement ma première boucle s’allonge, mais ma seconde boucle s’allonge aussi car j’affiche TOUS les éléments pour CHAQUE élément. Mon temps d’exécution dépend alors de “n” multiplié par lui-même : n X n. En effet, si j’ai 2 éléments, je vais faire 2 x 2 = 4 print(), si j’en ai 3, je vais faire 3 x 3 print(), etc.

Bien sûr, je pourrais faire des choses beaucoup plus compliquées qu’un print(), mais ça n’a pas d’importance. On en mesure pas le temps de tout le programme, seulement l’efficacité d’un algorithme. Ici, cela dépend du nombre d’éléments fois lui-même, soit au carré. On le note O(n²).

Il existe tout un tas de ces notations. Par exemple, 0(1) signifie un temps “constant”, c’est un abus de langage pour dire que le temps que met l’ago à s’effectuer ne dépend pas du nombre d’éléments.

Par exemple :

elements = [1, 2, 3]
print(elements[0])
## 1

Afficher le premier élément prend un temps du même ordre de grandeur – car c’est ça l’important, l’ordre de grandeur – si il y a 1 ou 10000 éléments. On note donc cet algo O(1).

Il y a des cas plus complexes. Imaginez celui-ci :

import random
 
number = random.randint(0, 100)
print("Choosing: %s" % number)
smallest = 0
biggest = 100
guess = 50
while guess != number:
    if number >= guess:
        smallest = guess
    else:
        biggest = guess
 
    guess = (biggest - smallest)//2 + smallest
    print("New guess: %s" % guess)
 
print("Last guess: %s" % guess)
## Choosing: 69
## New guess: 75
## New guess: 62
## New guess: 68
## New guess: 71
## New guess: 69
## Last guess: 69

Dans cet exemple, le nombre d’opérations dépend du nombre d’éléments “n” (ici 100) mais on divise l’interval de recherche par deux à chaque tour de boucle. On note cette complexité O(log n), puisque la fonction log illustre bien le concept d’avoir une mi-molle sur la fin de son algo :)

Il y a aussi l’inverse :

elements = [1, 2, 3, 4, 5]
copies = []
for x in elements:
    print()
    for i in copies:
        print(i, end="")
    copies.extend(elements)
## 12345
## 1234512345
## 123451234512345
## 12345123451234512345

Ici on augment la charge à traiter à chaque tour de boucle, et cette augmentation dépend du nombre d’éléments “n”. On parle d’une augmentation exponentielle de la charge de travail et on le note O(eⁿ).

A quoi ça sert ?

Essentiellement à avoir une idée d’où on met les pieds. Si vous lisez une doc, et qu’on vous dis “cet algo met un temps O(log(n))”, vous savez que même sur un grand ensemble de données, le traitement ne sera pas trop agressif. Si plus tard vous rencontrez des problèmes de perf, ce ne sera pas le premier endroit à regarder.

Par contre si vous lisez qu’un algo est O(n!) – là on tape dans les factoriels, c’est énorme – alors au premier ralentissement il faut jeter un coup d’œil sur ce bout de code.

C’est aussi utile pour comparer l’efficacité de deux implémentations.

Imaginez la structure suivante :

class Examen:
    """C'est un exemple pédagogique, ne faites pas ça chez vous les enfants"""
    def __init__(self):
        self.notes = []
 
    def ajouterNote(self, note):
        self.notes.append(note)
 
    def moyenne(self):
        total = 0
        for note in self.notes:
            total += note
        return total / len(self.notes)

Récupérer la moyenne est une opération O(n). En revanche, si on a :

class Examen:
    def __init__(self):
        self.notes = []
        self.moyenne = None
 
    def ajouterNote(self, note):
 
        if self.moyenne is None:
            self.moyenne = note
        else:
            self.moyenne = (len(self.notes)*self.moyenne + note) / (len(self.notes)+1)
        self.notes.append(note)

Là, récupérer la moyenne devient une opération O(1), on a déchargé et réparti le calcul sur l’ajout des notes. Selon que l’application va lire souvent la moyenne ou non, l’un ou l’autre algo est préférable, et la notation Big O va donner une idée duquel utiliser si on est face à la doc et pas au code, qui est généralement vachement plus compliqué que ça.

Bon, ok, dans la VVV, aucune de ces deux solutions n’est un problème, on s’en branle. Mais sur des algos plus riches, sur du matos plus limité, ou un jeu de données plus grand, c’est important. Ainsi, la doc de redis donne la notation Big O de toutes les commandes.

En Python, qui est quoi ?

Parcourir un itérable, c’est généralement du O(n), en tout cas pour les listes, les tuples, les dicos, les strings et les sets. Ajouter un élément ou en retirer un, c’est du O(1). Récupérer leurs tailles, c’est du O(1) aussi (elle est mise en cache), donc vous pouvez y aller avec len().

En revanche, l’opérateur in a un temps moyen de O(n) pour les strings, les tuples et les listes (il doit parcourir l’itérable jusqu’à trouver l’élément), et un temps de O(1) pour les sets et les dicos. Ces derniers utilisent des hash, rendant la recherche très très rapide. C’est pour cela qu’on vous dit d’utiliser la bonne structure de données pour le bon usage.

Attention cependant, c’est de l’optimisation de poil de cul, mais c’est pour la culture, O(1) ne veut pas dire “plus rapide que O(n)”. O(1) veut juste dire que le temps est indépendant du nombre d’éléments. Ainsi :

1 in [1, 2, 3] sera beaucoup plus rapide que 1 in [1, 2, 3..., 1000].

Et :

1 in {1, 2, 3} prendra un temps similaire à 1 in {1, 2, 3..., 1000}

Mais :

1 in {1, 2, 3} peut tout à faire être plus lent que 1 in [1, 2, 3]

Par contre, il est presque certain que :

1 in {1, 2, 3..., 1000} est BEAUCOUP plus rapide que 1 in [1, 2, 3..., 1000]

De plus, il y énormément de structures de données dans la stdlib Python, toutes avec des capacités différentes. Heapq assure que votre structure de données est toujours ordonnées pour un coût de O(log n) à l’insertion. Les deques sont très rapides comme FIFO/LIFO (O(1)), mais récupérer une donnée au milieu est une opération O(n). Certaines opérations, comme retirer un élément d’un type list sont étonnamment coûteuses ((O(n) dans le cas du del).

Voici quelques notations de la doc de Python.

La théorie, la pratique, et la mauvaise foi

La notation O est une bonne indication pour faire un choix d’algo ou pour commencer ses recherches de goulot d’étranglement dans un code.

Néanmoins, c’est la performance sur la papier. En pratique, on peut obtenir des résultats un peu différents, voir carrément surprenant. Il peut y avoir de multiples causes :

• L’implémentation ne se comporte pas comme prévu. CPython et Jython n’ont pas les mêmes perfs pour les mêmes choses. Jython n’a pas de GIL.
• Vous avez oublié un paramètre. Un accès disque ou un accès réseau au mauvais endroit, et bam, votre évaluation est à revoir.
• Les données de la vie réelle ont généralement des tendances. Par exemple elles sont souvent un peu triées plutôt que complètement en bordel. C’est pour cette raison que Python utilise Timsort.
• Le matos ne fait pas ce que vous croyez. Les processeurs / cartes graphiques actuels sont devenus incroyablement efficaces à certaines opérations réputées lentes
• Votre machine ne fait pas que faire tourner votre algo. Il y a d’autres processus, avec des conséquences.

Donc si les perfs sont importantes, comme toujours en informatique, on a le dernier mot en mesurant soi-même.

Qui n’a jamais rêvé de cloner des moutons clara morgane et de s’adonner à des expérimentations scientifiques de haut niveau ?

Bon ici, nous n’avons pas de clara morgane sous la main pour notre expérience mais, avec le python et les théories scientifiques de Darwin, on peut faire quelques trucs sympas : On va essayer de déterminer le plus court chemin à prendre pour relier plusieurs points entre eux, le truc cool c’est que pour solutionner le problème on va utiliser un algorithme génétique.

De la génétique dans du python ?!

En fait c’est assez simple (encore des termes barbares pour épater les copains..), écoutez bien, je vous explique le concept : on va faire des individus, chaque individu va faire un parcours en fonction des points du tracé en paramètre. A la fin, on note chaque individu avec un score, le score étant la longueur du parcours de l’individu. Vous suivez toujours ? Bien. On prend les meilleurs (Normal) et on les accouple avec des moins bons (faut les pousser un peu, au début ils sont timides mais, après ça va tout seul, c’est même l’orgie parfois…) ce qui donne une nouvelle population, normalement un poil meilleure que l’ancienne qu’on va vite mettre à la poubelle. On recommence le processus n fois et à la fin, on devrait arriver à des super individus, genre blonds aux yeux bleus qui parlent 14 langues : ça c’est notre solution.

Passons aux travaux pratiques !

Je commence par déclarer deux variables globales, la population et la liste de points.

population = []
a_map = []

Ensuite on créer une classe Point standard :

class Point(object):
 
    COUNT = 0
 
    def __init__(self, x, y):
        self.X = x
        self.Y = y
 
    def __str__(self):
        return "Point(%s,%s)"%(self.X, self.Y) 
 
    def distance(self, other):
        dx = self.X - other.X
        dy = self.Y - other.Y
        return sqrt(dx**2 + dy**2)

Rien de particulier ici, l’objet nous sera utile plus tard.

class Individu(object):
 
    # le constructeur de l'objet.
    # on met le score à zéro.
    # on peut aussi lui passer la liste de points
    # pour qu'il initialise une route au hasard.
    def __init__(self, init = False, map_point = []):
        self.score = 0
        self.route = []
        if init :
            self.set_route(map_point)
 
    # ici on créé une route avec un mélange des points
    # on utilise shuffle pour mélanger les points.
    # ensuite on calcul le score, c'est à dire la longueur du trajet.
    def set_route(self, map_point) :
        shuffle(map_point)
        self.route = map_point
        for p in range(len(map_point) - 1) :
            self.score += map_point[p].distance(map_point[p+1])
 
    # ici on donne à l'objet la capacité de faire un enfant
    # ça prend comme paramètre l'objet (lui même), et un autre individu.
    # on prend la moitié du trajet de l'objet et on complète avec
    # les points de l'autre individu.
    # on retourne un enfant, qui est un individu.
    def croisement(self, other):
        child = Individu()
        # je prends la moitier de moi-même.
        wdth = len(self.route)/2
        first_segment = self.route[:wdth/2]
        last_segment  = []
        # je complète avec l'autre
        for i in range(len(self.route)) :
            if other.route[i] not in first_segment :
                last_segment.append(other.route[i])
        child.set_route(first_segment + last_segment)
        return child
 
    # ici on défini une fonction pour que l'objet puisse se dessiner.
    # pour cela on utilisera Turtle de python.
    def show_me(self):
        turtle.clearscreen()
        pen = turtle.Turtle()
        pen.speed(0)
        pen.up()
        pen.setpos(self.route[0].X, self.route[0].Y)
        for point in self.route :
            pen.goto(point.X, point.Y)
            pen.down()
            pen.dot()
 
        pen.goto(self.route[0].X, self.route[0].Y)

Voilà pour l’objet individu (pas très inspiré sur le nom j’avoue..) qui est donc capable maintenant de faire pas mal de choses qui sera utile: se montrer, faire un petit (capacité que beaucoup d’objet lui envie déjà) et choisir une route parmi une liste de points.

La suite, j’ai écris ça dans des fonctions, il y a surement plus propre mais bon, le but est de vous montrer comment fonctionne un algo génétique, je laisserai le soin aux pro du python d’améliorer le code en lui-même (je ne vais pas faire tout le boulot non plus !)

# initialisation des points de la carte.
# prend en paramètre un nombre de points.
def init_map(nb):
    global a_map
    del a_map[:]
    for i in range(nb):
        p = Point(randint(1, 300), randint(1, 300))
        a_map.append(p)

# initialisation de la population.
# prend en paramètre le nombre d'individus à créer.
def init_pop(nb, map_point):
    global population
    del population[:]
    for i in range(nb):
        i = Individu(True, map_point)
        population.append(i)

# fonction qui sert à trier les individus suivant leur score.
# utile pour trouver les meilleurs.
def selection(pop):
    pop.sort(key=lambda x: x.score, reverse=True)

# dans cette fonction, on sélectionne les 15 meilleurs individus de la population
# que l'on croise avec les autres individus.
# la nouvelle population est constituée des 15 meilleurs plus les enfants.
def croisement(pop):
    new_pop = []
    best_pop = population[85:]
    for i in range(len(pop)-15) :
        new_pop.append(choice(best_pop).croisement(choice(population[20:85])))
    return new_pop + best_pop

# la fonction principal.
# on passe en paramètre le nombre de générations que l'on souhaite faire
# et le nombre de points. 
# Ensuite, on itère selon un algorithme précis :
# Création d'une population initiale.
# Sélection puis croisement de la population
# à chaque génération on regarde si on a un meilleur score
# si oui, on l'affiche.
def play(nb_gene, nb_point) :
    init_map(nb_point)
    init_pop(100, a_map)
    best_score = 1000000
    for i in range(nb_gene) :
        global population
        population = croisement(population)
        selection(population)
        if best_score > population[99].score :
            best_score = population[99].score
            print 'meilleur score : ' + str(population[99].score)
            population[99].show_me()

Voilà le morceau, je pense que j’ai laissé assez de commentaires dans le code pour bien comprendre comment ça fonctionne et au niveau du python en lui-même il n’y a vraiment rien de spécial, ici ce qui compte c’est que vous voyez rapidement comment fonctionne l’algorithme.

Alors, maintenant : Pourquoi s’emmerder à accoupler des objets à 2,78 Ghz ?

Le problème ci-dessus, un problème dit np-complet, c’est-à-dire que c’est la merde pour trouver une solution dans un temps raisonnable si on l’a fait de façon traditionnelle : pour trouver le meilleur trajet sur 10 points, on sera obligé dans un premier temps de trouver tous les trajets possibles, avec N villes on a (N-1)!/2 trajet possible, le nombre de trajets explose littéralement si N augmente. Avec 100 points il est déjà pratiquement impossible de calculer tous les trajets possibles en un temps raisonnable.

C’est là que l’algorithme génétique est très fort, on arrive très vite à une solution approchée, il est tout de même à noter que le résultat obtenu par l’algorithme génétique n’est pas LA solution exact au problème, il donne une solution approchée.

Dernier point sur le code ci-dessus, ce n’est que les bases de l’algorithme génétique, avec ce code vous ne pourrez pas venir à bout d’un parcours de plus de 20 ou 30 villes, pour cela il faut améliorer l’algorithme, par exemple le croisement entre deux individus peut être fait de plusieurs façons différentes, dans mon exemple je prends la moitié du “code génétique” d’un individu que je colle à une autre moitié, on peut aussi faire du crossover : c’est-à-dire qu’on prend des bouts du code génétique des deux individus alternativement. Ensuite, il y a aussi des mutations génétiques à introduire dans le croisement, à un certain taux, par exemple 1% des croisements entre individus produira une mutation génétique, concrètement : on fait le croisement puis on change aléatoirement des données du code génétique, dans notre exemple on échangera deux points sur le parcours. Cela a pour effet de produire des individus potentiellement meilleurs que les autres, en terme mathématique ça permet aussi de ne pas s’enfermer dans une solution locale, ce qui est souvent le cas.

J’espère ne pas vous avoir complètement perdu avec mes explications et vous avoir donné envie de regarder de plus près cet algorithme que je trouve très élégant.

Ceci est un post invité de Réchèr posté sous licence creative common 3.0 unported.

Kikoo amis matheux ou pas. Aujourd’hui, on va se faire un petit algo de derrière les fagots. Vous n’en aurez peut-être jamais besoin dans le monde réel, mais, qui a dit qu’on allait se contenter uniquement de ce dont on a besoin ? De plus, je présenterais, à la fin, une astuce générique d’algorithmiciens.

Pré-requis

• Connaître très vaguement la notion des O(n²), O(truc), … qui définissent le temps d’exécution d’un algorithme en fonction de la quantité de données à traiter. (Si ça vous parle pas c’est pas grave).
• Savoir que le pluriel d’intervalle n’est pas “intervaux”.

Petite précision : pour définir des intervalles d’entiers, j’emploierais la convention pythonienne : le dernier élément n’est pas inclus. C’est à dire que [2, 7] correspond à 5 éléments : 2, 3, 4, 5, 6.

Énoncé

Soit une liste de couple de nombres, représentant des intervalles. Ils sont tout en vrac, y’en a qui se chevauchent, d’autres qui s’inclusent, etc. Bref, l’ensemble fait penser à une partouse animale multi-espèces.

exemple : [ [2, 7], [3, 7], [1, 5], [9, 10], [8, 9] ]

Vous voulez une méthode pour rassembler tout ça, et obtenir une liste d’intervalles, triée, sans chevauchement, correspondant à la fusion de tous les intervalles de départ. En maths, on appelle cette opération une union. En partouse animale multi-espèces, on appelle aussi ça une union, mais ce n’est pas le sujet.

résultat souhaité : [ [1, 7], [8, 10] ]

Solutions auxquelles on pense en premier

Le bourrin pas-à-pas

On récupère le début d’intervalle le plus à gauche, et la fin la plus à droite. On boucle entre ces deux valeurs. À chaque itération, on effectue le traitement suivant :

• Vérifier si la valeur courante est dans au moins un intervalle.
• Si oui, et que juste avant on était dans aucun intervalle, alors on marque cette valeur comme un début d’intervalle.
• Si non, et que juste avant on était dans au moins un intervalle, alors on marque cette valeur comme une fin d’intervalle.

Désavantages

Si, au départ, on a deux intervalles très éloignés, par exemple [0, 2] et [1000000, 1000002] on va faire une boucle de 1000002 itérations. Pour traiter 2 intervalles, c’est un peu lourd.

Ça ne marche qu’avec des entiers. Si on a des intervalles de réels, on itère comment ? En avançant de 0.0000000001 en 0.0000000001 ? Même problème avec des intervalles de date-heure.

Le bourrin cumulatif

On crée une liste géante de booléens, tous à False, qui s’étend du premier début d’intervalle à la fin du dernier. Chaque booléen indiquera si le nombre correspondant se trouve dans au moins un intervalle. On met les bons booléens à True en parcourant les intervalles de la liste initiale. Puis, on construit la liste finale d’intervalles, en se basant sur les booléens.

Désavantages

Si on a en entrée un million de fois l’intervalle [10, 210], on va mettre un million de fois à True la même suite de 200 booléens. 200 millions d’opérations pour ressortir un unique intervalle [10, 210].

Même problème que précédemment. Ça ne marche qu’avec des nombres entiers.

L’enfileur de perles

On a d’un côté la liste finale des intervalles (initialisée à vide), et de l’autre, la liste initiale, en bordel. On passe les intervalles d’une liste à l’autre, un par un, en testant les cas suivants :

• Le début et la fin de l’intervalle en cours n’est dans aucun intervalle final -> ça fait un nouvel intervalle final.
• Le début est dans un intervalle final, mais pas la fin -> ça rallonge l’interval final existant.
• La fin est dans un intervalle final, mais pas le début -> ça rallonge l’intervalle final existant, mais par l’autre côté.
• La fin et le début sont dans le même intervalle final -> l’intervalle en cours ne sert à rien.
• La fin et le début sont dans deux intervalles finaux différents. -> il faut fusionner les deux intervalles finaux.

Et en plus de tout ça, il faut également tester s’il n’y a pas des intervalles finaux entièrement inclus dans l’intervalle en cours. Auquel cas, ils ne servent plus à rien, et doivent être enlevé de la liste.

Désavantages

Une bonne grosse prise de tête à coder tous les cas possibles, sans rien oublier, sans bug.

Le fait de chercher si un nombre se trouve dans une liste d’intervalles, fut-elle triée, est une opération qui prend un certain temps. Ça peut s’optimiser avec de la dichotomie ou des trucs du genre, mais quand même.

Par contre, cette algo marche avec des nombres réels et des date-heure. Youpi.

Et si on arrêtait les conneries ?

Dans ces premières solutions, on considère les intervalles comme des objets immuables. Il faut en traiter un entièrement avant de passer au suivant. Mais on peut aussi les voir comme deux événements distincts (un début et une fin), que l’on peut dissocier totalement, et traiter dans leur ordre d’arrivée. On ne sera plus capable de retrouver quel début correspond à quelle fin, mais ça on s’en fout, y’a rien qui ressemble plus à un intervalle qu’un autre intervalle.

Imaginez un petit bonhomme (ou une petite bonne femme, respectons la parité). Au départ, il est au niveau du sol. Il avance vers la droite. Quand il rencontre un début d’intervalle, il monte sur un mur d’un étage. Quand il rencontre une fin, il descend d’un étage. Il peut être sur plusieurs étages superposés. Au fur et à mesure qu’il se déplace, on note les endroits où il se retrouve sur le sol. Ces endroits correspondent à des zones sans aucun intervalle.

Le code

def tri_bonhomme_sur_un_mur(list_intervalle_en_bordel):
    """ Effectue une union de tous les intervalles indiqués en paramètre.
 
    Données d'entrée : une liste de liste de deux éléments, représentant
    des intervalles.
     - Le type des éléments n'est pas imposé. Il faut juste qu'on puisse 
       les ordonner et les trier. 
     - Dans chaque liste de deux éléments, le premier doit être plus 
       petit que le second. 
    La fonction ne vérifie pas ces contraintes. Si elles ne sont pas 
    respectées, le comportement est indéterminé. Ça peut planter, 
    ça peut renvoyer un résultat faux sans avertissement, etc.
 
    Sortie : une liste de liste de deux éléments, unionnisée et triée
    comme il faut.
    """
    # On extrait tous les débuts d'intervalles, et toutes les fins.
    list_debut = [ interv[0] for interv in list_intervalle_en_bordel ]
    list_fin = [ interv[1] for interv in list_intervalle_en_bordel ]
    # On les trie, pour pouvoir les traiter de gauche à droite.
    list_debut.sort()
    list_fin.sort()
    # Cette liste contiendra les intervalles unionnisés et triés.
    list_intervalle_final = []
    # indique le nombre d'invervalle superposés dans lesquels on se trouve
    # actuellement. (C'est à dire : le nombre d'étages sur lequel
    # marche le bonhomme).
    nb_superposition = 0
    # Lorsqu'on est dans un ou plusieurs intervalles superposés, on doit
    # se souvenir à quelle position on est entré dans le premier.
    # Cela permettra de créer l'intervalle final, lorsqu'on sera 
    # complètement sorti de la superposition en cours.
    debut_intervalle_courant = 0
 
    # C'est parti ! Le petit bonhomme avance. On lui fait traiter les
    # événements d'entrée et de sortie d'intervalle au fur et à mesure 
    # qu'ils arrivent.
    while list_debut:
        # Le premier élément de list_debut, c'est le premier début 
        # d'intervalle qu'on rencontrera. Le premier élément de list_fin,
        # c'est la première fin d'intervalle qu'on rencontrera. On 
        # détermine, parmi ces deux événements, lequel on rencontrera en 
        # tout premier.
        #
        # La fonction cmp renvoie -1, 0, ou 1, selon la comparaison 
        # effectuée entre les deux valeurs passées en paramètre.
        # Faire un petit help(cmp) pour connaître les détails.
        ordre_debut_fin = cmp(list_debut[0], list_fin[0])
        if ordre_debut_fin == -1:
            # L'événement rencontré est un début d'intervalle.
            # On enlève l'événement de la liste, puisqu'on va le traiter,
            # là, tout de suite.
            pos_debut = list_debut.pop(0)
            if nb_superposition == 0:
                # On était dans aucun intervalle, et on vient d'en 
                # rencontrer un. Dans la liste finale d'intervalles, 
                # ça va donc compter comme un début. On retient 
                # cette info.
                debut_intervalle_courant = pos_debut
            # Dans tous les cas, on ajoute une superposition d'intervalle
            # (le bonhomme monte d'un étage).
            nb_superposition += 1
        elif ordre_debut_fin == +1:
            # L'événement rencontré est une fin d'intervalle.
            # On l'enlève de la liste.
            pos_fin = list_fin.pop(0)
            # On enlève une superposition d'intervalle.
            nb_superposition -= 1
            if nb_superposition == 0:
                # Après avoir enlevé la superposition, on se retrouve
                # avec 0 intervalle superposé. 
                # (Le bonhomme est redescendu jusqu'au niveau du sol).
                # Il faut donc enregistrer ça comme une fin d'intervalle 
                # final. Tant qu'on y est, on crée tout de suite ce nouvel
                # intervalle final et on le met dans la liste.
                nouvel_intervalle = (debut_intervalle_courant, pos_fin)
                list_intervalle_final.append(nouvel_intervalle)
        else:
            # On rencontre à la fois un début et une fin d'intervalle.
            # Rien de spécial à faire. Faut juste virer les 2 événements 
            # traités de leur liste respectives.
            list_debut.pop(0)
            list_fin.pop(0)
 
        # Durant toute cette boucle, la variable nb_superposition augmente
        # et diminue. Mais elle n'est jamais censée devenir négative.
        # Si ça arrive, c'est que les données d'entrées sont mal foutues.
        # On entre dans un cas d'indétermination. 
 
    # Arrivé à la fin de la boucle, il peut rester, ou pas des éléments
    # dans list_fin. Ce qui est sûr, c'est que list_debut se vide
    # avant list_fin. Si ce n'est pas le cas, c'est encore un cas
    # d'indétermination.
 
    if list_fin:
        # On a passé tous les débuts d'intervalle, mais il reste des
        # fins. Ça veut dire qu'on est encore dans un ou plusieurs
        # intervalles. On devrait normalement avoir :
        # len(list_fin) == nb_superposition. Si c'est pas le cas, c'est
        # un cas d'indétermination.
        #
        # On pourrait traiter les événements de fin d'intervalle un par un,
        # et diminuer progressivement nb_superposition. Mais on s'en fout,
        # c'est pas nécessaire. On prend juste la fin d'intervalle qui 
        # supprimera la dernière superposition (c'est à dire la dernière
        # fin d'intervalle), et on construit un dernier intervalle final
        # avec ça.
        pos_fin = list_fin[-1]
        nouvel_intervalle = (debut_intervalle_courant, pos_fin)
        list_intervalle_final.append(nouvel_intervalle)
 
    return list_intervalle_final

Les avantages (parce que y’a aucun désavantages)

Ça marche avec des réels, des dates, et de manière générale, tout ce qu’on peut trier.

>>>tri_bonhomme_sur_un_mur([ [2, 7], [3, 7], [1, 5], [9, 10], [8, 9] ])
[(1, 7), (8, 10)]
 
# Testez pas ça chez vous ! Ça prend trois plombes ! Mettez juste 1000.
>>>tri_bonhomme_sur_un_mur( [ [10, 210], ] * 1000000 )
[(10, 210)]
 
# Voyons voir ce que ça donne avec des réels 
# (dont certains sont négatifs, tant qu'à faire).
>>>tri_bonhomme_sur_un_mur([ 
    [-7.2, -6.9], [-8.4, -5.3], [-10.5, -5.25], 
    [-1.7, 0.01], [0.0, 4.0], 
    [12.125, 13.9, ], [13.9, 15.0]])
[(-10.5, -5.25), (-1.7, 4.0), (12.125, 15.0)]    
 
# et avec des dates
>>>from datetime import datetime
>>>tri_bonhomme_sur_un_mur([
    [datetime(2012, 12, 21, 16, 54), 
     datetime(2013, 02, 16, 12, 59)], 
    [datetime(2013, 02, 14, 2, 0), 
     datetime(2069, 01, 01, 13, 37), ] ] )
[(datetime.datetime(2012, 12, 21, 16, 54),
  datetime.datetime(2069, 1, 1, 13, 37))]

En ajoutant à peine 2-3 lignes de code à la fonction, on peut récupérer le nombre maximal d’intervalles superposés.

En re-ajoutant quelques autres lignes, on peut récupérer les zones dans lesquelles ce maximum est atteint. Ce qui pourrait servir pour effectuer l’opération mathématique d’intersection. (Je vous laisse chercher ça par vous mêmes).

L’algorithme est principalement constitué d’une bi-boucle, c’est à dire une boucle unique, qui avance dans deux listes différentes (je viens d’inventer ce terme, ne m’embêtez pas). C’est encore plus simple que deux boucles imbriquées. Le nombre d’itérations à effectuer est égal au nombre d’intervalle multiplié par deux, c’est tout. Dans tous les cas limites présentés ci-dessus, ça fait une solution acceptable, demandant un temps d’exécution peu pharaonique.

Mais ou est passé la complexité ?

Les premières solutions avaient l’air de demander énormément de temps d’exécution, surtout avec beaucoup d’intervalles en entrée. Ça ne semble pas être le cas pour la solution du “bonhomme sur un mur”. Pourtant, la complexité d’une tâche, ça ne disparaît pas comme par magie. Y’aurait-il une entourloupe quelque part ?

Il y en a une. Ce sont les deux opérations de tri effectuées au début de la fonction. Un tri, ce n’est pas anodin, et son temps d’exécution peut augmenter très beaucoup et très vite. La complexité n’a pas disparue, on n’a fait que la déplacer vers des tris. Alors finalement, ma solution n’est pas si bien que ça ?

Eh bien si. Parce que le tri, même s’il reste coûteux en temps et en ressource, est un problème archi-connu, archi-réglé, et archi-optimisé. Le python, comme beaucoup d’autres langages, profite pleinement du travail réalisé par des centaines de matheux algorithmologues, qui se sont masturbés l’esprit sur des centaines de méthodes de tri différentes.

Photo prise dans le bureau d'un chercheur en algorithmologie.

C’est ça l’astuce générique dont je vous parlais au début. Face à un nouveau problème, le matheux sort son zguègue tente de trouver des équivalents à un ou plusieurs problèmes connus, que lui et ses amis matheux ont déjà réglés. C’est souvent bien plus simple que de tenter de régler le problème directement, en partant de rien.

“Un nain éjacule bien plus loin lorsqu’il est perché sur les épaules d’un géant.” Et pour respecter la parité, j’ajouterais qu’une naine femme-fontainise bien plus loin lorqu’elle est perchée sur les épaules d’une géante.