Updating an ordered list of dicts from a new list of dicts (priority merge)
<p>I'm currently faced with having to semi-regularly update (synchronize) a large-ish list of dicts from a canonical changing source while maintaining my own updates to it. A non-standard merge, for which the simplest description is probably:-</p>

<ul>
<li><code>A</code> is my own list of dicts (updated by my program to include cached values as additional keys.</li>
<li><code>b</code> is some regularly sent information from a source (A was originally identical to b). It contains a few keys, but not the cached values I've added to A.</li>
<li><code>keys = ['key1', 'key2']</code> is a list of keys which both A and b have (A has more keys than that.</li>
<li><code>mkey = 'mtime'</code> is a special key which both A and b have which indicates that I should invalidate the cached values of A.</li>
</ul>

<p>Basically, if a dict in <code>A</code> matches a dict in <code>b</code>, I should keep the dict in A unless <code>b['mtime'] &gt; A['mtime']</code>. If a dict appears in <code>A</code> but not in <code>b</code> I get rid of it, while if it appears in <code>b</code> but not in <code>A</code> I add it to <code>A</code>.</p>

<p>My holy grail objective is to not lose any cached key-value pairs in <code>A</code> at all, but I'm having trouble achieving that. My current solution looks something like this:-</p>

<pre><code>def priority_merge(A, b, keys, mkey):
    retval = []
    b_index = 0
    for elemA in A:
        if b_index &gt;= 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] &gt;= 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 &gt;= 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] &gt;= elembplus[mkey]:
                    retval.append(elemA)
                else:
                    retval.append(elembplus)
                b_index = b_index + 2
    if b_index &lt;= len(b):
        retval.extend(b[b_index:])
    return retval
</code></pre>

<p>This works fine as long as I don't get more than one additions and/or deletions (<code>b</code> relative to <code>A</code>) in a row. So if <code>A</code> contains 1, 2, 3, 5 and <code>b</code> contains 1, 2, 3, 4, 5 it's fine, but if <code>A</code> contains 1, 2, 5 and <code>b</code> contains 1, 2, 3, 4, 5 this breaks down.</p>

<p>I could do a check till len(b) under the else case commented as <code># No match, check forward by one</code>, or first iterate through both <code>A</code> and <code>b</code> to map matching elements, then iterate through again based on that map to create retval. This seems error-prone though (I'm sure its do-able logic wise, but I'm also fairly sure code I write for it would be buggy). Please recommend a suitable algorithm to tackle this problem, whether it be my two ideas or something else.</p>

<p>As I told hash method could help you to ensure comparison, based only on <code>keys</code> list you will able to find the intersection element (element to merged) and difference element. </p>

<pre><code>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'] &gt; a['mtime']:
            A.remove(a)
</code></pre>

<p><a href="https://gist.github.com/anonymous/fb9ede72b501788c759c80c77bbb5d02" rel="nofollow">here the complete snippet</a> </p>

python algorithm merge