Prev: [CfP] DLS'10
Next: Tracing recursive functions in slime REPL (Allegro CL)
From: Andrea Taverna on 19 Apr 2010 12:18
Hi,

I need to implement an argmax-like function that works this way:
(i*,j*) = argmax{f(i,j) | i,j in C}, i.e. I have to find the optimal
couple (i*,j*) for function f where i,j are variables varying on a
finite discrete set C=0..n-1.

Using iterate I came up with the following solution
(iter (for i from 0 below n)
(for result =
(iter (for j from 0 below n)
(for c = (list i j))
(finding c maximizing (apply #'f c) into c*)
(finally (return c*))))
(finally (return result)))

But I don't like it much, I'd prefer not to have to express how the
couple (i,j) is implemented, I'd like to write something like this:
(multiple-value-bind (i* j*)
(iter (for i from 0 below n)
(iter (for j from 0 below n)
(finding (i . j) maximizing (f i j) into (i^ . j^))
(finally (return (values i^ j^)))))
...)

Apart from "elegance", is there something I should look out
performance-wise?

TIA

Andrea
From: Andrea Taverna on 19 Apr 2010 12:55
Noticed I missed one piece, it should be

(iter (for i from 0 below n)
   (for result =
       (iter (for j from 0 below n)
         (for c = (list i j))
         (finding c  maximizing (apply #'f c) into c*)
      (finally (return c*))))
(finding result maximizing (apply #'f result) into result*)
   (finally (return result*)))

which adds another evaluation for f
From: Tamas K Papp on 19 Apr 2010 14:29
On Mon, 19 Apr 2010 09:18:13 -0700, Andrea Taverna wrote:

> Hi,
>
> I need to implement an argmax-like function that works this way: (i*,j*)
> = argmax{f(i,j) | i,j in C}, i.e. I have to find the optimal couple
> (i*,j*) for function f where i,j are variables varying on a finite
> discrete set C=0..n-1.
>
> Using iterate I came up with the following solution (iter (for i from 0
> below n)
> (for result =
> (iter (for j from 0 below n)
> (for c = (list i j))
> (finding c maximizing (apply #'f c) into c*)
> (finally (return c*))))
> (finally (return result)))
>
> But I don't like it much, I'd prefer not to have to express how the
> couple (i,j) is implemented, I'd like to write something like this:
> (multiple-value-bind (i* j*)
> (iter (for i from 0 below n)
> (iter (for j from 0 below n)
> (finding (i . j) maximizing (f i j) into (i^ .
j^)) (finally
> (return (values i^ j^)))))
> ...)
>
> Apart from "elegance", is there something I should look out
> performance-wise?

I would be very surprised if the performance difference between the
alternatives was even measurable. Don't worry about it. Use the form
that comes most naturally.

BTW, it seems to me that the inner loop would just return the best
(values i j) for a given i, which would then be ignored. I doubt that
this is the intention. In iterate, you can name your loop levels, and
collect/gather/etc in another (outer level). See the manual.

Best,

Tamas
From: grucidipo on 19 Apr 2010 15:08
On 19 abr, 18:18, Andrea Taverna <a.t...(a)hotmail.it> wrote:
> Hi,
>
> I need to implement an argmax-like function that works this way:
> (i*,j*) = argmax{f(i,j) | i,j in C}, i.e. I have to find the optimal
> couple (i*,j*) for function f where i,j are variables varying on a
> finite discrete set C=0..n-1.
>
> Using iterate I came up with the following solution
> (iter (for i from 0 below n)
>    (for result =
>        (iter (for j from 0 below n)
>          (for c = (list i j))
>          (finding c  maximizing (apply #'f c) into c*)
>       (finally (return c*))))
>    (finally (return result)))
>
> But I don't like it much, I'd prefer not to have to express how the
> couple (i,j) is implemented, I'd like to write something like this:
> (multiple-value-bind (i* j*)
>              (iter  (for i from 0 below n)
>                     (iter (for j from 0 below n)
>                           (finding (i . j)  maximizing (f i j) into (i^ . j^))
>                           (finally (return (values i^ j^)))))
>            ...)
>
> Apart from "elegance", is there something I should look out
> performance-wise?
>
> TIA
>
> Andrea


What about this one?

;; for testing (defun f(x y)(- (* x x) (* x y)))

(defun argmax-like (f n)
(loop with argmax = '(0 0)
with maxf = (funcall f 0 0)
for i below n do
(loop for j below n do
(when (> (funcall f i j) maxf)
(setq argmax (list i j)
maxf (funcall f i j))))
finally (return (list argmax maxf))))

;; example (argmax-like #'f 10) => ((9 0) 81)
From: Rob Warnock on 20 Apr 2010 20:13
Alberto Riva <alb(a)nospam.ufl.edu> wrote:
+---------------
| I would change it to:
|
| (defun argmax-like (f n)
| (loop with argmax = (cons 0 0)
| with maxf = (funcall f 0 0)
| for i below n do
| (loop for j below n do
| (let ((v (funcall f i j)))
| (when (> v maxf)
| (setf (car argmax) i
| (cdr argmax) j
| maxf v))))
| finally (return (list argmax maxf))))
|
| Advantages:
| 1. You use a single cons to store argmax, instead of creating a new list
| every time;
| 2. You avoid repeated evaluations of f.
+---------------

Or even get rid of the ARGMAX cons and the consing of results
and let everything be stack-allocated:

(defun argmax-like (f n)
(loop with max-i = 0
and max-j = 0
and max-f = (funcall f 0 0)
for i below n do
(loop for j below n
for v = (funcall f i j)
when (> v max-f)
do (setf max-i i
max-j j
max-f v))
finally (return (values max-i max-j max-f))))

Or (return (list (list max-i max-j) max-f)) if the original API
was really important...


-Rob

p.s. If the limit N -- or rather, (EXPT N 2) -- is fairly small and
the cost of calling F is very large [or has unwanted side-effects], one
might even want to get rid of the initializing call of (FUNCALL F 0 0),
like so:

(defun argmax-like (f n)
(loop with max-i = 0
and max-j = 0
and max-f = nil
and first-time = t
for i below n do
(loop for j below n
for v = (funcall f i j)
when (or first-time (> v max-f))
do (setf max-i i
max-j j
max-f v
first-time nil))
finally (return (values max-i max-j max-f))))

-----
Rob Warnock <rpw3(a)rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

 |  Next  |  Last
Pages: 1 2
Prev: [CfP] DLS'10
Next: Tracing recursive functions in slime REPL (Allegro CL)