Welcome, guest | Sign In | My Account | Store | Cart

If you need to synchronize two lists here's a simple pattern.

Python, 28 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def prune(L, unique_items):
    """Remove all items in the 'unique_items' list from list L"""
    map(L.remove, unique_items)

def graft(L, unique_items):
    """Add all items in the list 'unique_items' from list L"""
    L.extend(unique_items)

def unique(L1, L2):
    """Return a list containing all items in 'L1' that are not in 'L2'"""
    return [item for item in L1 if item not in L2]

# Sample code demonstratiing use
if __name__ == "__main__":

    # We start with two lists, and we want list1 to
    # be synchronized with list2
    list1 = ["a", "b", "c", "e", "f", "d"]
    list2 = ["a", "b", "f", "g"]

    # Prune extra items out of list1
    prune(list1, unique(list1, list2))

    # Graft any extra items from list2 into list1
    graft(list1, unique(list2, list1))

    print "list1 =", list1
    print "list2 =", list2

These 3 simple functions can be used to synchronize two lists when you can't use the copy module, for example in cases where you don't want to change list items already in both lists.

One example of where these functions are useful is when you have two filesystem directory hierarchies in a tree of lists and you want to synchronize one directory up with the other.

The functions shown here can be coded more compactly inline, but I'm showing them as functions both for clarity and because the pruning and grafting operation will usually need some additional code.

This pattern will work with dictionaries as well by passing a list of the dictionary keys to the unique() function, and writing dictionary aware prune() and graft() functions.

1 comment

Raymond Hettinger 19 years, 9 months ago  # | flag

Faster Implementation using a Dictionary. The above code for unique() has quadratic runtime (slow for long lists) because 'item not in L2' uses a sequential search over list L2.

To achieve linear runtime (fast for long lists), convert L2 to a dictionary so that sequential searching is replaced by fast hashing:

def unique(L1, L2):
    """Return a list containing all items in 'L1' that are not in 'L2'"""
    L2 = dict([(k,None) for k in L2])
    return [item for item in L1 if item not in L2]
Created by Van Gale on Mon, 15 Oct 2001 (PSF)
Python recipes (4591)
Van Gale's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks