Doshi's blog

Comment on mélange un tableau ?

03/08/2018 — informatique, programmation, python — ~5mn de lecture

L’autre jour (hier à l’heure de la rédaction de cet article, en fait), je me suis posé une question : « On entend vachement parler des algos de tri, et c’est vrai qu’ils sont cools, mais comment on mélange un tableau ¹ en fait ? »

Bah ouais : je savais même pas comment on mélangeait un tableau, c’est con quand même !

Bon bah du coup comment on fait ? Et bah on va aller mater du code :D

Quel code on va mater, du coup ?

J’me suis dit que j’allais présenter la façon de faire de Python et de Ruby, mais :

1. En fait ils font pareil
2. Ruby, c’est la méthode Array.shuffle!, qui est écrite en C ; et Python c’est random.random(liste) ², qui est écrite en Python

Bon bah du coup on va juste regarder en Python, parce que c’est pareil et c’est plus facile à lire !

Talk is cheap. Show me the code.

Extrait de random.py sur Github :

    def shuffle(self, x, random=None):
        """Shuffle list x in place, and return None.
        Optional argument random is a 0-argument function returning a
        random float in [0.0, 1.0); if it is the default None, the
        standard random.random will be used.
        """

        if random is None:
            randbelow = self._randbelow
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = randbelow(i+1)
                x[i], x[j] = x[j], x[i]
        else:
            _int = int
            for i in reversed(range(1, len(x))):
                # pick an element in x[:i+1] with which to exchange x[i]
                j = _int(random() * (i+1))
                x[i], x[j] = x[j], x[i]

Le cas normal (random is None)

Bon dans un premier temps ce qui nous intéresse, c’est le cas normal où on lui file pas de fonction random custom :

    randbelow = self._randbelow
    for i in reversed(range(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = randbelow(i+1)
        x[i], x[j] = x[j], x[i]

Bon la 1ère ligne, j’ai 2 hypothèses :

• Soit c’est juste pour réduire la taille de la ligne 4 (ça m’étonnerait)
• Soit c’est une histoire d’optimisation, genre une variable dans la fonction (sur la pile du coup), c’est plus rapide à accéder qu’une méthode de self

Ensuite la ligne 2 nous informe qu’on va parcourir le tableau à l’envers.

Ligne 4, on va choisir un entier au hasard entre 0 et i ³ (tout le tableau avant i du coup, vu qu’on parcourt à l’envers)

Et PAF ligne 5, on échange

Et du coup on se retrouve avec un algorithme tout mignon tout gentil en complexité O(n) ⁴ !

    [1, 2, 3, 4]      On prend un élément au pif dans [1,2,3] et on l'échange avec 4
    ⌊_______⌋ ^

    [1, 4, 3, 2]     On "descend" d'un rang et on recommence
    ⌊____⌋ ^

    [1, 3, 4, 2]     Quand il reste qu'un seul élement souligné, on a fini !
    ⌊_⌋ ^

Et tadam ! On a un beau tableau bien mélangé : [1, 3, 4, 2]

Et pour ceux qui se demanderaient pourquoi quand il reste qu’un élément, on fait pas encore une étape : parce que ça voudrait dire échanger tout le temps l’element 0 et l’élément 1. Et du coup y’a pas de hasard, qu’on les échange ou qu’on les échange pas, si on est sur à 100% de faire l’un des deux, ça change pas le “degré de mélange”. Du coup ça sert à rien de faire une opération inutile.

Le cas où random est fourni en argument

    _int = int
    for i in reversed(range(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = _int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

C’est exactement le même principe, sauf qu’au lieu d’avoir une distribution uniforme pour choisir notre élément (c’est à dire que chaque élément a la même chance d’être choisi), on fournit nous même une distribution à utiliser. Par exemple, on pourrait utiliser une distribution qui favoriserait les élément vers le début du tableau, ou l’inverse.

Et quant-à la 1ère ligne, j’imagine qu’elle est là pour la même raison que randbelow = self._randbelow, pour aller plus vite

Voilà voilà !