From: Rene de Visser
Subject: Sets of structures
Date: 
Message-ID: <b5p5qj$cr3$1@news1.wdf.sap-ag.de>
I wish to have sets of structures (based on the identity of the structures
rather than their content).
(Or is it more correct to say structure instances?? i.e. sets of the things
you get when you do
(make-test) where test is a structure definition).

I am planning to do this using lists. However to allow for easy comparison
of sets I wish to
keep the structures within each set in a canonical ordering (there is no
natural ordering implicit
in the structures).

i.e. if I have two sets (lists) with structure (instances) S1, S2, S3 I want
them to always appear in the same
order so that I can simply compare the two lists with #'equal two see if the
two sets are the same.

Am I correct in thinking that the only way of doing this is adding a slot to
the structure which contains an
integer that is unique for the particular structure instance?

Somehow this doesn't seem so aesthetic, but I can't think of any other way.

Rene.

From: Matthew Danish
Subject: Re: Sets of structures
Date: 
Message-ID: <20030325044427.I1644@lain.cheme.cmu.edu>
On Tue, Mar 25, 2003 at 10:00:03AM +0100, Rene de Visser wrote:
> i.e. if I have two sets (lists) with structure (instances) S1, S2, S3
> I want them to always appear in the same order so that I can simply
> compare the two lists with #'equal two see if the two sets are the
> same.

I don't know if this helps with other problems, but have you considered
SET-DIFFERENCE?

-- 
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
From: Thomas A. Russ
Subject: Re: Sets of structures
Date: 
Message-ID: <ymid6kfp9zs.fsf@sevak.isi.edu>
Matthew Danish <·······@andrew.cmu.edu> writes:

> 
> On Tue, Mar 25, 2003 at 10:00:03AM +0100, Rene de Visser wrote:
> > i.e. if I have two sets (lists) with structure (instances) S1, S2, S3
> > I want them to always appear in the same order so that I can simply
> > compare the two lists with #'equal two see if the two sets are the
> > same.
> 
> I don't know if this helps with other problems, but have you considered
> SET-DIFFERENCE?

Well, the big difference between EQUAL and SET-DIFFERENCE is that EQUAL
is O(n) and SET-DIFFERENCE is O(n^2) runtime complexity.   If you have
large sets of these structures, then it may be worthwhile to keep the
lists sorted O(n log n).   If the lists are fairly short, then it
probably isn't worth the effort to be clever, and using the set
operators would work well.


-- 
Thomas A. Russ,  USC/Information Sciences Institute          ···@isi.edu    
From: Gabe Garza
Subject: Re: Sets of structures
Date: 
Message-ID: <87r88u6hql.fsf@ix.netcom.com>
···@sevak.isi.edu (Thomas A. Russ) writes:

> Matthew Danish <·······@andrew.cmu.edu> writes:

> > I don't know if this helps with other problems, but have you considered
> > SET-DIFFERENCE?
> 
> Well, the big difference between EQUAL and SET-DIFFERENCE is that EQUAL
> is O(n) and SET-DIFFERENCE is O(n^2) runtime complexity.  

If you ignore differences in key length, and only use EQ, EQL, EQUAL,
or EQUALP as the :TEST argument, you can very easily write a
\Theta(n_1 + n_2) SET-DIFFERENCE:

(defun linear-set-difference (list-1 list-2 &key (test #'eql) key)
  (let* ((list-2-hash (make-hash-table :test test))
         (key (or key #'identity)))
    (dolist (item list-2)
      (setf (gethash (funcall key item) list-2-hash) t))
    (loop for item in list-1
      when (not (gethash (funcall key item) list-2-hash))
      collect item)))

Gabe Garza
From: Kent M Pitman
Subject: Re: Sets of structures
Date: 
Message-ID: <sfw1y0uzy63.fsf@shell01.TheWorld.com>
Gabe Garza <·······@ix.netcom.com> writes:

> ···@sevak.isi.edu (Thomas A. Russ) writes:
> 
> > Matthew Danish <·······@andrew.cmu.edu> writes:
> 
> > > I don't know if this helps with other problems, but have you considered
> > > SET-DIFFERENCE?
> > 
> > Well, the big difference between EQUAL and SET-DIFFERENCE is that EQUAL
> > is O(n) and SET-DIFFERENCE is O(n^2) runtime complexity.  
> 
> If you ignore differences in key length, and only use EQ, EQL, EQUAL,
> or EQUALP as the :TEST argument, you can very easily write a
> \Theta(n_1 + n_2) SET-DIFFERENCE:
> 
> (defun linear-set-difference (list-1 list-2 &key (test #'eql) key)
>   (let* ((list-2-hash (make-hash-table :test test))
>          (key (or key #'identity)))
>     (dolist (item list-2)
>       (setf (gethash (funcall key item) list-2-hash) t))
>     (loop for item in list-1
>       when (not (gethash (funcall key item) list-2-hash))
>       collect item)))

Not that you can't just make a hybrid that does this technique in the
case it can make a hash table of the right kind, and the slower thing
in the other case.
From: Pascal Bourguignon
Subject: Re: Sets of structures
Date: 
Message-ID: <87el4vu71s.fsf@thalassa.informatimago.com>
"Rene de Visser" <··············@hotmail.de> writes:

> I wish to have sets of structures (based on the identity of the
> structures rather than their content).  (Or is it more correct to
> say structure instances?? i.e. sets of the things you get when you
> do (make-test) where test is a structure definition).
> 
> I am planning to do this using lists. However to allow for easy
> comparison of sets I wish to keep the structures within each set in
> a canonical ordering (there is no natural ordering implicit in the
> structures).
> 
> i.e. if I have two sets (lists) with structure (instances) S1, S2,
> S3 I want them to always appear in the same order so that I can
> simply compare the two lists with #'equal two see if the two sets
> are the same.
> 
> Am I correct in thinking that the only way of doing this is adding a
> slot to the structure which contains an integer that is unique for
> the particular structure instance?
> 
> Somehow this doesn't seem so aesthetic, but I can't think of any
> other way.


I first had  the idea to use the hash value  of the structure instance
and  sort on  it.  But sxhash  returns  a fixnum  and  there could  be
collisions even if you computed your own hash value, so this would not
work in all cases.

This is typically a  case where in C I would sort  on the pointer cast
to  unsigned int.  If  you have  a  FFI interface,  perhaps you  could
retrieve the address of the structure and sort on it.


So I  guess that  the cleaner  way is probably  what you  proposed, to
associate  a unique  identifier to  each structure  instance.   If you
don't  like adding  it  inside  the structure,  you  could record  the
association separately, for  example in a hash table  struct -> order.
But they  you'd have  to manage memory,  removing the struct  from the
hash table when they should be released...



-- 
__Pascal_Bourguignon__                   http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
From: Tim Bradshaw
Subject: Re: Sets of structures
Date: 
Message-ID: <ey3u1drk8dt.fsf@cley.com>
* Pascal Bourguignon wrote:
> This is typically a  case where in C I would sort  on the pointer cast
> to  unsigned int.  If  you have  a  FFI interface,  perhaps you  could
> retrieve the address of the structure and sort on it.

However, in the presence of a copying GC it's not likely that the
addresses of objects will remain the same as they get moved around by
the GC.

--tim
From: Marco Antoniotti
Subject: Re: Sets of structures
Date: 
Message-ID: <1akga.119$oj7.12206@typhoon.nyu.edu>
Rene de Visser wrote:

> I wish to have sets of structures (based on the identity of the structures
> rather than their content).
> (Or is it more correct to say structure instances?? i.e. sets of the 
> things
> you get when you do
> (make-test) where test is a structure definition).
>
> I am planning to do this using lists. However to allow for easy comparison
> of sets I wish to
> keep the structures within each set in a canonical ordering (there is no
> natural ordering implicit
> in the structures).


The key question is how you define "canonical ordering" of these 
defstruct instances.

> i.e. if I have two sets (lists) with structure (instances) S1, S2, S3 
> I want
> them to always appear in the same
> order so that I can simply compare the two lists with #'equal two see 
> if the
> two sets are the same.
>
> Am I correct in thinking that the only way of doing this is adding a 
> slot to
> the structure which contains an
> integer that is unique for the particular structure instance?
>
> Somehow this doesn't seem so aesthetic, but I can't think of any other 
> way.

Answer the previous question and you will be half way there.

Cheers

--
Marco Antoniotti