Algorithm: Practical Set Reconciliation

《Practical Set Reconciliation》
Yaron Minsky Cornell University https://blog.janestreet.com/author/yminsky/
Ari Trachtenberg Boston University

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.456.7200&rep=rep1&type=pdf

def set_reconcile(src_seq, dst_seq):
    "Return required operations to mutate src_seq into dst_seq"
    src_set= set(src_seq) # no-op if already of type set
    dst_set= set(dst_seq) # ditto

    for item in src_set - dst_set:
        yield 'delete', item

    for item in dst_set - src_set:
        yield 'create', item

for i in set_reconcile([1,2,3,4], [2,3,4,5]):
    print i

$ python set_reconcile.py 
('delete', 1)
('create', 5)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.