Petit problème de logique à résoudre

Version imprimable

05/01/2010, 21h33
Ggamer

Petit problème de logique à résoudre

Bonjour à tous et meilleurs voeux,

J'ai un petit problème de logique à résoudre en Python. Ce n'est sûrement pas compliqué mais je n'arrive pas à trouver la solution... Imaginons :

J'ai une liste de personnes ayant été présents sur la journée de mardi. Par exemple :

- Marcel : 10h00>12h00
- Philippe : 09h00>11h00
- David : 09h00>15h00

Je souhaite savoir combien de personnes étaient présentes à chaque moment de la journée :

Donc avec mon exemple :
- De 09:00 à 10:00 : 2 personnes
- De 10:00 à 11:00 : 3 personnes
- De 11:00 à 12:00 : 2 personnes
- De 12:00 à 15h00 : 1 personne

MAIS QUELLE MÉTHODE UTILISER POUR Y ARRIVER ?

Je vous serai reconnaissant de me donner un coup de pouce. Cela ne doit pas être bien sorcier....

Merci !

PS : J'ai utilisé, pour la lisibilité, des heures en mode texte, mais j'utiliserai bien-sûr des datetime pour les stocker et les traiter.
05/01/2010, 22h46
josmiley

ça dépend de la structure de la 'liste' ...
05/01/2010, 22h52
Ggamer

Et bien, c'est au choix. Ce peut-être une liste ou un dictionnaire... du genre {"Marcel" : ("10:00", "12:00") } par exemple...

Bonjour,

Voilà comment je ferais au plus simple:

On résume l'occupation par une simple liste de plage horaire:

Code:

P = [[10,12],[9,11],[9,15]]

Et à la question "combien de personnes y avaient-il à l'heure h?", par exemple ici h=10:
Code:

1 2 3 4 5 6 7 8 h = 10 c = 0 # =compteur for h1,h2 in P: if h>=h1 and h<h2: c += 1 print "A", h, "heures, il y avait",c, "personne(s)"
Ce qui donne bien tous les résultats que tu cites. (et il faut bien sûr remplacer les entiers par des datetime python).

A noter que ça marche toujours si une personne est présente pendant plusieurs plages d'une même journée.

A noter aussi qu'il est facile de fournir le nom des personnes présentes à l'heure h, si on les ajoute dans les listes des plages horaires. Ce qui donne, par exemple, le code suivant:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 P = [["Marcel",10,12],["Philippe",9,11],["David",9,15]] h = 10 c = 0 n = [] for nom,h1,h2 in P: if h>=h1 and h<h2: c += 1 n.append(nom) print "A", h, "heures, il y avait",c, "personne(s), qui sont:",n
Ce qui donne bien, pour h=10:
Code:

1 2 A 10 heures, il y avait 3 personne(s), qui sont: ['Marcel', 'Philippe', 'David']
Tyrtamos

06/01/2010, 11h35
eyquem
ce serait y pas mieux ? :

Code:

c = sum( h1<=h<h2 for h1,h2 in P )
Code:

1 2 n = [ nom for nom,h1,h2 in P if h1<=h<h2 ] c = len(n)
06/01/2010, 11h39
ju_bicycle

Ahh les listes de compréhension...
Mieux je sais pas, plus court surement...
Ceci dit c'est généralement plus dificile a comprendre.
D'ailleurs je voulais savoir, dans le cas général le programme tourne plus vite avec des boucles ou des listes de compréhension ?

On pourrait aussi utiliser filter pour résoudre le problème (mais je trouve ça particulièrement pas compréhensible).

Code:

1
2
 
filter(lambda x: x[0] < h < x[1], P)

Citation:

Envoyé par ju_bicycle

Ahh les listes de compréhension...
Mieux je sais pas, plus court surement...
Ceci dit c'est généralement plus dificile a comprendre.
D'ailleurs je voulais savoir, dans le cas général le programme tourne plus vite avec des boucles ou des listes de compréhension ?

Les compréhensions de liste sont effectivement assez vite incompréhensibles, elles sont à garder pour des cas simples (et je trouve que celui-ci l'est).
En général, et d'après ce que j'ai pu en lire ici et là, les compréhensions de liste sont + rapides que les boucles.
Et puis, on peut en faire des générateurs assez facilement, ce qui permet d'améliorer la vitesse du code qui s'en sert s'il doit juste itérer dessus.

Bon, comme il vaut mieux mesurer plutôt que de se fier aux "on dit que" :

Code:

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
30
31
32
33
34
35
36
37
 
def presenceloop(hour, presences):
    result = []
    for name, start, end in presences:
        if start <= hour <= end:
            result.append(name)
    return result
 
def presencecomprehension(hour, presences):
    return [name for name, start, end in presences if start <= hour <= end]
 
def presencefilter(hour, presences):
    return filter(lambda presence: presence[1] <= hour <= presence[2], presences)
 
def comparepresences():
    from timeit import Timer
    from random import randint
 
    # Horaires de présence : de 7h à 21h (ils ont posé des 1/2-journée).
    hour = randint(7, 21)
    # Pour ne pas me prendre la tête, je donne un numéro à chacun (tant pis
    # pour Patrick McGoohan).
    presences = [[str(x)] + sorted([randint(7, 21), randint(7, 21)]) for x in range(100)]
 
    print 'seeking number of people present at', hour
    print presences
    print '*' * 40
 
    for func in (presenceloop, presencecomprehension, presencefilter):
        stmt = '{0}({1}, {2})'.format(func.__name__, hour, presences)
        setup = 'from {0} import {1}'.format(func.__module__, func.__name__)
        timer = Timer(stmt, setup)
        print 'Benchmarking', func.__name__
        # timer.timeit execute le code 1'000'000 de fois.
        print timer.timeit()
        print 'result:', func(hour, presences)
        print '*' * 40

Résultat :

Code:

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
30
31
32
33
34
35
36
37
38
39
 
seeking number of people present at 13
[['0', 9, 20], ['1', 12, 14], ['2', 8, 12], ['3', 18, 19], ['4', 13, 14], ['5', 12, 14], ['6', 12, 15], ['7', 8, 21], ['
8', 9, 13], ['9', 8, 16], ['10', 10, 17], ['11', 8, 10], ['12', 12, 17], ['13', 14, 18], ['14', 10, 21], ['15', 14, 14],
 ['16', 16, 20], ['17', 7, 20], ['18', 14, 18], ['19', 9, 12], ['20', 10, 13], ['21', 9, 14], ['22', 15, 15], ['23', 9,
10], ['24', 18, 21], ['25', 15, 21], ['26', 17, 18], ['27', 14, 17], ['28', 10, 13], ['29', 11, 17], ['30', 17, 19], ['3
1', 12, 14], ['32', 11, 15], ['33', 14, 19], ['34', 12, 18], ['35', 12, 13], ['36', 7, 12], ['37', 15, 18], ['38', 20, 2
1], ['39', 10, 16], ['40', 13, 14], ['41', 8, 16], ['42', 13, 15], ['43', 10, 19], ['44', 10, 16], ['45', 13, 13], ['46'
, 12, 16], ['47', 16, 16], ['48', 11, 13], ['49', 19, 20], ['50', 16, 21], ['51', 7, 15], ['52', 15, 17], ['53', 15, 19]
, ['54', 7, 9], ['55', 10, 11], ['56', 13, 15], ['57', 11, 17], ['58', 10, 18], ['59', 11, 12], ['60', 10, 13], ['61', 9
, 11], ['62', 11, 16], ['63', 16, 19], ['64', 10, 11], ['65', 13, 16], ['66', 8, 9], ['67', 18, 19], ['68', 17, 19], ['6
9', 9, 21], ['70', 16, 20], ['71', 7, 20], ['72', 12, 14], ['73', 10, 15], ['74', 17, 19], ['75', 11, 11], ['76', 19, 19
], ['77', 8, 13], ['78', 10, 18], ['79', 14, 16], ['80', 11, 12], ['81', 7, 20], ['82', 8, 20], ['83', 16, 20], ['84', 9
, 21], ['85', 12, 18], ['86', 13, 15], ['87', 9, 19], ['88', 12, 14], ['89', 7, 9], ['90', 12, 14], ['91', 7, 11], ['92'
, 20, 21], ['93', 8, 9], ['94', 8, 13], ['95', 7, 20], ['96', 18, 20], ['97', 8, 13], ['98', 8, 8], ['99', 11, 16]]
****************************************
Benchmarking presenceloop
42.5548161853
result: ['0', '1', '4', '5', '6', '7', '8', '9', '10', '12', '14', '17', '20', '21', '28', '29', '31', '32', '34', '35',
 '39', '40', '41', '42', '43', '44', '45', '46', '48', '51', '56', '57', '58', '60', '62', '65', '69', '71', '72', '73',
 '77', '78', '81', '82', '84', '85', '86', '87', '88', '90', '94', '95', '97', '99']
****************************************
Benchmarking presencecomprehension
37.2302801881
result: ['0', '1', '4', '5', '6', '7', '8', '9', '10', '12', '14', '17', '20', '21', '28', '29', '31', '32', '34', '35',
 '39', '40', '41', '42', '43', '44', '45', '46', '48', '51', '56', '57', '58', '60', '62', '65', '69', '71', '72', '73',
 '77', '78', '81', '82', '84', '85', '86', '87', '88', '90', '94', '95', '97', '99']
****************************************
Benchmarking presencefilter
48.3513078009
result: [['0', 9, 20], ['1', 12, 14], ['4', 13, 14], ['5', 12, 14], ['6', 12, 15], ['7', 8, 21], ['8', 9, 13], ['9', 8,
16], ['10', 10, 17], ['12', 12, 17], ['14', 10, 21], ['17', 7, 20], ['20', 10, 13], ['21', 9, 14], ['28', 10, 13], ['29'
, 11, 17], ['31', 12, 14], ['32', 11, 15], ['34', 12, 18], ['35', 12, 13], ['39', 10, 16], ['40', 13, 14], ['41', 8, 16]
, ['42', 13, 15], ['43', 10, 19], ['44', 10, 16], ['45', 13, 13], ['46', 12, 16], ['48', 11, 13], ['51', 7, 15], ['56',
13, 15], ['57', 11, 17], ['58', 10, 18], ['60', 10, 13], ['62', 11, 16], ['65', 13, 16], ['69', 9, 21], ['71', 7, 20], [
'72', 12, 14], ['73', 10, 15], ['77', 8, 13], ['78', 10, 18], ['81', 7, 20], ['82', 8, 20], ['84', 9, 21], ['85', 12, 18
], ['86', 13, 15], ['87', 9, 19], ['88', 12, 14], ['90', 12, 14], ['94', 8, 13], ['95', 7, 20], ['97', 8, 13], ['99', 11
, 16]]
****************************************

On peut voir ici que la compréhension de liste est la + rapide pour ce qui est de la construction de la liste.
S'il s'agit simplement de compter le nombre d'éléments de la liste, la version de Tyrtamos est légèrement + rapide que la compréhension de liste, car c'est la seule méthode qui ne cherche pas à construire la liste mais juste à compter.
Je ne vous polluerais pas + avec du code et du résultat, vous pouvez essayer vous-même pour vérifier.

Oublions vite filter, qui n'est ni compréhensible, ni rapide et qui ne donne même pas un résultat identique aux autres.

J'avais compris la question initiale différemment, en ce qu'il fallait construire la liste des intervalles de temps avec le nombre de personnes présentes.

Voici ma solution:

Code:

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
P = [(10,12),(9,11),(9,15),(11,13)]
 
# déterminer les moments où il y a des arrivées et des départs
moments = list(reduce(set.union, (set(x) for x in P)))
moments.sort()
 
# déterminer les présences entre ces moments
presents = 0
presences = []
for i in xrange(len(moments)-1):
    m = moments[i]
    presents += sum((entree == m) - (sortie == m) for entree, sortie in P)
    presences.append((m, moments[i+1], presents))
 
#optionnel: fusionner les intervalles adjacents si les présences sont identiques
pr = [presences.pop(0)]
for p in presences:
    _,fin,n = p
    debut,_,n0 = pr[-1]
    if n == n0:
        pr[-1] = (debut,fin,n)
    else:
        pr.append(p)
presences = pr
 
for p in presences:
    print "De %dh à %dh : %d personnes" % p

Résultat:

Code:

1
2
3
4
De 9h à 10h : 2 personnes
De 10h à 12h : 3 personnes   # intervalles fusionnés
De 12h à 13h : 2 personnes
De 13h à 15h : 1 personnes

Bonjour,

Effectivement, on peut comprendre la question comme ça.

La modif que je ferais par rapport à ma solution est la suivante:

Je prends toutes les heures de début et de fin de plages horaires dans une liste (en éliminant les redondances) et je trie la liste: j'ai donc dans l'ordre chrono toutes les heures qui correspondent aux arrivées et départs.

Cela donne le nouveau code suivant:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 P = [["Marcel",10,12],["Philippe",9,11],["David",9,15]] B = [] for nom,h1,h2 in P: if h1 not in B: B.append(h1) if h2 not in B: B.append(h2) B.sort() print "début à", B[0], "heures" for i in xrange(0,len(B)-1): n = [] for nom,h1,h2 in P: if h1<=B[i]<h2: n.append(nom) c = len(n) print "entre", B[i], "heures et", B[i+1], "heures, il y a", c, "personne(s):",n print "Il n'y plus personne à partir de", B[-1], "heures"
Qui affiche:
Code:

1 2 3 4 5 6 7 début à 9 heures entre 9 heures et 10 heures, il y a 2 personne(s): ['Philippe', 'David'] entre 10 heures et 11 heures, il y a 3 personne(s): ['Marcel', 'Philippe', 'David'] entre 11 heures et 12 heures, il y a 2 personne(s): ['Marcel', 'David'] entre 12 heures et 15 heures, il y a 1 personne(s): ['David'] Il n'y plus personne à partir de 15 heures
Pour trier les heures, j'ai pris ici des nombres, ce qui rend le pb très simple. Qu'en est-il si on prend des vrais temps?

1ère solution avec des chaines: plutôt que d'utiliser des datetime, on peut tout simplement utiliser des chaines "hhmm" (comme "1015" pour 10h 15mn) ou avec les dates "aaaammjjhhmm" (comme "201001071015" pour la même heure aujourd'hui). En effet, rangé comme cela, l'ordre chronologique des temps coïncide avec l'ordre alphabétique des chaines. Mais, bien sûr, on ne peut pas faire d'opération entre les temps de cette façon.

2ème solution avec des datetime: je ne sais pas si le tri peut se faire directement avec des datetime, mais si ce n'est pas le cas, la méthode de tri sort() accepte comme argument une fonction de comparaison qui permet de trier n'importe quoi: il suffit de la définir.

Tyrtamos

07/01/2010, 09h20
Ggamer

Eh bien, je vois que vous avez été inspirés ! :ccool:

Moi aussi puisque de mon côté, j'ai également fini par trouvé une solution... qui est celle de tyrtamos. Si j'avais su, je vous aurai consulté plus tôt :roll:

Merci pour votre aide

Bonne journée.