Aktualisieren einer geordneten Liste von Dicts aus einer neuen Liste von Dicts (Priorität Merge)

Question

Ich bin derzeit konfrontiert mit semi-regelmäßig zu aktualisieren (synchronisieren) eine große Liste von Diktaten aus einer kanonischen wechselnden Quelle, während meine eigenen beibehalten Aktualisierungen dazu. Eine Nicht-Standard-Zusammenführung, für die die einfachste Beschreibung wahrscheinlich ist: -

• A ist meine eigene Liste des dicts (durch mein Programm aktualisiert, um im Cache gespeicherten Werte als zusätzliche Tasten umfassen
• b einige Informationen regelmäßig gesendet wird. von einer Quelle (A war ursprünglich identisch mit b) Es enthält einige Schlüssel, aber nicht die zwischengespeicherten Werte, die ich zu A hinzugefügt habe
• keys = ['key1', 'key2'] ist eine Liste von Schlüsseln, die sowohl A als auch b haben (A hat mehr Schlüssel als das.
• mkey = 'mtime' ist eine spezielle Taste, die beide A und b haben, die angibt, dass ich sollte entkräften die im Cache gespeicherten Werte von A.

Grundsätzlich, wenn ein dict in A ein dict in b passt, sollte ich die dict in A, es sei denn b['mtime'] > A['mtime'] halten. Wenn ein Diktat in A aber nicht in b erscheint, werde ich es los, während wenn es in b aber nicht in A erscheint, füge ich es zu A hinzu.

Meine heilige Gral Ziel ist es, keine zwischengespeicherten Schlüssel-Wert-Paare in A überhaupt zu verlieren, aber ich habe Schwierigkeiten, das zu erreichen. Meine aktuelle Lösung sieht ungefähr wie folgt aus: -

def priority_merge(A, b, keys, mkey): 
    retval = [] 
    b_index = 0 
    for elemA in A: 
     if b_index >= len(b): 
      break # No more items in b 
     elemb = b[b_index] 
     minA = { k: elemA[k] for k in keys } 
     minb = { k: elemb[k] for k in keys } 
     if minA == minb: # Found a match 
      if elemA[mkey] >= elemb[mkey]: 
       retval.append(elemA) 
      else: # Check mkey to see if take b instead 
       retval.append(elemb) 
      b_index = b_index + 1 
     else: # No match, check forward by one 
      if b_index+1 >= len(b): 
       continue 
      elembplus = b[b_index+1] 
      minb = { k: elembplus[k] for k in keys} 
      if minA == minb: 
       retval.append(elemb) # This is a new element 
       if elemA[mkey] >= elembplus[mkey]: 
        retval.append(elemA) 
       else: 
        retval.append(elembplus) 
       b_index = b_index + 2 
    if b_index <= len(b): 
     retval.extend(b[b_index:]) 
    return retval 

Dies funktioniert gut, solange ich nicht mehr als ein Ergänzungen erhalte und/oder Deletionen (b bezogen auf A) in einer Reihe. Also wenn A enthält 1, 2, 3, 5 und b enthält 1, 2, 3, 4, 5 ist es in Ordnung, aber wenn A enthält 1, 2, 5 und b enthält 1, 2, 3, 4, 5 dies zusammenbricht .

Ich konnte einen Scheck bis len (b) unter dem sonsten Fall tun, wie # No match, check forward by one kommentiert oder erste Iterierte sowohl durch A und b passende Elemente auf der Karte, dann wieder durch auf dieser Karte Retval erstellen iterieren basierte. Dies scheint jedoch fehleranfällig zu sein (ich bin mir sicher, dass es logisch machbar ist, aber ich bin mir auch ziemlich sicher, dass Code, den ich dafür schreibe, fehlerhaft wäre). Bitte empfehle einen geeigneten Algorithmus, um dieses Problem anzugehen, sei es meine zwei Ideen oder etwas anderes.

Answer 1

Wie ich sagte Hash-Methode konnte Ihnen helfen, einen Vergleich zu gewährleisten, basierend nur auf keys Liste Sie in der Lage, das Kreuzungselement (Element zu fusionieren) und Differenzelement zu finden.

class HashedDictKey(dict): 

    def __init__(self, keys_, **kwargs): 
     super().__init__(**kwargs) 
     self.keys_ = keys_ 

    def __hash__(self): 
     return hash(tuple(sorted((k, self.get(k)) for k in self.keys_))) 

    def __eq__(self, other): 
     return hash(self) == hash(other) 

def merge(A, B): 

    to_be_added = [] 
    to_be_del = [] 
    to_be_updated = [] 

    def get(obj, it): 
     for i in it: 
      if obj == i: 
       return i 
     raise ValueError("No %s value" % obj) 

    for a, b in zip_longest(A, B): 
     if a in B: 
      to_be_updated.append(a) 
     if a not in B: 
      to_be_del.append(a) 
     if b not in A: 
      to_be_added.append(b) 

    for i in to_be_del: 
     A.remove(i) 

    for j in to_be_added: 
     A.append(j) 

    for i in to_be_updated: 
     a = get(i, A) 
     b = get(i, B) 
     if b['mtime'] > a['mtime']: 
      A.remove(a) 

here the complete snippet