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.

[tbc92]

@anapurna

Avec l'algorithme que je propose, on traite effectivement les éléments en commençant par les plus importants et en finissant par les moins importants.
Mais les moins importants se retrouveront en gros au milieu du tableau

Si je prends tous les éléments qui ont le même symbole (=le même chiffre) , et que je fais la moyenne de leurs rangs, j'obtiens toujours un nombre proche de (NE-1)/2. C'est l'un des objectifs que je vise. Je suppose que c'est aussi l'objectif visé par boboss123, mais je n'en suis pas sûr !

[boboss123]

Bonjour,

Merci pour toutes vos réponses

Ce que je voudrais, c'est que les files d'attentes soient positionnées avec une période la plus constante possible : pas besoin que l'ordre d’apparition des files d'attentes soit dans l'ordre décroissant de priorité vu que l'algo va traiter en boucle mes files d'attentes).
Plus une file d'attente est de niveau prioritaire, plus sa périodicité doit être constante.
=> Est-ce suffisant comme information ?

Parmis les solutions proposées, la solution de tbc92 semble la meilleure (à voir ce que ça donne dans tous les cas) :
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 -> 0 3 6 9 12 15 18 ...
=> Cependant les séquences "21 -> 25", "70 -> 74" et "98 -> 0" ne sont pas optimales : entre "21 -> 25" et "70 -> 74", on a 3 entrées alors qu'entre 98 et 0, on a 0 entrées. ça serait plus régulier si on avait de partout 2 entrées entre chaque parution de la file d'attente... cependant, à voir quel serait l'impact pour les autres files.

Remarque : le calcul sera effectué sur un µControlleur, j'aimerai donc éviter de faire des calculs sur des floatants pour éviter qu'il soit trop long.

[tbc92]

Si le système est un cycle (après 98, on repart à 0), alors effectivement, il faut adapter.
Peu de temps maintenant, mais je pense que'il faut prendre comme formule I*NE/NS , arrondi à l'entier le plus proche, pour le 1er symbole. (je crois que j'avais mal recopié ma formul dans mon message précédent).
En terme de temps de traitement, le fait de faire des calculs avec des nombres réels ne devraient vraiment pas poser de problème. Par contre, le traitement qui peut être un peu lent, c'est celui qui va intercaler le 2ème symbole dans les emplacements vide et ainsi de suite pour les symboles suivants.

Un problème bien formulé est un problème à moitié résolu : c'était essentiel de dire dès le début que tu voulais un système cyclique.

[boboss123]

Merci pour ces remarques.

Autrement, je pensais à un système comme celui :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
1-Pour chaque file d'attente, je calcule sa période et avec ça, je crée un tableau QueueInterval[queueCount]
2- J'initialise le tableau NextInterval[queueCount] avec les valeurs de QueueInterval[queueCount]
3- Ensuite je fais une boucle tant que je n'ai pas rempli ma liste de mes 99 éléments
   3a- je parcours mon tableau NextInterval[queueCount] et recherche quelle fille d'attente queueSelected à le nombre le plus petit
   3b- j'ajoute la file d'attente queueSelected à ma liste en cours de création
   3c- j'incrémente NextInterval[queueSelected] => NextInterval[queueSelected] = NextInterval[queueSelected] + QueueInterval[queueSelected]

Après là où j'ai un doute, c'est est-ce que je ne risque pas d'avoir des problèmes d'arrondis vu que je travaille sur des floats

Remarque : en contrainte, j'ai "le nombre d'éléments de ma liste doit être inférieur ou égal à 128".

[tbc92]

C'est peut-être bon, peut-être pas. C'est tellement incompréhensible que je ne sais pas estimer.