[Python] Generalizzando: algoritmi di calcolo
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), (10, 101000)] s2ev = [(9154, 9307), (9340, 10442), (87361, 98214)] quindi l'evento s1ev è cominciato a 1723 e finito a 18550, riprende a 10 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), (10, 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? Grazie! Ciao ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] Generalizzando: algoritmi di calcolo
2009/10/19 > 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), (10, 101000)] > s2ev = [(9154, 9307), (9340, 10442), (87361, 98214)] > > quindi l'evento s1ev è cominciato a 1723 e finito a 18550, riprende a > 10 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), (10, 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), (10, 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, 10], [101000, 0]] 1 [[1723, 9154], [9307, 9340], [10442, 18550], [87361, 98214], [10, 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 ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] Generalizzando: algoritmi di calcolo
Questa versione non inserisce l'ultimo intervallo spurio da 0 eventi attivi: s1ev = [(1723, 18550), (10, 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 if ends: actives[actives_count].append([x, 0]) -- http://thinkcode.tv - Prossimamente su questi schermi http://beri.it - Blog di una testina di vitello http://stacktrace.it - Aperiodico di resistenza informatica ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] Generalizzando: algoritmi di calcolo
2009/10/19 Marco Beri : > Questa versione non inserisce l'ultimo intervallo spurio da 0 eventi attivi: > > s1ev = [(1723, 18550), (10, 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 > if ends: > actives[actives_count].append([x, 0]) > > E' perfetto, grazie mille. Il codice mi è un po' oscuro, quindi ora mi metto con l'interprete ad eseguire passo passo i tuoi statement e vedere come costruisci il tutto. Grazie! ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
