Discussion :

[Valou6323]

Bonjour à tous,

nouveau sur ce site j'aurais besoin de conseil de pro ..

j'ai besoin définir une file d'attente en C++ à partir de priorité de de position d'arriver

ENONCE
File d’attente élaboré

Un patient a un nom et un type. Il y a trois types de patients T1 : les très urgent ; T2 : urgent et T3 : non urgent.

J’ai une file d’attente unique (salle d’attente) pour ces trois types de patients. La règle est : a priorité égale, premier arrivée premier servi », sinon le T1 passent devant les T2 qui passent devant les T3.

Exemple : file vide. Arrivent « Joe, T3 » puis « Jack T3 » puis « William » T2. La file est <William, Joe, Jack>. Le médecin se libère, il traite donc « William ». Arrivent « Lucky Luke T1 » puis « Avrell T2 ». On a donc <Lucky Luke, Avrell, Joe, Jack>. Arrivent ensuite « Jessie James T1 », « Billy the Kid T2 » et « Ma Dalton T3 ». On a donc <Lucky Luke, Jessie James, Avrell, Billy the Kid , Joe, Jack, Ma Dalton>.

Le programme doit pouvoir (menu principal en fait) :
- Afficher la liste en cours ;
- Ajouter une personne ;
- Supprimer le premier de la file ;
- Sauvegarder/récupérer la file.

Si quelqu'un a deja fait ca ou c'est me dire comment gérer le file d'attente, ce serai gentil ;-)

merci

[Aleph69]

Bonjour,

où bloques-tu exactement?

[Klaim]

Cela te donnerai la solution à cet exercice.

Il serait plus interessant pour toi de te poser les bonnes questions en lisant le problème:
- qu'est-ce qu'une file d'attente, de manière abstraite? quel est son role?
- qu'est-ce que va contenir ta file?
- quelles sont les actions a effectuer?
- etc...

Je t'ai donnée des premiers indices.

[JolyLoic]

Si quelqu'un a deja fait ca ou c'est me dire comment gérer le file d'attente, ce serai gentil ;-)

std::priority_queue...

[poukill]

std::priority_queue...

Afin de gagner du temps, je me propose d'anticiper la suite :

Oui, mais j'ai pas le droit....

[koala01]

Salut,

Le principe est assez trivial et peut s'envisager sous la forme de

Code :

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

1
2
3
4
5
Si  Priorité de l'élément à insérer inférieure a un élément testé
    passer à l'élément précédent dans la file
Sinon
    insérer l'élément entre l'élément testé et son suivant
Fin Si

Reste à savoir:

1. comment comparer la priorité des éléments à insérer
2. comment insérer un élément entre deux autres
3. comment relier les différents élément les un aux autres

A toi de jouer

[JolyLoic]

Afin de gagner du temps, je me propose d'anticiper la suite :

Oui, mais j'ai pas le droit....

Sauf le droit de s'en inspirer ?

[bacelar]

Vu l'algo, je ne me serais pas enquiquiner.
Trois files en fonction du type de patient et récupération dans la liste de plus haut priorité non vide.
Reste plus que le verrouillage des inserts durant le scan des 3 files.

[koala01]

Vu l'algo, je ne me serais pas enquiquiner.
Trois files en fonction du type de patient et récupération dans la liste de plus haut priorité non vide.

Tu imagine la difficulté de l'algorithme, si tu le fais ainsi

L'insertion serait effectivement facile, mais pour le reste, tu tombe sous une forme proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
Pour Renvoyer le patition de plus haute priorité
 
si urgent non vide
    renvoyer urgent top
sinon 
    si moyen non vide
        renvoyer moyen top
    sinon 
        si non_urgent non vide
            renvoyer non_urgent top
        fin si
    fin si
fin si
renvoyer rien
 
 
Pour sortir un patient de la liste
si patient:priorite egal urgent
    retirer urgent top
    sinon 
    si patient: priorite égal moyen
        retirer moyen top
    sinon 
        si patient:priorite égal non_urgent
            retirer non_urgent top
        fin si
   fin si
fin si

Si tu places tous les patients dans une seule et même liste, l'insertion sera certes un peu plus lente, mais le reste de la gestion se fera beaucoup plus rapidement, vu que tu évite les tests
[/QUOTE]Reste plus que le verrouillage des inserts durant le scan des 3 files.[/QUOTE]Ce serait plus problématique que cela...

Tu utiliserais sans doute le double check; verrouiller, tester si vide, déverrouiller retester.

Avec trois listes, rien ne t'empêche d'ajouter un élément dans les listes sur lesquelles tu ne travaille pas (il serait dommage de verrouiller les trois listes alors que tu ne travailles que sur une).

tu devrais donc revérifier les listes de priorité supérieure lors deux deuxième test Encore du temps de perdu

[Luc Hermitte]

Le prix d'un déplacement pour insertion me parait tellement aberrant, que je foncerai sans hésiter une seule seconde vers la triple file -- si NIH interdisant la solution standard.

Quant au lock ... le temps des déplacements est tel, que c'est pour moi un argument de plus en faveur de la triple file -- un seul lock global suffisant amplement comparé à 3 micro-locks (et si on a accès à des listes lock-free, le problème ne se pose pas)(quant à l'aspect : un cas urgent arrive alors que l'on pioche la fiche d'un cas de moindre priorité, c'est tant pis, il faut rester simple).

Maintenant, j'ai tendance à supposer qu'il y a beaucoup d'éléments dans la queue pour justifier un système de passe-droits. La dimension du problème est à étudier avant de valider la meilleure des approches.

[JolyLoic]

Le prix d'un déplacement pour insertion me parait tellement aberrant, que je foncerai sans hésiter une seule seconde vers la triple file

Il me parait tellement aberrant, que j'utiliserais peut-être une structure de base où il n'existe pas (liste chaînée).