timestamps और कतार के साथ tuples की दो सूचियां मर्ज लंबाई

Question

समस्या: मैं दो सूचियों जो tuples (टाइम स्टैंप और एक कतार-लंबाई के प्रत्येक मिलकर) जो मर्ज करने की आवश्यकता शामिल है:

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) कि रिटर्न की जरूरत है:

[[ 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 

[ध्यान दें: मैं की जरूरत नहीं है 60+80 - यह केवल संकेत मिलता है जो मूल्यों फिर से जोड़ रहे हैं है

• (अलग टाइम स्टाम्प्स के मर्ज किए गए सूची में से सबसे छोटा मान V पॉपिंग setwise संघ: 60+80 = 140 की sult मैं क्या जरूरत है]

  क्या मैं ऊपर उत्पादन से निकालने कि मैं बार-बार कर रहा हूँ है timestamps)।

• V से कम या बराबर टाइमस्टैम्प की गैर-V सूची से कतार-लंबाई जोड़ना।
• ... V तक समाप्त हो गया है।

मेरे समस्या: मैं बहुत यकीन है कि heapq इसे हल कर सकते हैं, लेकिन कैसे समाधान heapq मॉड्यूल का उपयोग कर की संरचना करने के लिए चारों ओर मेरे सिर नहीं मिल सकता हूँ।

अधिक प्रक्रिया के पर्यटन विवरण:

1. पहले चरण में - 0.00 पर और 7.75 तक यौगिक कतार की लंबाई 50+80 है - से L1[0][0] == L2[0][0]
2. लिया मैं मान L1[0][1]+L2[0][1] = 50+80 जोड़ सकते हैं। अब मैंने L1[0][:] और L2[0][:]
3. दूसरे चरण में - 7.75 पर - एल 2 की कतार बढ़ रही नहीं है, लेकिन एल 1 की कतार में है: L1[1][0] = 120। इसलिए 120+80 प्राप्त करने के लिए L2[0][1] के साथ L1[1][1] जोड़ने के लिए यौगिक कतार लंबाई प्राप्त करने की आवश्यकता है।
4. मैंने अब पहले दर्ज किए गए पहले मान का बड़ा उपयोग किया है और जब तक अंतराल समाप्त हो गया है (23.99 के बाद) अगले चरणों के लिए ऐसा करना चाहिए। "समय" के सेट में अगला सबसे बड़ा मान L2[1][0] है जो 8.00 है।
5. जैसा कि 8.00 775 से बड़ा है, मुझे इन मानों को मर्ज करने की आवश्यकता है ताकि 8.00 पर कतार की लंबाई 120 + 120 है जो एल 1 के सबसे बड़े मूल्य पर आधारित है जो 8.00 से कम है - जो 7.75 है। इस प्रकार मैं एल 1 1 और एल 2 1 जोड़ता हूं।
6. अगले चरण में सबसे बड़ा अप्रयुक्त मूल्य एल 2 से 10.00 है। L2 से कतार लंबाई L1 के साथ सबसे बड़ी मान के साथ विलय करने की आवश्यकता है, जो 10.00 से कम या उसके बराबर है ...
7. और इसलिए यह जारी है ...जिस क्रम में वे होती हैं, और, पिछले आपरेशन (last_time) के समय स्टाम्प रखने में घटनाओं से अधिक

Answer 1

दोहराएं तो अगर अगली घटना एक ही समय टिकट है, लेकिन दो अन्य पंक्ति से आता है कि परिवर्तन 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

आप भी इस तरह कर सकता है:

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) 

उत्पादन:

[[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

galath's solution से प्रेरित होकर, मैं से अधिक के लिए एक समाधान खोजने के लिए करने की कोशिश की दो इनपुट:

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()) 

मूल कार्य के साथ परीक्षण किया गया,

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]) 

उत्पादन होता है tuples की एक सूची के रूप में आवश्यक मान,:

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