Discussion :

[boboss123]

Bonjour,

J'ai 8 files d'attentes (numérotés de 0 à 7) et chaque file d'attente à un poids.

Ex :
- file 7 => poid = 25
- file 6 => poid = 17
- file 5 => poid = 1
- file 4 => poid = 33
- file 3 => poid = 2
- file 2 => poid = 6
- file 1 => poid = 3
- file 0 => poid = 12

Je cherche à créer un algo qui me permette de définir une séquence de traitement de mes files d'attente de manière à ce qu'elles soient traitées de manière uniformes.

Voilà où j'en suis :
1- je trie mes files d'attente en fonction de leur priorité (celle qui à le ppoid le plus élevé est la plus prioritaire)s les plus forts) :
- file 4 => poid = 33
- file 7 => poid = 25
- file 6 => poid = 17
- file 0 => poid = 12
- file 2 => poid = 6
- file 1 => poid = 3
- file 3 => poid = 2
- file 5 => poid = 1

2- Je détermine le nombre de traitement de ma séquence pour un cycle (c'est la somme des poids) :
33 + 25 + 17 + 12 + 6 + 3 + 2 + 1 = 99

3- Je calcule la période de la file d'attente la plus prioritaire :
99 / 33 = 3 => donc cette file d'attente, devra apparaitre avec une période de 3 dans ma séquence

4- Je commence à créer mon tableau de séquence (-1 signifie que l'entrée est encore vide et 4 est le numéro de ma file d'attente la plus prioritaire):
4 -1 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4 -1 -1 -1 4....


Comment faire pour positionner les autres files d'attentes dans ma séquence (je bloque) ?

Merci d'avance,

[pLOPeGG]

Une proposition : pourquoi ne pas générer une permutation aléatoire d'une liste contenant les numéros de file autant de fois que leur poids ?
Ainsi si une file N a une importance de 30, le numéro N apparaîtra 30 fois dans ta liste permutée, soit 30 fois plus qu'une file de poids 1.
C'est une solution très rapide à calculer, et sur le long terme les liste seront traitées de manière uniforme (en terme de probabilités) avec la possibilité de changer la permutation en fin de cycle pour en commencer un nouveau.

[tbc92]

N'allons pas trop vite. Avant de passer à la 2ème file, est-ce que ce que tu proposes pour la 1ère file est bon ? Tu as vérifié ?

Tu proposes 4-1-1-1-4-1-1-1-4-1-1 etc etc.
Je vais noter 4-*-*-*-4-*-*-*-4-*-* ... pour éviter les confusions, car il y a une autre file qui porte le n°1. Au moins, avec le symbole *, on sait que c'est un emplacement qui n'est pas affecté.
Déjà, sur cette bases, on est mal parti.
J'intercalerais seulement 2 cases * entre les cases '4' , et non 3 comme tu l'as fait. Donc : 4-*-*-4-*-*-4-*-* etc. Ainsi, quand on arrive à 99 symboles, on finit par 4-*-*, et on a bien 33 fois le symbole 4.

Ca, c'est à peu prèsok.
Mais ici, c'était un cas simple : 33 fois le chiffre 4 sur un total de 99, la division de 99 par 33 tombe juste, c'est trop facile. Imaginons le cas où on a au total 17 cases , et on veut 6 cases avec le symbole 4. Comment on répartit nos 6 cases parmi 17. Je prend volontairement des petits nombres pour éviter les etc à la fin de la ligne.
Idem, que veux-tu comme répartition si on a 5 symboles 4 à répartir sur 18 emplacements ...

D'ailleurs, je pense que dans le 1er cas, ce que tu voulais, c'était que ça commence avec un 4, mais aussi que ça finisse avec un 4.

Quand le cas du 1er symbole sera bien cerné, avec des équations correctes, et robustes, la suite devrait pouvoir se faire facilement.

[Nebulix]

Je n'ai pas vraiment compris le problème et je pense que la difficulté vient ( comme souvent ) de ce que tu ne sais pas vraiment ce que tu veux. Je te conseille de bien tout préciser d'abord pour toi-même. La solution sera beaucoup plus facile, voire évidente.

[tbc92]

Reprenons.
On a NE emplacements. NE = 99 dans l'exemple. Ces emplacements sont numérotés de 0 à NE-1 ; s'ils sont numérotés de 1 à NE, il faut adapter.
On a NS symboles. NS = 33 dans l'exemple. Les symboles sont numérotés de 0 à NE-1
Nos 33 symboles, on les met aux emplacements i*(NE-1) /NS ; cette opération donne un nombre qui n'est pas forcément un entier ; on arrondit systématiquement à l'entier le plus proche. i varie entre 0 et NE-1.

Ceci nous permet de placer les 33 symboles régulièrement;
Ici, nos 33 symboles seront aux emplacements :0 3 6 9 12 15 18 21 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 74 77 80 83 86 89 92 95 98
En gros , une case sur 3 est occupée par notre symbole, mais avec des petites irrégularités.
Ces irrégularités sont nécessaires.

Il nous reste 66 cases disponibles. Pour le 2ème symbole, on procède de la même façon. On a 66 cases disponibles, on les numérote de 0 à 65 ; on veut placer 25 éléments sur ces 66 cases; on les place aux emplacements i*65/24 , avec i variant de 0 à 24.
Et ainsi de suite, pour les symboles suivants.

[anapurna]

salut

avec cette solution il y a de grande chance que le plus petit element soit le dernier traité
vouloir définir sa priorité par le nombre n'est pas forcement une bonne solution
existe t'il d'autre critères ?

[Flodelarab]

Bonjour

Décrémentons les poids. Simplement. Jusqu'à ce qu'ils soient tous nul.

4 7 6 0 2 1 3 5 4 7 6 0 2 1 3 4 7 6 0 2 1 4 7 6 0 2 4 7 6 ... etc ... 4 4 4 4.