I have some numeric nonsense that rates teams based on who can beat
whom, a winner earns N points based on the losers rank in the prior
ranking. Points are summed, and a new ranking is created. Iterate a
thousand times to get some stability. Since A beating B, B beating C,
and C beating A is common, there will always be some rank shuffling
between I interations and (1+ I) interations.
So I proclaim that teams that shuffled ranks represent tied teams. I
need a list that reflects those ties, e.g.
DOBROW> (next-rankings)
(("TOR" 1) ("KC" 2) ("BOS" 3) ("DET" 4) ("CWS" 5) ("TB" 6) ("TEX" 7)
("SEA" 8) ("MIN" 9) ("NYY" 10) ("CLE" 11) ("LAA" 12) ("LAD" 13)
("BAL" 14) ("OAK" 15) ("SF" 16) ("ARI" 17) ("SD" 18) ("COL" 19)
("CHC" 20) ("MIL" 21) ("STL" 22) ("CIN" 23) ("HOU" 24) ("PHI" 25)
("NYM" 26) ("PIT" 27) ("ATL" 28) ("FLA" 29) ("WSH" 30))
DOBROW> (next-rankings)
(("KC" 1) ("TOR" 2) ("BOS" 3) ("DET" 4) ("TB" 5) ("CWS" 6) ("TEX" 7)
("MIN" 8) ("SEA" 9) ("CLE" 10) ("NYY" 11) ("LAA" 12) ("BAL" 13)
("LAD" 14) ("OAK" 15) ("SF" 16) ("ARI" 17) ("COL" 18) ("SD" 19)
("CHC" 20) ("STL" 21) ("MIL" 22) ("CIN" 23) ("HOU" 24) ("PHI" 25)
("PIT" 26) ("NYM" 27) ("WSH" 28) ("ATL" 29) ("FLA" 30))
should become
((("TOR" 1) ("KC" 1))
("BOS" 3)
("DET" 4)
(("CWS" 5) ("TB" 5))
("TEX" 7)
(("SEA" 8) ("MIN" 8))
(("NYY" 10) ("CLE" 10))
("LAA" 12)
(("LAD" 13) ("BAL" 13))
("OAK" 15)
("SF" 16)
("ARI" 17)
(("SD" 18) ("COL" 18))
("CHC" 20)
(("MIL" 21) ("STL" 21))
("CIN" 23)
("HOU" 24)
("PHI" 25)
(("NYM" 26) ("PIT" 26))
(("ATL" 28) ("FLA" 28) ("WSH" 28)))
Hmm, after writing this all out, I see that walking each list
separately and averaging the rankings will solve it sufficiently.
For future reference, is there a simple way to walk two lists
simultaneously? I can only think of 'aref as a solution, with careful
"pointer" manipulation.
--
"Humans are allergic to change. "We've always done it that way" is not
a good reason to continue to do so. That's why I have a clock on my
office wall that runs backwards. It forces visitors to think.
They hate me for that." - Admiral Hopper.
On Sat, 9 May 2009 21:56:01 +0000 (UTC), <··············@usenet.kitty.sub.org> wrote:
>
>
> Hi!
>
> GP lisper <········@clouddancer.com> wrote:
>>[...]
>
>>For future reference, is there a simple way to walk two lists
>>simultaneously? I can only think of 'aref as a solution, with careful
>>"pointer" manipulation.
>
> IIRC map can do that.
>
> If you want to walk it for a side effect, use
> (map nil
> (lambda (first-list-element second-list-element) body...)
> first-list
> second-list)
>
> If you want to collect the results in a list, use (map 'list ...)
> instead.
Hmm, map walks them at the same position, which will work nicely in my
solution, that's much cleaner. Thanks!
But I didn't phrase that query properly, I was thinking of at a
position in one list, be able to walk back/forth on the other list,
e.g look at the last 3 teams in the next-rankings output. I suppose
map would help that out too, or it's sourcecode would...
--
Humans are allergic to change. "We've always done it that way" is not
a good reason to continue to do so. That's why I have a clock on my
office wall that runs backwards. It forces visitors to think.
They hate me for that. - Admiral Hopper.
GP lisper <········@clouddancer.com> wrote:
+---------------
| For future reference, is there a simple way to walk two lists
| simultaneously? I can only think of 'aref as a solution, with
| careful "pointer" manipulation.
+---------------
Others have dealt with the case of truly *simultaneous* (synchronized)
walking [MAP, LOOP, etc.], but you indicated you wanted something
more like pushing an examination window down each list independently.
ISTM that the general name for this just might be "merge sort" ;-} ;-}
<http://en.wikipedia.org/wiki/Merge_sort>, or at least the merge
phase of it.
I've occasionally had to do things like that, and the result tended
to look something like one of the following three examples [from more
generic to more low-level/bit-fiddly], which all just a LOOP wrapped
around one of the common forms of a finite state machine [with only
one state(!), though more states could easily be added]:
(loop with in1 = input-list-1
and in2 = input-list-2
while (or in1 in2)
;; CHOICE-FUNCTION returns a keyword naming the desired action.
for next-pick = (choice-function (first in1) (first in2)
(second in1) (second in2)
...extend-window-as-needed...)
when (eq next-pick :in1)
collect (pop in1)
when (eq next-pick :in2)
collect (pop in2)
when (eq next-pick :both)
collect (pop in1)
and
collect (pop in2)
when (eq next-pick :drop1)
do (pop in1)
when (eq next-pick :drop2)
do (pop in2)
when (eq next-pick :drop-both)
do (pop in1) (pop in2))
Or you may prefer to do the collection yourself for more Lispy control:
(loop with in1 = input-list-1
and in2 = input-list-2
and result = nil
while (or in1 in2)
do (case (choice-function (first in1) (first in2)
(second in1) (second in2)
...extend-window-as-needed...)
((:in1) (push (pop in1) result))
((:in2) (push (pop in2) result))
((:both) (push (pop in1) result) (push (pop in2) result))
((:drop1) (pop in1))
((:drop2) (pop in2))
((:drop-both) (pop in1) (pop in2)))
finally (return (nreverse result)))
Or even finer-grained spreading of the choice function [note that this
version does *not* implement exactly the same algorithm as the above]:
(loop with in1 = input-list-1
and in2 = input-list-2
and result = nil
while (or in1 in2)
do (cond
((strange-deep-look-test (first in1) (first in2)
(second in1) (second in2))
(push (average (first in1) (second in2)) result)
(push (average (first in2) (second in1)) result)
(pop1 in1)
(pop1 in1)
(pop1 in2)
(pop1 in2))
((definitely-better-p (first in1) (first in2))
(push (pop in1) result)
(pop in2))
((definitely-better-p (first in2) (first in1))
(push (pop in2) result)
(pop in1))
((good-enough-p (first in1))
(push (pop in1) result))
((good-enough-p (first in2))
(push (pop in2) result))
(t ; Neither is even "good enough", so drop both.
(pop in1)
(pop in2)))
finally (return (nreverse result)))
The above styles can all be easily extended to three or more input
lists [or sets, or vectors, whatever], along with more states to
remember history of previous choices/actions, but the choice functions
and actions sections will get messier and messier. As some point it
will become advantageous to define a DSL for the desired processing
which compiles into a giant TAGBODY. ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Sat, 09 May 2009 20:07:58 -0500, <····@rpw3.org> wrote:
>
> I've occasionally had to do things like that, and the result tended
> to look something like one of the following three examples [from more
> generic to more low-level/bit-fiddly], which all just a LOOP wrapped
> around one of the common forms of a finite state machine [with only
> one state(!), though more states could easily be added]:
>
> (loop with in1 = input-list-1
> and in2 = input-list-2
> while (or in1 in2)
> ;; CHOICE-FUNCTION returns a keyword naming the desired action.
> for next-pick = (choice-function (first in1) (first in2)
> (second in1) (second in2)
> ...extend-window-as-needed...)
Ah, yes.
The window merely needs to be large enough to capture all of the
intermediate ranks from when the ranking diverges to when they
converge again (or whatever rule for the problem in consideration).
Then the return value of CHOICE bumps the sublists as desired. Since
this is LOOP, I can fiddle the loop index to jump ahead after a
diverge/converge. A handy solution to tuck away, thanks Rob.
On Sat, 09 May 2009 14:36:00 -0700, GP lisper wrote:
> I have some numeric nonsense that rates teams based on who can beat
> whom, a winner earns N points based on the losers rank in the prior
> ranking. Points are summed, and a new ranking is created. Iterate a
> thousand times to get some stability. Since A beating B, B beating C,
> and C beating A is common, there will always be some rank shuffling
> between I interations and (1+ I) interations.
I don't know if you can change the algorithm (ie if this is for your
own amusement/research, or a task given by someone else), but I can't
resist suggesting it, considering that you got some solutions to the
original question already :-)
I would use simple probabilistic inference.
Eg consider the following model: each team i has a "strength" x_i.
Whenever i and j meet, i beats j by x_i-x_j+epsilon, where epsilon is
some random variable with mean zero. In the first approximation, I
would just make it normal and IID with the same variance for all
observations.
It is very easy to write the likelihood function for this problem, and
I think that even a closed-form characterization is possible (fully
Bayesian of course, of if you are feeling lazy, then maximum
likelihood). Then you can also make predictions, eg the probability
that j beats i is F(x_j-x_i), where F is the distribution function of
epsilon.
Notice that the original algorithm is a special case of this: you just
make epsilon degenerate (zero variance), but then you can't deal with
circularities (A > B > C > A) because those have zero likelihood, so
you introduce ad-hoc rules. No need for that.
HTH,
Tamas
On 9 May 2009 23:41:27 GMT, <······@gmail.com> wrote:
> On Sat, 09 May 2009 14:36:00 -0700, GP lisper wrote:
>
>> I have some numeric nonsense that rates teams based on who can beat
>> whom, a winner earns N points based on the losers rank in the prior
>> ranking. Points are summed, and a new ranking is created. Iterate a
>> thousand times to get some stability. Since A beating B, B beating C,
>> and C beating A is common, there will always be some rank shuffling
>> between I interations and (1+ I) interations.
>
> I don't know if you can change the algorithm (ie if this is for your
> own amusement/research, or a task given by someone else), but I can't
> resist suggesting it, considering that you got some solutions to the
> original question already :-)
No problem. These posts are always my baseball research.
> I would use simple probabilistic inference.
>
> Eg consider the following model: each team i has a "strength" x_i.
> Whenever i and j meet, i beats j by x_i-x_j+epsilon, where epsilon is
> some random variable with mean zero. In the first approximation, I
> would just make it normal and IID with the same variance for all
> observations.
Not all teams play each other.
Not all teams play teams the same number of times.
The winning-margin in a game is not a useful measure, teams will
routinely trade runs for outs late in a game. There are other
reasons why winning-margin is not reflective of the comparable team
strengths, mainly they reflect the brutal grind of 162 games in 180 days.
There needs to be some measure other than prior scoring history to
work an improved model. Historical attempts to select a measure
have rarely risen above the 60% accuracy level for prediction.
> It is very easy to write the likelihood function for this problem, and
> I think that even a closed-form characterization is possible (fully
> Bayesian of course, of if you are feeling lazy, then maximum
> likelihood). Then you can also make predictions, eg the probability
> that j beats i is F(x_j-x_i), where F is the distribution function of
> epsilon.
The technique works nicely for stuff such as NCAA March Madness, and I
have been imspired by reading their code examples. This being
baseball, it's not so simple, but a new approach is always of interest.
I just wrote this code to have an answer for 'My team can beat your
team' with some math behind it. When I ran it against the 2008
season, it just reflected the final won/loss outcome of the various
teams within a baseball division, and the divisions record against
other divisions (so that the divisions were separated and stacked).
That reflected the incompleteness and unequal weighting of the playing
schedule, and thus isn't generally useful for prediction of a
particular matchup (unless it's MIL beating PIT again, and again, and...)
GP lisper <········@CloudDancer.com> writes:
> For future reference, is there a simple way to walk two lists
> simultaneously? I can only think of 'aref as a solution, with careful
> "pointer" manipulation.
(loop :for a :in list-of-a
:for b :in list-of-b
:for c :across string-of-c
:for d :across vector-of-d
:do (things-with a b c d))
--
__Pascal Bourguignon__
GP lisper <········@CloudDancer.com> writes:
>
> For future reference, is there a simple way to walk two lists
> simultaneously? I can only think of 'aref as a solution, with careful
> "pointer" manipulation.
Well, that depends on what you mean by "walk two lists simultaneously".
The simplest interpretation is that you want to go down two lists, each
one a single element at a time. In that case, LOOP works quite nicely:
(loop for element1 in list1
as element2 in list2
do ....)
If you need to do something more like a merge-type operation where you
go down lists, but not in lock step, then you would typically want to
handle the iteration manually, using POP as needed:
(loop with element1 = nil and element2 = nil
while (or list1 list2)
do (cond ((...) (setq element1 (pop list1)))
((...) (setq element2 (pop list2)))
...))
If you need random access, then lists are the wrong data structure to
use. You should use vectors, or perhaps hash tables instead.
Also, as an aside. It would be more lisp-like and also faster for
comparison purposes if you used symbols instead of strings for the
baseball team abbreviations:
((TOR 1) (KC 2) ...)
--
Thomas A. Russ, USC/Information Sciences Institute
On 11 May 2009 08:59:03 -0700, <···@sevak.isi.edu> wrote:
>
> Also, as an aside. It would be more lisp-like and also faster for
> comparison purposes if you used symbols instead of strings for the
> baseball team abbreviations:
>
> ((TOR 1) (KC 2) ...)
Except symbols don't work in SQL table access.
--
Humans are allergic to change. "We've always done it that way" is not
a good reason to continue to do so. That's why I have a clock on my
office wall that runs backwards. It forces visitors to think.
They hate me for that. - Admiral Hopper.
On May 11, 2:36 pm, GP lisper <········@CloudDancer.com> wrote:
> On 11 May 2009 08:59:03 -0700, <····@sevak.isi.edu> wrote:
>
>
>
> > Also, as an aside. It would be more lisp-like and also faster for
> > comparison purposes if you used symbols instead of strings for the
> > baseball team abbreviations:
>
Would be more 'lisp like' to use do* instead of loop :-P
(do* ((car1 (car l1) (car cdr1))
(cdr1 (cdr l1) (cdr cdr1))
(car2 (car l2) (car cdr2))
(cdr2 (cdr l2) (cdr cdr2)))
((or (not car1) (not car2)))
(print car1) (print car2)))
This can be abstracted into a macro like so:
--
(defmacro dolists (keys/lists &body body)
(flet ((make-do (key/list)
(let ((cdr (gensym)))
`((,(first key/list) (car ,(second key/list)) (car ,cdr))
(,cdr (cdr ,(second key/list)) (cdr ,cdr))))))
`(do* ,(mapcan #'make-do keys/lists)
((or ,@(mapcar #'(lambda (key/list) `(not ,(first key/list))) keys/
lists)))
,@body)))
--
(I think something like this appears in On Lisp or one of the other
texts, but I couldn't find it so I wrote my own...)
(Is only cursorily tested, so if there is an error, well, that
happens.. works on my test-case, however)
--
>(dolists ((a '(1 2 3 4 5))
> (b '(6 7 8 9 10)))
> (print a) (print b))
> 1
> 6
> 2
> 7
> 3
> 8
> 4
> 9
> 5
> 10
--
> > ((TOR 1) (KC 2) ...)
>
> Except symbols don't work in SQL table access.
>
Symbol names, however, do.
On May 12, 11:01 pm, ··················@gmail.com wrote:
> This can be abstracted into a macro like so:
> --
> (defmacro dolists (keys/lists &body body)
> (flet ((make-do (key/list)
> (let ((cdr (gensym)))
> `((,(first key/list) (car ,(second key/list)) (car ,cdr))
> (,cdr (cdr ,(second key/list)) (cdr ,cdr))))))
> `(do* ,(mapcan #'make-do keys/lists)
> ((or ,@(mapcar #'(lambda (key/list) `(not ,(first key/list))) keys/
> lists)))
> ,@body)))
> --
Thinking about it i think this needs some sort of once-only around it
to make it only evaluate the 'lists' once:
-
(defmacro dolists (keys/lists &body body)
(let (letform)
(labels ((make-do (key/list)
(let ((listkey (gensym))
(cdr (gensym)))
(push (list listkey (second key/list)) letform)
`((,(first key/list) (car ,listkey) (car ,cdr))
(,cdr (cdr ,listkey) (cdr ,cdr))))))
(let ((dobody (mapcan #'make-do keys/lists)))
`(let ,letform
(do* ,dobody
((or ,@(mapcar #'(lambda (key/list) `(not ,(first key/list)))
keys/lists)))
,@body))))))
-
I knew it had to be wrong when I thought I got it right the first
time :-)
On May 12, 11:14 pm, ··················@gmail.com wrote:
> On May 12, 11:01 pm, ··················@gmail.com wrote:> This can be abstracted into a macro like so:
> > --
> > (defmacro dolists (keys/lists &body body)
> > (flet ((make-do (key/list)
> > (let ((cdr (gensym)))
> > `((,(first key/list) (car ,(second key/list)) (car ,cdr))
> > (,cdr (cdr ,(second key/list)) (cdr ,cdr))))))
> > `(do* ,(mapcan #'make-do keys/lists)
> > ((or ,@(mapcar #'(lambda (key/list) `(not ,(first key/list))) keys/
> > lists)))
> > ,@body)))
> > --
>
> Thinking about it i think this needs some sort of once-only around it
> to make it only evaluate the 'lists' once:
> -
> (defmacro dolists (keys/lists &body body)
> (let (letform)
> (labels ((make-do (key/list)
> (let ((listkey (gensym))
> (cdr (gensym)))
> (push (list listkey (second key/list)) letform)
> `((,(first key/list) (car ,listkey) (car ,cdr))
> (,cdr (cdr ,listkey) (cdr ,cdr))))))
> (let ((dobody (mapcan #'make-do keys/lists)))
> `(let ,letform
> (do* ,dobody
> ((or ,@(mapcar #'(lambda (key/list) `(not ,(first key/list)))
> keys/lists)))
> ,@body))))))
> -
> I knew it had to be wrong when I thought I got it right the first
> time :-)
This is probably a more robust version as the previous one returned
on the first 'nil' in the list. (as opposed to either the first nil
cdr or the last nil cdr).
(below is a version of the last nil cdr).
(change and to or for first nil cdr).
Getting macros right always takes me a few tries...
(defmacro dolists (keys/lists &body body)
(let (letform
notform)
(labels ((make-do (key/list)
(let ((listkey (gensym))
(cdr (gensym)))
(push (list listkey (second key/list)) letform)
(push `(not ,cdr) notform)
`((,(first key/list) (car ,listkey) (car ,cdr))
(,cdr (cdr ,listkey) (cdr ,cdr)))
)))
(let ((dobody (mapcan #'make-do keys/lists)))
`(let ,letform
(do* ,dobody
(nil)
,@body
(when (and ,@notform)
(return))
))))))
On May 11, 8:36 pm, GP lisper <········@CloudDancer.com> wrote:
> On 11 May 2009 08:59:03 -0700, <····@sevak.isi.edu> wrote:
>
>
>
> > Also, as an aside. It would be more lisp-like and also faster for
> > comparison purposes if you used symbols instead of strings for the
> > baseball team abbreviations:
>
> > ((TOR 1) (KC 2) ...)
>
> Except symbols don't work in SQL table access.
You can alsways do
(string 'TOR)
when accessing the DB.
Cheers
--
Marco
ELS 2009 www.european-lisp-symposium.org
>
> --
> Humans are allergic to change. "We've always done it that way" is not
> a good reason to continue to do so. That's why I have a clock on my
> office wall that runs backwards. It forces visitors to think.
> They hate me for that. - Admiral Hopper.