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.
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."
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
···@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
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.
"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.
* 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
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