GrabBag data structure

J'ai trouvé cette description d'un TAD que je ne connaissais pas:

Citation:

---

The data structure GrabBag is similar to a stack or a queue, but instead of the first or last element being removed on a pop or dequeue, a random element is removed on a grab. Grabbags are very useful for simulating random draws without repetition, like drawing cards from a deck or numbers in a bingo game. Consider the following ADT:

• Insert(item e): e is inserted into the grabbag
• Grab(): if the grabbag is not empty, return a random element from the bag
• Size(): return how many items are in the grabbag
• List(): return a list of all items in the grabbag

---

En cherchant j'ai trouvé plusieurs implantations sub-optimales en temps (trop de random) et en espace (les noeuds portent trop d'information).
Ma question :

• c'est seulement un exercice pour étudiant ?
• ou bien c'est un TAD intéressant qui mérite une implantation optimale (pas très difficile à réaliser)

Ca permet de garantir a tout moment que la liste est en désordre. Mais Je ne vois pas trop l'intérêt de cette structure dans la vie courante, car généralement on cherche quelque chose de déterministe (FIFO/LIFO/...).

Citation:

---

Grabbags are very useful for simulating random draws without repetition, like drawing cards from a deck or numbers in a bingo game.

---

En relisant je comprends que c'est pour extraire un arrangement ou une combinaison.
Ça ne fait donc rien de bien nouveau (on a déjà 1000 questions à ce sujet sur ce forum), ce qui est nouveau c'est la formulation, au lieu d'être un algorithme implémentable ça devient un TAD plus abstrait.

Citation:

---

Envoyé par SpiceGuid

En relisant je comprends que c'est pour extraire un arrangement ou une combinaison.
Ça ne fait donc rien de bien nouveau (on a déjà 1000 questions à ce sujet sur ce forum), ce qui est nouveau c'est la formulation, au lieu d'être un algorithme implémentable ça devient un TAD plus abstrait.

---

hum... oui et non.

L'implémentation habituelle c'est, a un moment, de "mélanger" un TAD ordonné. Là il s'agit d'avoir en permanence un tas désordonné.

L'implémentation habituelle permet difficilement de gérer le parallélisme Insert()/Grab(), sauf a mélanger continuellement le TAD