hoko a écrit :
Bonjour,
j'aimerais faire une liste de n nombres entiers distincts compris entre x1 et x2 (x1 et x2 sont entiers >0)
j'ai fait une procédure où je compare à chaque fois ce que je viens de tirer avec mon début de liste. C'est un peu lent je tire quelques milliers de nombres à chaque fois... quelqu'un aurait-il un super truc mieux? Accessoirement, auriez vous des conseils généraux pour accélerer les choses quand on traite un grand nombre de données sur maple?
Remarque importante : je fais de la SI donc expliquez bien si votre truc est compliqué!
Edit : |x1-x2|>n
|
En termes d'algorithme, j'énumèrerai tous les entiers compris entre X1 et X2 dans une liste chainée. Je tire un nombre au hasard entre 1 et N, que je vais appeler X. Je retire le Xème nombre de mon tableau, et je relance un tirage aléatoire entre 0 et N-1.
Pour détailler : Admettons que tu veuilles tirer 3 chiffres au hasard entre 10 et 15.
Tu fais une liste chainée ( très efficace ici, je sais pas si c'est faisable en maple, mais l'idée est là ) ou un tableau :
10 11 12 13 14 15
Tu tires un nombre entre 1 et 6. Admettons que ce soit 4. Tu vas donc prendre le 4ème nombre, soit 13. Ton tableau devient :
10 11 12 14 15
Et tu tires un nombre entre 1 et 5. Admettons que ce soit 1, tu enlève le nombre 10 du tableau, il reste :
11 12 14 15
Tu tires entre 1 et 4, tu obtiens 3, donc tu enlèves le nombre 14 du tableau.
A la fin, tu as tiré 13, 10 et 14, en faisant uniquement 3 tirages aléatoire, soit une complexité n, ce qui est très efficace
( Pour la complexité n, c'est simple, on a grosso merdo ces tâches suivantes :
Enumérer les entier entre x1 et x2 et créer le tableau. Complexité x2-x1. N'arrive qu'une fois, donc pas pris en compte dans le calcul.
Tirer un entier entre 0 et n : complexité 1
Retirer un entier du tableau : complexité 1 ( si liste chainée )
Les deux dernières tâches sont exécutées autant de fois que d'entier sont tirés : complexité n.
Soit une complexité de l'ordre de n.
)
Message édité par Tetedeiench le 17-02-2006 à 16:52:15
---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !