[Python] Generalizzando: algoritmi di calcolo

[Marco Beri]

2009/10/19 <michele a nectarine.it>

> Salve a tutti,
> ho un problema interessante che vorrei discutere con voi.
> In generale, sono interessato a due eventi che sono intermittenti (=
> iniziano e finiscono casualmente) e concorrenti (= capitano
> contemporaneamente e non).
>
> Per capirci meglio, in input ho due liste che contengono gli istanti
> di (inizio, fine) dei due eventi:
> s1ev = [(1723, 18550), (100000, 101000)]
> s2ev = [(9154, 9307), (9340, 10442), (87361, 98214)]
>
> quindi l'evento s1ev è cominciato a 1723 e finito a 18550, riprende a
> 100000 e termina a 101000, etc.
>
> Ora, supponendo di tracciare una linea temporale unica e dato che i
> due eventi s1 e s2 sono sincronizzati sulla stessa linea temporale,
> vorrei calcolare:
> a) gli istanti di tempo (inizio, fine) in cui gli eventi sono entrambi
> attivi [s1ev and s2ev]
> b) gli istanti di tempo (inizio, fine) in cui esattamente *un* evento
> (non specifico quale è attivo [s1ev xor s2ev]
> c) gli istanti di tempo (inizio, fine) in cui *nessun* evento è attivo
> [!s1ev and !s2ev]
>
> Date le premesse, riesco a calcolare il punto a) in questo modo:
> s1ev = [(1723, 18550), (100000, 101000)]
> s2ev = [(9154, 9307), (9340, 10442), (87361, 98214)]
>
> # end = [1]
> # begin = [0]
>
> print 'both: '
> for s1 in s1ev:
>     for s2 in s2ev:
>         if s1[0] > s2[0] and s1[1] < s2[1] \
>         or s1[0] < s2[0] and s1[1] > s2[1] \
>         or s1[0] < s2[0] and s1[1] < s2[1] \
>         or s1[0] > s2[0] and s1[1] > s2[0]:
>             begin = max(s1[0],s2[0])
>             finish = min(s1[1],s2[1])
>             if (finish > begin):
>                 print str(begin) + '-' + str(finish)
> In questo modo ottengo:
> both:
> 9154-9307
> 9340-10442
>
> che sono gli istanti (inizio, fine) in cui entrambi gli eventi sono attivi.
>
> Tentando di implementare il punto b), mi sono accorto di un problema:
> print 'only one: '
> for s1 in s1ev:
>     for s2 in s2ev:
>             if s1[0] < s2[0] and s1[1] < s2[1] \
>             or s1[0] > s2[0] and s1[1] > s2[1]:
>
> tecnicamente: se s1 è iniziato prima o dopo di s2 (cioè hanno
> intersezione vuota), allora dovremmo avere che s1 è evento singolo
> (cioè soddisfa la condizione del punto b)). Tuttavia, la condizione
> non funziona, visto che (1723, 18550) soddisfa la condizione, ma
> sappiamo che da 9154 in avanti gli eventi sono entrambi presenti...
>
> Quindi chiedo a voi, come impostereste la condizione di verifica del punto
> b)?
> Per il punto c), invece, non ho ancora pensato ad una strategia.
> Dove sto sbagliando?
>

Non lo so, io il tutto lo farei cosi`:

s1ev = [(1723, 18550), (100000, 101000)]
s2ev = [(9154, 9307), (9340, 10442), (87361, 98214)]

starts = sorted(s[0] for s in s1ev + s2ev)
ends = sorted(s[1] for s in s1ev + s2ev)

actives = [[] for x in range(3)]
actives[0] = [[0, 0]]

actives_count = 0
while ends:
    if starts and starts[0] < ends[0]:
        x = starts.pop(0)
        inc = 1
    else:
        x = ends.pop(0)
        inc = -1
    actives[actives_count][-1][1] = x
    actives_count += inc
    actives[actives_count].append([x, 0])

for n, active in enumerate(actives):
    print n, active

Se lo eseguo viene fuori questo:
0 [[0, 1723], [18550, 87361], [98214, 100000], [101000, 0]]
1 [[1723, 9154], [9307, 9340], [10442, 18550], [87361, 98214], [100000,
101000]]
2 [[9154, 9307], [9340, 10442]]

Il numero a inizio riga dice quanti eventi sono attivi.
Può andarti bene?

Se ti va bene puoi anche generalizzare a n eventi contemporanei cambiando le
prime righe.

Ciao.
Marco.

-- 
http://thinkcode.tv - Prossimamente su questi schermi
http://beri.it - Blog di una testina di vitello
http://stacktrace.it - Aperiodico di resistenza informatica
-------------- parte successiva --------------
Un allegato HTML è stato rimosso...
URL: http://lists.python.it/pipermail/python/attachments/20091019/198eee05/attachment.htm