Doshi's blog

Thème:

Comment on mélange un tableau ?

, — ~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 1 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)2, 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 :

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 3 (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) 4 !

    [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à !

  1. Ou une liste si vous venez de Python, c’est pareil (mais j’avoue que liste pour un tableau à 1 dimension, c’est plus logique) 

  2. Il y a aussi entre autres numpy.random(liste), mais ça fait des trucs que je comprends pas forcément avec plein de fonctions de numpy, et le cas où l’argument passé est une simple liste Python est la même que celle de random.random(liste) 

  3. La docstring de randbelow nous dit : “Return a random int in the range [0,n). Raises ValueError if n==0.”. Soit en français “Retoune un entier aléatoire entre 0 et n (n exclus). Lève une ValueError (erreur de valeur) si n == 0” 

  4. Pour ceux pas familier avec la complexité, c’est le “temps” que prend un algorithme à se faire, avec une entrée de taille n. Du coup une complexité en O(n) ça veut dire que que l’algo prends un “temps” proportionnel à la taille de l’entrée. Ce qui est vachement bien. (et pour les malins qui auraient remarqué qu’on fait un truc proportionnel à n-1, en fait on regarde la limite en l’infini. Donc on garde que le terme de plus haut degré. Donc ici entre n de degré 1 et -1 de degré 0, bah on garde que n) 


Il n'y a pas de commentaires sur ce blog, cependant, n'hésitez pas à me faire des remarques sur cet article (ou autre, d'ailleurs). Que ce soit via Mastodon, Twitter, XMPP ou encore par mail, je serai ravi de voir que des gens me lisent pour de vrai