Comment implémenter un shuffle pondéré

J'ai récemment écrit du code que je pensais très inefficace, mais comme il ne comprenait que quelques valeurs, je l'ai accepté. Cependant, je suis toujours intéressé par un meilleur algorithme pour les éléments suivants:

1. Une liste d'objets X, chacun d'eux se voit attribuer un "poids"
2. Résumez les poids
3. Générer un nombre aléatoire de 0 à la somme
4. Itérer à travers les objets, en soustrayant leur poids de la somme jusqu'à ce que la somme soit non positive
5. Supprimez l'objet de la liste, puis ajoutez-le à la fin de la nouvelle liste

Les éléments 2, 4 et 5 prennent tous du ntemps, et c'est donc un O(n^2)algorithme.

Cela peut-il être amélioré?

À titre d'exemple d'un shuffle pondéré, un élément a plus de chances d'être à l'avant avec un poids plus élevé.

Exemple (je vais générer des nombres aléatoires pour le rendre réel):

6 objets de poids 6,5,4,3,2,1; La somme est 21

J'en ai choisi 19: 19-6-5-4-3-2 = -1donc 2 va en première position, les poids sont maintenant de 6,5,4,3,1; La somme est de 19

J'en ai choisi 16 16-6-5-4-3 = -2:, donc 3 passe en deuxième position, les poids sont maintenant de 6,5,4,1; La somme est 16

J'en ai choisi 3: 3-6 = -3donc 6 passe en troisième position, les poids sont maintenant 5,4,1; La somme est 10

J'ai choisi 8:, 8-5-4 = -1donc 4 va en quatrième position, les poids sont maintenant de 5,1; La somme est 6

J'ai choisi 5:, 5-5=0donc 5 va en cinquième position, les poids sont maintenant à 1; La somme est 1

J'ai choisi 1:, 1-1=0donc 1 va dans la dernière position, je n'ai plus de poids, je termine

Cela peut être implémenté en O(n log(n))utilisant un arbre.

Créez d'abord l'arborescence en conservant dans chaque nœud la somme cumulée de tous les nœuds descendants à droite et à gauche de chaque nœud.

Pour échantillonner un élément, échantillonnez récursivement à partir du nœud racine, en utilisant les sommes cumulées pour décider si vous renvoyez le nœud actuel, un nœud de gauche ou un nœud de droite. Chaque fois que vous échantillonnez un nœud, définissez son poids sur zéro et mettez également à jour les nœuds parents.

Voici mon implémentation en Python:

import random

def weigthed_shuffle(items, weights):
    if len(items) != len(weights):
        raise ValueError("Unequal lengths")

    n = len(items)
    nodes = [None for _ in range(n)]

    def left_index(i):
        return 2 * i + 1

    def right_index(i):
        return 2 * i + 2

    def total_weight(i=0):
        if i >= n:
            return 0
        this_weigth = weights[i]
        if this_weigth <= 0:
            raise ValueError("Weigth can't be zero or negative")
        left_weigth = total_weight(left_index(i))
        right_weigth = total_weight(right_index(i))
        nodes[i] = [this_weigth, left_weigth, right_weigth]
        return this_weigth + left_weigth + right_weigth

    def sample(i=0):
        this_w, left_w, right_w = nodes[i]
        total = this_w + left_w + right_w
        r = total * random.random()
        if r < this_w:
            nodes[i][0] = 0
            return i
        elif r < this_w + left_w:
            chosen = sample(left_index(i))
            nodes[i][1] -= weights[chosen]
            return chosen
        else:
            chosen = sample(right_index(i))
            nodes[i][2] -= weights[chosen]
            return chosen

    total_weight() # build nodes tree

    return (items[sample()] for _ in range(n - 1))

Usage:

In [2]: items = list(range(10))
   ...: weights = list(range(10, 0, -1))
   ...:

In [3]: for _ in range(10):
   ...:     print(list(weigthed_shuffle(items, weights)))
   ...:
[5, 0, 8, 6, 7, 2, 3, 1, 4]
[1, 2, 5, 7, 3, 6, 9, 0, 4]
[1, 0, 2, 6, 8, 3, 7, 5, 4]
[4, 6, 8, 1, 2, 0, 3, 9, 7]
[3, 5, 1, 0, 4, 7, 2, 6, 8]
[3, 7, 1, 2, 0, 5, 6, 4, 8]
[1, 4, 8, 2, 6, 3, 0, 9, 5]
[3, 5, 0, 4, 2, 6, 1, 8, 9]
[6, 3, 5, 0, 1, 2, 4, 8, 7]
[4, 1, 2, 0, 3, 8, 6, 5, 7]

weigthed_shuffleest un générateur, vous pouvez donc échantillonner kefficacement les meilleurs éléments. Si vous voulez mélanger l'ensemble du tableau, il suffit d'itérer sur le générateur jusqu'à épuisement (en utilisant la listfonction).

MISE À JOUR:

L'échantillonnage aléatoire pondéré (2005; Efraimidis, Spirakis) fournit un algorithme très élégant pour cela. L'implémentation est super simple, et s'exécute également dans O(n log(n)):

def weigthed_shuffle(items, weights):
    order = sorted(range(len(items)), key=lambda i: -random.random() ** (1.0 / weights[i]))
    return [items[i] for i in order]

EDIT: Cette réponse n'interprète pas les pondérations de la manière attendue. Autrement dit, un article de poids 2 n'est pas deux fois plus susceptible d'être premier qu'un article de poids 1.

Une façon de mélanger une liste consiste à attribuer des numéros aléatoires à chaque élément de la liste et à les trier par ces numéros. Nous pouvons étendre cette idée, il suffit de choisir des nombres aléatoires pondérés. Par exemple, vous pouvez utiliser random() * weight. Des choix différents produiront des distributions différentes.

Dans quelque chose comme Python, cela devrait être aussi simple que:

items.sort(key = lambda item: random.random() * item.weight)

Veillez à ne pas évaluer les clés plus d'une fois, car elles se retrouveront avec des valeurs différentes.

Tout d'abord, permet de partir du fait que le poids d'un élément donné dans la liste à trier est constant. Cela ne changera pas entre les itérations. Si c'est le cas, alors ... eh bien, c'est un plus gros problème.

Par exemple, utilisons un jeu de cartes où nous voulons pondérer les cartes face vers l'avant. weight(card) = card.rank. En résumé, si nous ne savons pas, la distribution des poids est en effet O (n) une fois.

Ces éléments sont stockés dans une structure triée telle qu'une modification sur une liste de saut indexable de telle sorte que tous les index des niveaux soient accessibles à partir d'un nœud donné:

   1 10
 o ---> o -------------------------------------------- -------------> o Niveau supérieur
   1 3 2 5
 o ---> o ---------------> o ---------> o ---------------- -----------> o Niveau 3
   1 2 1 2 5
 o ---> o ---------> o ---> o ---------> o ----------------- ----------> o Niveau 2
   1 1 1 1 1 1 1 1 1 1 1 
 o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o Niveau inférieur

Tête 1er 2e 3e 4e 5e 6e 7e 8e 9e 10e néant
      Node Node Node Node Node Node Node Node Node Node

Cependant, dans ce cas, chaque nœud prend également autant de place que son poids.

Maintenant, lorsque vous recherchez une carte dans cette liste, vous pouvez accéder à sa position dans la liste en temps O (log n) et la supprimer des listes associées en temps O (1). Ok, ce n'est peut-être pas O (1), ce pourrait être O (log log n) (je devrais y penser beaucoup plus). La suppression du 6e nœud dans l'exemple ci-dessus impliquerait la mise à jour des quatre niveaux - et ces quatre niveaux sont indépendants du nombre d'éléments dans la liste (selon la façon dont vous implémentez les niveaux).

Le poids d'un élément étant constant, on peut simplement se passer de sum -= weight(removed)devoir traverser à nouveau la structure.

Et donc, vous avez un coût unique de O (n) et une valeur de recherche de O (log n) et un coût de retrait de la liste de O (1). Cela devient O (n) + n * O (log n) + n * O (1) qui vous donne une performance globale de O (n log n).

Regardons cela avec des cartes, car c'est ce que j'ai utilisé ci-dessus.

      dix
top 3 -----------------------> 4d
                                .
       3 7.
    2 ---------> 2d ---------> 4d
                  . .
       1 2. 3 4.
bot 1 -> Ad -> 2d -> 3d -> 4d

Il s'agit d'un très petit deck avec seulement 4 cartes. Il devrait être facile de voir comment cela peut être étendu. Avec 52 cartes, une structure idéale aurait 6 niveaux (log ₂ (52) ~ = 6), bien que si vous creusez dans les listes de sauts, cela pourrait être réduit à un plus petit nombre.

La somme de tous les poids est 10. Ainsi, vous obtenez un nombre aléatoire de [1 .. 10) et ses 4 Vous parcourez la liste de saut pour trouver l'élément qui est au plafond (4). Comme 4 est inférieur à 10, vous passez du niveau supérieur au deuxième niveau. Quatre est supérieur à 3, alors maintenant nous sommes au 2 des diamants. 4 est inférieur à 3 + 7, donc nous descendons au niveau inférieur et 4 est inférieur à 3 + 3, nous avons donc un 3 de diamants.

Après avoir retiré les 3 diamants de la structure, la structure ressemble maintenant à:

       7
top 3 ----------------> 4d
                         .
       3 4.
    2 ---------> 2d -> 4d
                  . .
       1 2. 4.
bot 1 -> Ad -> 2d -> 4d

Vous noterez que les nœuds occupent une quantité «d'espace» proportionnelle à leur poids dans la structure. Cela permet la sélection pondérée.

Comme cela se rapproche d' un arbre binaire équilibré, la recherche dans cela n'a pas besoin de parcourir la couche inférieure (qui serait O (n)) et à la place, aller du haut vous permet de sauter rapidement la structure pour trouver ce que vous cherchez pour.

Une grande partie de cela pourrait plutôt se faire avec une sorte d'arbre équilibré. Le problème est que le rééquilibrage de la structure lorsqu'un nœud est supprimé devient déroutant car il ne s'agit pas d'une structure arborescente classique et le ménage doit se rappeler que le 4 de diamants est maintenant déplacé des positions [6 7 8 9] vers [3 4 5 6] peut coûter plus cher que les avantages de la structure arborescente.

Cependant, bien que la liste de sauts se rapproche d'un arbre binaire dans sa capacité à sauter la liste en temps O (log n), elle a la simplicité de travailler avec une liste liée à la place.

Cela ne veut pas dire qu'il est facile de faire tout cela (vous devez toujours garder un œil sur tous les liens que vous devez modifier lorsque vous supprimez un élément), mais cela signifie seulement mettre à jour le nombre de niveaux que vous avez et leurs liens plutôt que tout à droite sur la structure arborescente appropriée.