Mailing List Archive: Efficient List Subtraction

Efficient List Subtraction

Apr 23, 1999, 3:08 PM

Post #1 of 6 (993 views)

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]

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.

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].

If anyone out there has a suggestion (or two) I would very much appreciate it.

Cheers! -Scott

-------------------------------------------------------------------
Scott Kelley Phone: 303-492-1474
Dept. MCD Biology Fax: 303-492-7744
Campus Box 347 E-mail: Scott.Kelley@Colorado.edu
University of Colorado
Boulder, CO 80309-0347

Efficient List Subtraction [ In reply to ]

jfarr at real

Apr 23, 1999, 3:29 PM

Post #2 of 6 (996 views)

Permalink

I have also longed for built in support for the union and intersection of
two sequences.

Perhaps:
list.union(list2)
and
list.intersection(list2)

??

insert-clever-witty-long-hyphenated-phrase-ly y'rs
--jfarr

Efficient List Subtraction [ In reply to ]

sdm7g at Virginia

Apr 23, 1999, 6:35 PM

Post #3 of 6 (985 views)

Permalink

On Fri, 23 Apr 1999, KELLEY SCOTT T wrote:

>
> 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]
>
> 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.
>
> 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].
>

Well -- it's probably not the most efficient, but the simplest
list intersection is probably:

>>> a = [1,4,5,100]
>>> b = [4,5]
>>> filter( lambda x: x in a, b )
[4, 5]
>>> filter( lambda x: x in b, a ) # order doesn't matter
[4, 5] # for intersection

# but it does for set-difference
>>> filter( lambda x: x not in a, b ) # b - a
[]
>>> filter( lambda x: x not in b, a ) # a - b
[1, 100]

I don't think union or XOR can be done as concisely.

---| Steven D. Majewski (804-982-0831) <sdm7g@Virginia.EDU> |---
---| Department of Molecular Physiology and Biological Physics |---
---| University of Virginia Health Sciences Center |---
---| P.O. Box 10011 Charlottesville, VA 22906-0011 |---

Caldera Open Linux: "Powerful and easy to use!" -- Microsoft(*)
(*) <http://www.pathfinder.com/fortune/1999/03/01/mic.html>

Efficient List Subtraction [ In reply to ]

gmcm at hypernet

Apr 23, 1999, 8:26 PM

Post #4 of 6 (996 views)

Permalink

Jonothan Farr wrote:

> I have also longed for built in support for the union and
> intersection of two sequences.
>
> Perhaps:
> list.union(list2)
> and
> list.intersection(list2)

While not exactly what you're looking for, I suggest going to
chordate.com and looking for kjbuckets. It's got sets and graphs; you
can do intersections and closures...

- Gordon

Efficient List Subtraction [ In reply to ]

mlh at idt

Apr 25, 1999, 12:35 PM

Post #5 of 6 (989 views)

Permalink

KELLEY SCOTT T <Scott.Kelley@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@laiv.org>

Efficient List Subtraction [ In reply to ]

mlh at idt

Apr 25, 1999, 12:45 PM

Post #6 of 6 (993 views)

Permalink

"Steven D. Majewski" <sdm7g@Virginia.EDU> writes:

> On Fri, 23 Apr 1999, KELLEY SCOTT T wrote:
>
> >
> > 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,
[...]
>
> Well -- it's probably not the most efficient, but the simplest
> list intersection is probably:

OK... Posted an efficient version earlier -- now for the simple ones...

(Assuming that there are no duplicates in the original lists...)

>
> >>> a = [1,4,5,100]
> >>> b = [4,5]
> >>> filter( lambda x: x in a, b )
> [4, 5]
> >>> filter( lambda x: x in b, a ) # order doesn't matter
> [4, 5] # for intersection
>
> # but it does for set-difference
> >>> filter( lambda x: x not in a, b ) # b - a
> []
> >>> filter( lambda x: x not in b, a ) # a - b
> [1, 100]
>
> I don't think union or XOR can be done as concisely.

Let's do union first:

>>> a + filter(lambda x: x not in a, b)

Then XOR:

>>> filter(lambda x: x not in b, a) + filter(lambda x: x not in a, b)

*If* we had an xor operator, we might say:

>>> filter(lambda x: x in a xor x in b, a+b)

Even though we don't, we might settle for:

>>> filter(lambda x: (x in a and not (x in b)) or \
(x in b and not (x in a)), a+b)

Or, actually:

>>> filter(lambda x: not (x in a and x in b), a+b)

Not too bad, is it?

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