Sam Steingold <···@goems.com> writes:
> (defun foo=* (&rest foos) (apply #'= (map-into foos #'bar foos)))
Alternative come to mind:
(defun foo=* (&rest foos)
(map-into foos #'bar foos)
(every #'= foos (cdr foos)))
(defun foo=* (&rest foos)
(loop for first-bar = (bar (car foos)) then second-bar
and second-foo in (cdr foos)
for second-bar = (bar second-foo)
always (= first-bar second-bar)))
I'll try to explain why I think this might work out better.
> 1. since I am not modifying the top-level structure of `foos', I assume
> this is legal (OTOH, what if `foo=*' is itself applied? darn...)
I believe &rest is required to cons up a new list. You ought to be safe.
> 2. I tried this in several implementations and in all of them `foo=*'
> consed quite a bit. why?
My guess is that there are two forms of #'=, one optimized for two
arguments (the most common case) and the other implemented using &rest. In
the former case, no consing would be required, while in the second Lisp
will have to cons up a list for the corresponding &rest, allocating
additional memory. This is, of course, speculation on my part, and most
likely highly implementation dependent.
If you compiled your code (which I assume you did), there is also the
possibility of a compiler macro jumping in to do some optimization on =.
> 3. I timed
> (and (foo= foo1 foo1) (foo= foo1 foo2))
> versus
> (foo=* foo1 foo1 foo2)
> and the first one was about twice as fast as the second one. why?
> [obviously this will depend on the nature of `bar', let's assume it's
> just an accessor.]
Did you compare (and (foo=* foo1 foo1) (foo=* foo1 foo2))? You ought to
find in-between performance if my assumptions are correct.
Getting back to my alternative implementations, they are based on my
assumptions. The first uses #'= with two arguments, so it ought to show
some improvement over #'= with multiple arguments. The second form lends
itself to optimization through compiler macros, etc, so I'd imagine it
would be somewhat faster still. In both forms (and in your version of
foo=*), you can (or have the opportunity to) parameterize the comparison
operator too.
Sunil
* Sunil Mishra wrote:
> Sam Steingold <···@goems.com> writes:
>> (defun foo=* (&rest foos) (apply #'= (map-into foos #'bar foos)))
> Alternative come to mind:
> (defun foo=* (&rest foos)
> (map-into foos #'bar foos)
> (every #'= foos (cdr foos)))
> (defun foo=* (&rest foos)
> (loop for first-bar = (bar (car foos)) then second-bar
> and second-foo in (cdr foos)
> for second-bar = (bar second-foo)
> always (= first-bar second-bar)))
For this one, if you declare FOOS to be DYNAMIC-EXTENT you may save a
lot of consing-of-rest-lists.
This is what I came up with. I don't know which is better (this or
the loop one). This one certainly has more bugs I think!
(defun better-foo=* (&rest foos)
(declare (dynamic-extent foos))
;; this will do bad things if FOOS is NIL (and I suppose some implementation
;; of REDUCE could actually check that my fn has the wrong signature).
(if (reduce #'(lambda (x y)
(if (= x y) y nil))
foos
:key #'bar)
t nil))
--tim
Tim Bradshaw <···@aiai.ed.ac.uk> writes:
> For this one, if you declare FOOS to be DYNAMIC-EXTENT you may save a
> lot of consing-of-rest-lists.
Thanks for pointing that out :-)
> This is what I came up with. I don't know which is better (this or
> the loop one). This one certainly has more bugs I think!
>
> (defun better-foo=* (&rest foos)
> (declare (dynamic-extent foos))
> ;; this will do bad things if FOOS is NIL (and I suppose some implementation
> ;; of REDUCE could actually check that my fn has the wrong signature).
> (if (reduce #'(lambda (x y)
> (if (= x y) y nil))
> foos
> :key #'bar)
> t nil))
>
>
> --tim
I considered (and rejected) a reduce version, because reduce is going to go
through the entire list. Unnecessary if the first two turn out to be not
equal.
Sunil
* Sunil Mishra wrote:
> I considered (and rejected) a reduce version, because reduce is going to go
> through the entire list. Unnecessary if the first two turn out to be not
> equal.
My version was also just wrong in an embarrassing way!
This works (but I prefer your loop one):
(defun better-foo=* (&rest foos)
(declare (dynamic-extent foos))
(if (reduce #'(lambda (x y)
(if (= x y)
y
(return-from better-foo=* nil)))
foos
:key #'car)
t nil))
--tim
Sunil Mishra <·······@hustle.cc.gatech.edu> writes:
> Sam Steingold <···@goems.com> writes:
>
> > (defun foo=* (&rest foos) (apply #'= (map-into foos #'bar foos)))
>
> Alternative come to mind:
>
> (defun foo=* (&rest foos)
> (map-into foos #'bar foos)
> (every #'= foos (cdr foos)))
>
> (defun foo=* (&rest foos)
> (loop for first-bar = (bar (car foos)) then second-bar
> and second-foo in (cdr foos)
> for second-bar = (bar second-foo)
> always (= first-bar second-bar)))
>
I like the second alternative for the reasons below. Here's a
variant:
;; Untested
(defun foo=* (first &rest rest)
(let ((test-value (bar first)))
(every #'(lambda (x) (= test-value (bar x))) rest)))
First, this one doesn't need to go to the end of the list if there's a
mismatch, as the mapping versions do. Second, it doesn't bother to
carry along neighboring values for comparison; testing against the
first one is fine for '=. Third, for consistency with '=, requiring
at least one argument is a reasonable thing to do.
Rob St. Amant
·······@ncsu.edu writes:
> Sunil Mishra <·······@hustle.cc.gatech.edu> writes:
[Others deleted]
> > (defun foo=* (&rest foos)
> > (loop for first-bar = (bar (car foos)) then second-bar
> > and second-foo in (cdr foos)
> > for second-bar = (bar second-foo)
> > always (= first-bar second-bar)))
> >
>
> I like the second alternative for the reasons below. Here's a
> variant:
>
> ;; Untested
> (defun foo=* (first &rest rest)
> (let ((test-value (bar first)))
> (every #'(lambda (x) (= test-value (bar x))) rest)))
>
> First, this one doesn't need to go to the end of the list if there's a
> mismatch, as the mapping versions do. Second, it doesn't bother to
> carry along neighboring values for comparison; testing against the
> first one is fine for '=. Third, for consistency with '=, requiring
> at least one argument is a reasonable thing to do.
>
> Rob St. Amant
Good point! Especially if bar turns out to be an expensive operation. About
the only advantage I can claim with the neighbor-testing versions is that
you can blindly replace = with > and expect it to work right. Negation,
i.e. replacing = with /=, will of course require more of a rewrite. But
then extending your version to do pairwise testing would be pretty easy
too, but it would start looking *a lot* like the loop version.
Sunil
This is a tangent to the previous thread, and not a specific-to-lisp
question, I just want to check my intuition!
I want to consider functions that test a set of objects for
inequality:
not-equal things -> T if none of things are equal to any
other.
Am I right in thinking that if there is no order on the things, then
the best approach is quadratic (basically take the first thing, check
it is not equal to any of the rest, and then recurse on the tail)?
If there *is* an order then the best approach is to sort the things
and then do a nearest-neighbour comparison. In fact since a sort
routine must do that anyway, you can use a non-local return from the
sort comparison function to avoid the second step. So the worst-case
complexity should be the same as sort which is nlogn. (Is that right?
anyway, better than n^2.).
Is that right? Is there an even cleverer way? What about hashing all
the objects somehow and checking for collisions, should be linear, but
somehow sounds implausible?
--tim
In article <··················@todday.aiai.ed.ac.uk>,
Tim Bradshaw <···@aiai.ed.ac.uk> wrote:
>Is that right? Is there an even cleverer way? What about hashing all
>the objects somehow and checking for collisions, should be linear, but
>somehow sounds implausible?
That's how I would do it. That's also how I often implement a routine that
deletes duplicates.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
Tim Bradshaw <···@aiai.ed.ac.uk> writes:
> This is a tangent to the previous thread, and not a specific-to-lisp
> question, I just want to check my intuition!
>
> I want to consider functions that test a set of objects for
> inequality:
>
> not-equal things -> T if none of things are equal to any
> other.
>
> Am I right in thinking that if there is no order on the things, then
> the best approach is quadratic (basically take the first thing, check
> it is not equal to any of the rest, and then recurse on the tail)?
>
> If there *is* an order then the best approach is to sort the things
> and then do a nearest-neighbour comparison. In fact since a sort
> routine must do that anyway, you can use a non-local return from the
> sort comparison function to avoid the second step. So the worst-case
> complexity should be the same as sort which is nlogn. (Is that right?
> anyway, better than n^2.).
>
> Is that right? Is there an even cleverer way? What about hashing all
> the objects somehow and checking for collisions, should be linear, but
> somehow sounds implausible?
>
Hashing will give you expected O(n) time (due to the expected O(1)
time for the find operation). Sorting will give you the worst case O(n lg(n))
time or the O(n) time if you can do a non-comparison based sort.
Hashing is usually "good enough" and, on top of that it works for sets
where you can define equality but not an ordering relationship.
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - (0)6 - 68 10 03 16, fax. +39 - (0)6 - 68 80 79 26
http://www.parades.rm.cnr.it