unire due liste di tuple con timestamp e coda lunghezze

Question

Il problema: Ho due liste che contengono tuple (ciascuna composta di un timbro di tempo e di una coda di lunghezza) che devono essere fuse:

L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]] 

L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]] 

ho bisogno di una funzione che restituisce merge(L1,L2):

[[ 0.00, 50+80 ], 
[ 7.75, 120+80 ], 
[ 8.00, 120+120], 
[10.00, 85+120], 
[10.25, 70+80 ], 
[17.00, 100+80 ], 
[20.00, 60+80 ]] # note 

[nota: non ho bisogno del 60+80 - si tratta semplicemente di indicare quali valori vengono aggiunti la ri Sult di 60+80 = 140 è quello che mi serve]

Quello che ho estratto dalla uscita di cui sopra è che io sono più volte:

• Popping il valore più piccolo V dalla lista fusione di timestamp distinti (il sindacato setwise di timestamps).
• Aggiunta della lunghezza della coda dall'elenco non V di timestamp minore o uguale a V.
• ... fino a V esaurito.

Il mio problema: Sono abbastanza sicuro che heapq può risolverlo, ma non si può ottenere la mia testa intorno a come strutturare la soluzione utilizzando il heapq-modulo.

Maggiori dettagli vagante del processo:

1. Nella prima fase - alle 0.00 e fino alle 7,75 la lunghezza della coda composto è 50+80 - tratto da L1[0][0] == L2[0][0]
2. posso aggiungere i valori L1[0][1]+L2[0][1] = 50+80. Ora ho usato L1[0][:] e L2[0][:]
3. Nella seconda fase - alle 7,75 - la coda di L2 non è aumentata, ma la coda di L1 ha: L1[1][0] = 120. Per ottenere la lunghezza della coda composta è quindi necessario aggiungere L1[1][1] con L2[0][1] per ottenere 120+80.
4. Ora ho usato il primo valore più grande di qualsiasi altro registrato in precedenza e lo devo fare per i passaggi successivi fino a quando gli intervalli di tempo non sono stati esauriti (dopo 23.99). Il prossimo valore più grande nel set di "time" è L2[1][0] che è 8,00.
5. Poiché 8,00 è più grande di 7,75 ho bisogno di unire questi valori in modo che alle 8.00 la lunghezza della coda sia 120 + 120 in base al valore più grande di L1 che è inferiore a 8,00 - che è 7,75. Con la presente aggiungo L1 1 e L2 1.
6. Nel passaggio successivo il valore maggiore non utilizzato è 10,00 da L2. La lunghezza della coda da L2 deve essere unita al valore maggiore L1, ovvero minore o uguale a 10.00 ...
7. E così continua ...

Answer 1

iterare gli eventi nell'ordine in cui accadono, e mantenere il timestamp dell'ultima operazione (last_time), in modo che se il prossimo evento ha la stessa ora, ma proviene dalla altra coda, i due le modifiche verranno unite in un articolo in result.

def merge(a, b): 
    l1 = [(t, value, 1) for (t, value) in a] 
    l2 = [(t, value, 2) for (t, value) in b] 
    events = l1 + l2 
    events.sort() 
    last_time = -1 
    result = [] 
    c1 = 0 
    c2 = 0 
    for t, value, index in events: 
     if index == 1: 
      c1 = value 
     if index == 2: 
      c2 = value 
     if t == last_time: 
      result.pop() 
     result.append((t, c1 + c2)) 
     last_time = t 
    return result 

In [26]: L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]] 
     L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]] 

     merge(L1, L2) 

Out[26]: [(0, 130), (7.75, 200), (8, 240), (10, 205), (10.25, 150), (17, 180), (20, 140)] 

Answer 2

Si potrebbe anche fare in questo modo:

def merge(z): 
    previous=None 
    l=[] 
    z.sort() 
    for i in range(len(z)): 
     if i==len(z)-1: 
      if previous==z[i][0]: 
       continue 
      else: 
       l.append([float(z[i][0]),z[i][1]) 
     elif previous is None: 
      previous=z[i][0] 
      l.append([float(z[i][0]),z[i][1]+z[i+1][1]]) 
     else: 
      if previous==z[i][0]: 
       continue 
      if z[i][0]<=z[i+1][0]: 

       l.append([float(z[i][0]),z[i][1]+z[i-1][1]]) 
      else: 
       l.append([float(z[i][0]),z[i][1]+z[i+1][1]]) 

    return l 
L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]] 
L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]] 
z=L1+L2 
print merge(z) 

uscita:

[[0.0, 130], [7.75, 200], [8.0, 240], [10.0, 205], [10.25, 155], [10.25, 150], [17.0, 180], [20.0, 60]] 

Answer 3

Ispirato da galath's solution, ho cercato di trovare una soluzione per più di due ingressi:

def merge(tup): 
    events = list(); 
    i = 0 # ;-) Well, I wished I was able to compact this accumulation 
    for l in tup: 
     events += [(t, value, i) for (t, value) in l] 
     i += 1 
    events.sort(key=lambda x: x[0]) 
    result = dict() 
    time = [0 for i in tup] 
    for t, value, index in events: 
     time[index] = value 
     result[t] = sum(time) 
    return sorted(result.items()) 

Testato con il compito originale,

L1 = [[0, 50], [7.75, 120], [10.25, 70], [17, 100], [20, 60]] 
L2 = [[0, 80], [8, 120], [10, 85], [10.25, 80]] 
print merge([L1, L2]) 

l'uscita è i valori richiesti, come una lista di tuple:

[(0, 130), (7.75, 200), (8, 240), (10, 205), (10.25, 150), (17, 180), (20, 140)]