Hi all,
I'm writing an operator ordering heuristic, using the
most-constraining-variable principle. For this, I
should count in how many constraits a given variable is
involved with a list of unassigned variables.
So, I wrote a function count-constraints, that is given
a val and a list (it also uses the list of constraints,
*rows* which is global), and returns the number.
The idea: *rows* is a list of lists, each one a constraint.
If both _val_ and one (or more, doesn't matter at the moment)
of the values in _lst_ appear together in a constraint,
add one.
Below is my implementation... it's quite, ahem, "draconian",
though the idea is pretty clear.
Go over each constraint (with mapcar on *rows*), return
1 if both val and one of lst is found in the constraint.
In the end, sum the values.
(defun count-constraints (val lst)
(apply #'+
(mapcar #'(lambda (x)
(if (and (find val x) (some #'(lambda (y) (find y x)) lst))
1
0)
) *rows*)))
I'd love to hear suggestions for improvement, and general
comments. It seems like a very "lispy" way of doing things :-)
and I'm sure you'll be able to point out some fine points
and helpful tips.
Thanks in advance
--
Email: ________ at yahoo dot com
(the username is spur4444)
Website: http://www.geocities.com/spur4444/
Eli Bendersky <··@the.signature> writes:
> Go over each constraint (with mapcar on *rows*), return
> 1 if both val and one of lst is found in the constraint.
> In the end, sum the values.
>
> (defun count-constraints (val lst)
> (apply #'+
> (mapcar #'(lambda (x)
> (if (and (find val x) (some #'(lambda (y) (find y x)) lst))
> 1
> 0)
> ) *rows*)))
>
> I'd love to hear suggestions for improvement, and general
> comments. It seems like a very "lispy" way of doing things :-)
> and I'm sure you'll be able to point out some fine points
> and helpful tips.
First, be careful with (apply #'+ ...) when ... might be arbitrarily
large. You might run into problems with CALL-ARGUMENTS-LIMIT which
might be as small as 50. (reduce #'+ ...) is a better alternative.
Then, there are a lot of methods that would avoid consing an
unnecessary temporary list (of 0s and 1s) in the first place. You
might want to use COUNT-IF, for instance, or (loop for list in *rows*
count (and ...)) or some such.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
Nils Goesche <······@cartan.de> writes:
<snip>
> First, be careful with (apply #'+ ...) when ... might be arbitrarily
> large. You might run into problems with CALL-ARGUMENTS-LIMIT which
> might be as small as 50. (reduce #'+ ...) is a better alternative.
>
> Then, there are a lot of methods that would avoid consing an
> unnecessary temporary list (of 0s and 1s) in the first place. You
> might want to use COUNT-IF, for instance, or (loop for list in *rows*
> count (and ...)) or some such.
Thanks again for your help, Nils.
count-if works for me:
(defun count-constraints-involvement (val lst)
"Counts in how many constraints on values of lst, val is involved"
(count-if #'(lambda (x)
(if (and (find val x) (some #'(lambda (y) (find y x)) lst))
t
nil)
) *rows*))
The function doesn't look much less scary, but avoiding the temporary
list is definitely good.
And moreover, your advice led me to apply the function position-if
in another problem (how ? well, they are on the same page in Norvig's
book :-) ).
Thanks
--
Email: ________ at yahoo dot com
(the username is spur4444)
Website: http://www.geocities.com/spur4444/
Eli Bendersky <··@the.signature> writes:
> count-if works for me:
>
> (defun count-constraints-involvement (val lst)
> "Counts in how many constraints on values of lst, val is involved"
> (count-if #'(lambda (x)
> (if (and (find val x) (some #'(lambda (y) (find y x)) lst))
> t
> nil)
> ) *rows*))
>
> The function doesn't look much less scary, but avoiding the
> temporary list is definitely good.
You might simplify it a bit further by
(defun count-constraints-involvement (val list)
"Counts in how many constraints on values of list, val is involved"
(count-if (lambda (x)
(and (find val x)
(some (lambda (y) (find y x)) list)))
*rows*))
This is not Scheme: You can call a list a list, and need not be afraid
of using arbitrary values as (generalized) booleans. (Whether you
write lambda expressions #'(lambda ...) or use the macro form
(lambda ...) is purely personal preference).
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
In article <··············@cartan.de>, Nils Goesche <······@cartan.de> wrote:
> Eli Bendersky <··@the.signature> writes:
>
> > count-if works for me:
> >
> > (defun count-constraints-involvement (val lst)
> > "Counts in how many constraints on values of lst, val is involved"
> > (count-if #'(lambda (x)
> > (if (and (find val x) (some #'(lambda (y) (find y x)) lst))
> > t
> > nil)
> > ) *rows*))
> >
> > The function doesn't look much less scary, but avoiding the
> > temporary list is definitely good.
>
> You might simplify it a bit further by
>
> (defun count-constraints-involvement (val list)
> "Counts in how many constraints on values of list, val is involved"
> (count-if (lambda (x)
> (and (find val x)
> (some (lambda (y) (find y x)) list)))
> *rows*))
>
> This is not Scheme:
Which means you can use LOOP:
(defun count-constraints-involvement (val list)
(loop for row in *rows*
when (and (find val row) (some (lambda (y) (find y row)) list)))
sum 1))
E.
···@jpl.nasa.gov (Erann Gat) writes:
> Which means you can use LOOP:
>
> (defun count-constraints-involvement (val list)
> (loop for row in *rows*
> when (and (find val row) (some (lambda (y) (find y row)) list)))
> sum 1))
Or even:
(loop for row in *rows*
count (and (find val row)
(some (lambda (y) (find y row)) list)))
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'