From: mlh at idt.ntnu.no (Magnus L. Hetland)
Date: 25 Apr 1999 21:35:08 +0200
Subject: Efficient List Subtraction
References: <3720EF73.CA7DDEFF@Colorado.edu>
Message-ID: <y0j4sm4o5n7.fsf@vier.idi.ntnu.no>
Content-Length: 1547
X-UID: 1324                                                  

KELLEY SCOTT T <Scott.Kelley at Colorado.edu> writes:

> Does anyone out there have a simple way to compare two lists (some operator perhaps) and
> return
> a list of *differences*?  By differences, I mean the following:  If had two
> lists  like,
> 
> a = [1, 4, 5, 100]
> b = [4, 5]

(Check dejanews for similar reply to several similar functions...)


You can use dictionaries.

def difference(a,b):
    result = {}
    for element in a:
        result[element] = 1
    for element in b:
        if result.has_key(element):
            del result[element]
    return result.keys()
> 
> the difference between a and b (a-b) would be [1, 100]. I suppose you could
> write a couple of for loops to go through each list and compare them, but I
> thought there might be a simple way to do this.

At least hashtables makes it more efficient.

> I'm also interested in a simple way to returning a list of what is identical between the
> two lists.
> In the case of the above lists, a and b, they both contain [4, 5].

Same thing, basically... Just do something like:

def intersection(a,b):
    temp = {}
    result = []
    for elt in a:
        temp[elt] = 1
    for elt in b:
        if temp.has_key(elt):
            result.append(elt)
    return result

> 
> If anyone out there has a suggestion (or two) I would very much appreciate it.
> 
> Cheers! -Scott

--
               > Hi! I'm the signature virus 99!
  Magnus       > Copy me into your signature and join the fun!
  Lie
  Hetland        http://arcadia.laiv.org <arcadia at laiv.org>




