On 12 Dez., 03:42, gavino <·········@gmail.com> wrote:
> produce some FREE (read non allegro) mainstream apps that show lisp
> superiority
> 1 database
> 2 webserver/appserver
> 3 cms
Challenge for Gavino: finish chapter 2 of Practical Common Lisp.
······@corporate-world.lisp.de wrote:
> On 12 Dez., 03:42, gavino <·········@gmail.com> wrote:
>> produce some FREE (read non allegro) mainstream apps that show lisp
>> superiority
>> 1 database
>> 2 webserver/appserver
>> 3 cms
>
> Challenge for Gavino: finish chapter 2 of Practical Common Lisp.
Anybody have a clue who that Gavino guy is? I haven't visited this
newsgroup for quite a long time, but it seems that some faces (glad that
I didn't mistype the "a", that could have been easy, just two keys
away... ;)) are going to stay...
Jakub Hegenbart
Jakub Hegenbart wrote:
> ······@corporate-world.lisp.de wrote:
>
>> On 12 Dez., 03:42, gavino <·········@gmail.com> wrote:
>>
>>> produce some FREE (read non allegro) mainstream apps that show lisp
>>> superiority
>>> 1 database
>>> 2 webserver/appserver
>>> 3 cms
>>
>>
>> Challenge for Gavino: finish chapter 2 of Practical Common Lisp.
>
>
> Anybody have a clue who that Gavino guy is? I haven't visited this
> newsgroup for quite a long time, but it seems that some faces (glad that
> I didn't mistype the "a", that could have been easy, just two keys
> away... ;)) are going to stay...
Who the hell are you, or anyone else I have not met at an ILC or Lisp
Beer Tasting? Gavino has been annoying this NG for years and has become
a veritable c.l.l institution. Furthermore, he has been successfully
trolled by kenny, the cll metatroll. We are printing up replica Gavino
jerseys now. Gavino is one of us.
hth, kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Dec 12, 12:00 am, Ken Tilton <···········@optonline.net> wrote:
> Jakub Hegenbart wrote:
> > ······@corporate-world.lisp.de wrote:
>
> >> On 12 Dez., 03:42, gavino <·········@gmail.com> wrote:
>
> >>> produce some FREE (read non allegro) mainstream apps that show lisp
> >>> superiority
> >>> 1 database
> >>> 2 webserver/appserver
> >>> 3 cms
>
> >> Challenge for Gavino: finish chapter 2 of Practical Common Lisp.
>
> > Anybody have a clue who that Gavino guy is? I haven't visited this
> > newsgroup for quite a long time, but it seems that some faces (glad that
> > I didn't mistype the "a", that could have been easy, just two keys
> > away... ;)) are going to stay...
>
> Who the hell are you, or anyone else I have not met at an ILC or Lisp
> Beer Tasting? Gavino has been annoying this NG for years and has become
> a veritable c.l.l institution. Furthermore, he has been successfully
> trolled by kenny, the cll metatroll. We are printing up replica Gavino
> jerseys now. Gavino is one of us.
>
> hth, kt
>
> --http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
Ken in my defense is the most boring poster.
gavino schrieb:
> On Dec 12, 12:00 am, Ken Tilton <···········@optonline.net> wrote:
> > Jakub Hegenbart wrote:
> > > ······@corporate-world.lisp.de wrote:
> > >> On 12 Dez., 03:42, gavino <·········@gmail.com> wrote:
...
> Ken in my defense is the most boring poster.
Ey no. Ken is the thunderstorm in every bottleneck around.
On 12 dic, 09:00, Ken Tilton <···········@optonline.net> wrote:
> Jakub Hegenbart wrote:
> > ······@corporate-world.lisp.de wrote:
>
> >> On 12 Dez., 03:42, gavino <·········@gmail.com> wrote:
>
> >>> produce some FREE (read non allegro) mainstream apps that show lisp
> >>> superiority
> >>> 1 database
> >>> 2 webserver/appserver
> >>> 3 cms
>
> >> Challenge for Gavino: finish chapter 2 of Practical Common Lisp.
>
> > Anybody have a clue who that Gavino guy is? I haven't visited this
> > newsgroup for quite a long time, but it seems that some faces (glad that
> > I didn't mistype the "a", that could have been easy, just two keys
> > away... ;)) are going to stay...
>
> Who the hell are you, or anyone else I have not met at an ILC or Lisp
> Beer Tasting? Gavino has been annoying this NG for years and has become
> a veritable c.l.l institution. Furthermore, he has been successfully
> trolled by kenny, the cll metatroll. We are printing up replica Gavino
> jerseys now. Gavino is one of us.
What I suspect is that Kenny and Gavino are the same one... Kenny, are
you using the gavino personality when being in trance or something
like that?
·······@corporate-world.lisp.de" <······@corporate-world.lisp.de>
writes:
> On 12 Dez., 03:42, gavino <·········@gmail.com> wrote:
>> produce some FREE (read non allegro) mainstream apps that show lisp
>> superiority
>> 1 database
>> 2 webserver/appserver
>> 3 cms
>
> Challenge for Gavino: finish chapter 2 of Practical Common Lisp.
You can track his progress on his blog:
http://bootiack.livejournal.com/
Zach
On Tue, 11 Dec 2007 18:42:34 -0800, gavino wrote:
> produce some FREE (read non allegro) mainstream apps that show lisp
> superiority
> 1 database
> 2 webserver/appserver
> 3 cms
Challenge for troll:
Produce some objective (read quantitative) metrics to measure
superiority. And not words like "enterprise-friendly" please.
--
Sohail Somani
http://uint32t.blogspot.com
Sohail Somani <······@taggedtype.net> wrote:
+---------------
| Challenge for troll:
| Produce some objective (read quantitative) metrics to measure
| superiority. And not words like "enterprise-friendly" please.
+---------------
Hey, nothing wrong with "enterprise-friendly"... as long as
it's the name of a real-valued function in closed form *and*
G....o posts to this group an actual instance of it as a
*portable* CL function which accepts a list of pathname
designators comprising the source files of an arbitrary
application and in less than 100 seconds per megabyte of
input source produces a single float valued result in
the closed interval [0.0, 100.0] which represents the
"enterprise-friendliness" of said application.
In the words of the K-prefixed one, "Show us the code..."
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Jason wrote:
> Gavino,
>
> Help me optimize this please.
>
> (defparameter *counter* 0)
>
> (defun roll-nums (sides factor target)
> (incf *counter*)
> (cond
> ((< target 1)
> 0)
> (t (let ((sum 0)
> (fact (/ factor sides)))
> (do ((face 1 (1+ face)))
> ((> face sides))
> (progn
> (incf sum fact)
> (if (< face target)
> (incf sum (roll-nums sides fact (- target face))))))
> ;(incf sum (+ fact (roll-nums sides fact (- target face)))))
> sum))))
>
> (defun expected-throws (candies)
> (let ((*counter* 0))
> (let ((throws (roll-nums 6 1 candies)))
> (list :throws (* 1.0 throws) :counter *counter*))))
>
> I've been waiting for (expected-throws 47) to return for over 26
> minutes!
>
> -Jason
You have an exponential-time algorithm on your hands. Fortunately this
is a case where you can use memoization or dynamic programming to turn
it into a polynomial-time algorithm. Here's a solution with memoization
(not the most elegant, but it works):
(defparameter *counter* 0)
(defun expected-throws (candies)
(let ((*counter* 0))
(let ((throws (roll-nums 6 1 candies)))
(list :throws (* 1.0 throws) :counter *counter*))))
;;; This hash table stores the values returned by roll-nums
;;; for each combination of the factor and target arguments.
;;; (We can ignore sides since it is always 6 when roll-nums
;;; is initially called from expected-throws.
(defparameter *ft-hash* (make-hash-table :test #'equalp))
;;; Look up the sum for a given factor and target.
(defun ft-get (factor target)
(gethash (list factor target) *ft-hash*))
;;; Store the sum for a given factor and target.
(defun ft-put (factor target sum)
(setf (gethash (list factor target) *ft-hash*) sum))
;;; Look up factor and target in the table; if we find a sum,
;;; return it; otherwise call roll-nums and cache the result.
(defun maybe-recurse (sides factor target)
(let ((stored (ft-get factor target)))
(if stored
stored
(let ((computed (roll-nums sides factor target)))
(ft-put factor target computed)
computed))))
;;; The same as your original roll-nums, except that the recursive
;;; call has been replaced by a call to maybe-recurse. (Also, I made
;;; a couple of minor stylistic tweaks, like removing the progn inside
;;; the body of do, and replacing a two-argument if with when.)
(defun roll-nums (sides factor target)
(incf *counter*)
(if (< target 1)
0
(let ((sum 0)
(fact (/ factor sides)))
(do ((face 1 (1+ face)))
((> face sides))
(incf sum fact)
(when (< face target)
(incf sum (maybe-recurse sides fact (- target face)))))
sum)))
In SBCL:
CL-USER> (time (expected-throws 47))
Evaluation took:
0.343 seconds of real time
0.32402 seconds of user run time
0.020001 seconds of system run time
[Run times include 0.06 seconds GC run time.]
0 page faults and
18,694,752 bytes consed.
(:THROWS 13.904762 :COUNTER 928)
On 2007-12-12 15:11:33 -0500, Joseph Dale <·····@berkeley.edu> said:
> You have an exponential-time algorithm on your hands. Fortunately this
> is a case where you can use memoization or dynamic programming to turn
> it into a polynomial-time algorithm. Here's a solution with memoization
> (not the most elegant, but it works):
I think you possibly missed the liklihood Jason was not actually
looking for help from c.l.l at large, just trying to get Gavino to post
on topic.
On Dec 12, 12:20 pm, Raffael Cavallaro <················@pas-d'espam-
s'il-vous-plait-mac.com> wrote:
> On 2007-12-12 15:11:33 -0500, Joseph Dale <·····@berkeley.edu> said:
>
> > You have an exponential-time algorithm on your hands. Fortunately this
> > is a case where you can use memoization or dynamic programming to turn
> > it into a polynomial-time algorithm. Here's a solution with memoization
> > (not the most elegant, but it works):
>
> I think you possibly missed the liklihood Jason was not actually
> looking for help from c.l.l at large, just trying to get Gavino to post
> on topic.
I was actually hoping for both. :)
-Jason
P.S. I'm *STILL* waiting for my original program to return. Going on 3
and 1/2 hours now. I'm morbidly curious about what the value of
*counter* will be...
Jason wrote:
> P.S. I'm *STILL* waiting for my original program to return. Going on 3
> and 1/2 hours now.
How long are you planning to wait? As I pointed out earlier, your
algorithm takes exponential time. That is, the running time of
(expected-throws n) is an exponential function of n, of the form k*c^n.
I timed your program under SBCL, running (expected-throws n) for n = 0
to 25. I then fit a regression line to the logarithm of the runtimes,
which gave me c = 1.880429. This means that (expected-throws (1+ n))
will take about 1.88 times longer than (expected-throws n). By my
calculations, (expected-throws 47) would take nearly two years on my
machine (a 2.2 GHz AMD64 running Linux).
The point here is that when you recognize that you have an
exponential-time algorithm, the only optimization that makes sense is to
find a better algorithm.
> I'm morbidly curious about what the value of
> *counter* will be...
Well, again, you're going to have to find a better way to compute
*counter*. Actually, we can compute *counter* in linear time! *counter*
is the number of times roll-nums gets called, right? So the basic
principle is to notice that:
- for target = 1, no recursive calls are made; *counter* = 1
- for target = 2, one recursive call is made with target = 1, so
*counter* = 1 + 1 = 2
- for target = 3, two recursive calls are made, with target = 2 and
target = 1, so *counter* = 1 + 2 + 1 = 4
- for target = 4, three recursive calls are made, with target = 3,
target = 2, and target = 1, so *counter* = 1 + 4 + 2 + 1 = 8
... and so on. When n gets large enough, the general case (assuming
sides is fixed at six) is:
- for target = n, six recursive calls are made, with target = n - 1,
target = n - 2, ..., target = n - 6. If C(k) is the value of *counter*
for target = k, then C(n) = 1 + C(n-1) + C(n-2) + ... + C(n-6).
From these observations, we can build up the value of *counter* from
small values of target to large:
(defun counter (max-target)
(let ((ctr (make-array (1+ max-target) :initial-element 1)))
(loop for target from 1 to max-target
do (loop for k from 1 to (min (1- target) 6)
do (incf (aref ctr target) (aref ctr (- target k)))))
ctr))
This function returns a vector containing the values of *counter* for
target from 0 to max-target. I get *counter* = 50679972597024 for target
= 47. Now even if each call to roll-nums took only a nanosecond (which
is doubtful), you'd still be waiting at least 50679972597024 / (1e9 *
3600) = 14 hours to get the answer.
If this seems complicated, just notice that *counter* is defined by a
certain recurrence relation, just like the Fibonacci numbers. Now here
are two algorithms for computing the Fibonacci numbers:
(defun naive-fib (n)
(if (< n 2)
1
(+ (naive-fib (- n 1))
(naive-fib (- n 2)))))
(defun faster-fib (n &optional (a 1) (b 1))
(cond ((= n 0) a)
((= n 1) b)
(t (faster-fib (- n 1) b (+ a b)))))
On Dec 12, 4:27 pm, Joseph Dale <·····@berkeley.edu> wrote:
> Jason wrote:
> > P.S. I'm *STILL* waiting for my original program to return. Going on 3
> > and 1/2 hours now.
>
> How long are you planning to wait? As I pointed out earlier, your
> algorithm takes exponential time. That is, the running time of
> (expected-throws n) is an exponential function of n, of the form k*c^n.
>
> I timed your program under SBCL, running (expected-throws n) for n = 0
> to 25. I then fit a regression line to the logarithm of the runtimes,
> which gave me c = 1.880429. This means that (expected-throws (1+ n))
> will take about 1.88 times longer than (expected-throws n). By my
> calculations, (expected-throws 47) would take nearly two years on my
> machine (a 2.2 GHz AMD64 running Linux).
>
> The point here is that when you recognize that you have an
> exponential-time algorithm, the only optimization that makes sense is to
> find a better algorithm.
>
> > I'm morbidly curious about what the value of
> > *counter* will be...
>
> Well, again, you're going to have to find a better way to compute
> *counter*. Actually, we can compute *counter* in linear time! *counter*
> is the number of times roll-nums gets called, right? So the basic
> principle is to notice that:
>
> - for target = 1, no recursive calls are made; *counter* = 1
>
> - for target = 2, one recursive call is made with target = 1, so
> *counter* = 1 + 1 = 2
>
> - for target = 3, two recursive calls are made, with target = 2 and
> target = 1, so *counter* = 1 + 2 + 1 = 4
>
> - for target = 4, three recursive calls are made, with target = 3,
> target = 2, and target = 1, so *counter* = 1 + 4 + 2 + 1 = 8
>
> ... and so on. When n gets large enough, the general case (assuming
> sides is fixed at six) is:
>
> - for target = n, six recursive calls are made, with target = n - 1,
> target = n - 2, ..., target = n - 6. If C(k) is the value of *counter*
> for target = k, then C(n) = 1 + C(n-1) + C(n-2) + ... + C(n-6).
>
> From these observations, we can build up the value of *counter* from
> small values of target to large:
>
> (defun counter (max-target)
> (let ((ctr (make-array (1+ max-target) :initial-element 1)))
> (loop for target from 1 to max-target
> do (loop for k from 1 to (min (1- target) 6)
> do (incf (aref ctr target) (aref ctr (- target k)))))
> ctr))
>
> This function returns a vector containing the values of *counter* for
> target from 0 to max-target. I get *counter* = 50679972597024 for target
> = 47. Now even if each call to roll-nums took only a nanosecond (which
> is doubtful), you'd still be waiting at least 50679972597024 / (1e9 *
> 3600) = 14 hours to get the answer.
>
> If this seems complicated, just notice that *counter* is defined by a
> certain recurrence relation, just like the Fibonacci numbers. Now here
> are two algorithms for computing the Fibonacci numbers:
>
> (defun naive-fib (n)
> (if (< n 2)
> 1
> (+ (naive-fib (- n 1))
> (naive-fib (- n 2)))))
>
> (defun faster-fib (n &optional (a 1) (b 1))
> (cond ((= n 0) a)
> ((= n 1) b)
> (t (faster-fib (- n 1) b (+ a b)))))
Joseph,
Thanks for your help. My code is almost identical to yours. Here's
*my* final version:
-- file: rolls.lisp --
(defun calc-rolls (sides target)
(let ((calls 0)
(cache (make-hash-table :test #'equal)))
(labels (; recursively search for the number of 'sides' sided dice
to roll
; to achieve exactly 'target' result.
(rolls (sides factor target)
(incf calls)
(if (< target 1)
0
(let ((sum 0)
(fact (/ factor sides)))
(do ((side 1 (1+ side)))
((> side sides))
(progn
(incf sum fact)
(incf sum (cached-roll? sides fact (- target side)))))
sum)))
; pull from the hash-table, if there is a cached value.
; calulate otherwise.
(cached-roll? (sides factor target)
(let* ((key (list sides factor target))
(val (gethash key cache)))
(if (null val)
(setf val (rolls sides factor target)))
(setf (gethash key cache) val)
val)))
(list :rolls (* 1.0 (rolls sides 1 target)) :calls calls))))
-- output --
; SLIME 2006-04-20
CL-USER> (compile-file "rolls.lisp")
;; Compiling file /Users/jason/tmp/rolls.lisp ...
;; Wrote file /Users/jason/tmp/rolls.fas
0 errors, 0 warnings
#P"/Users/jason/tmp/rolls.fas"
NIL
NIL
CL-USER> (load "rolls.fas")
;; Loading file rolls.fas ...
;; Loaded file rolls.fas
T
CL-USER> (time (calc-rolls 6 47))
Real time: 0.077444 sec.
Run time: 0.066474 sec.
Space: 1171880 Bytes
GC: 2, GC time: 0.023636 sec.
(:ROLLS 13.904762 :CALLS 1164)
CL-USER>
Gavino, you missed out on the fun this time. Don't worry, you can help
me optimize the next one, buddy!
-Jason
Jason wrote:
> P.S. I'm *STILL* waiting for my original program to return. Going on 3
> and 1/2 hours now.
How long are you planning to wait? As I pointed out earlier, your
algorithm takes exponential time. That is, the running time of
(expected-throws n) is an exponential function of n, of the form k*c^n.
I timed your program under SBCL, running (expected-throws n) for n = 0
to 25. I then fit a regression line to the logarithm of the runtimes,
which gave me c = 1.880429. This means that (expected-throws (1+ n))
will take about 1.88 times longer than (expected-throws n). By my
calculations, (expected-throws 47) would take nearly two years on my
machine (a 2.2 GHz AMD64 running Linux).
The point here is that when you recognize that you have an
exponential-time algorithm, the only optimization that makes sense is to
find a better algorithm.
> I'm morbidly curious about what the value of
> *counter* will be...
Well, again, you're going to have to find a better way to compute
*counter*. Actually, we can compute *counter* in linear time! *counter*
is the number of times roll-nums gets called, right? So the basic
principle is to notice that:
- for target = 1, no recursive calls are made; *counter* = 1
- for target = 2, one recursive call is made with target = 1, so
*counter* = 1 + 1 = 2
- for target = 3, two recursive calls are made, with target = 2 and
target = 1, so *counter* = 1 + 2 + 1 = 4
- for target = 4, three recursive calls are made, with target = 3,
target = 2, and target = 1, so *counter* = 1 + 4 + 2 + 1 = 8
... and so on. When n gets large enough, the general case (assuming
sides is fixed at six) is:
- for target = n, six recursive calls are made, with target = n - 1,
target = n - 2, ..., target = n - 6. If C(k) is the value of *counter*
for target = k, then C(n) = 1 + C(n-1) + C(n-2) + ... + C(n-6).
From these observations, we can build up the value of *counter* from
small values of target to large:
(defun counter (max-target)
(let ((ctr (make-array (1+ max-target) :initial-element 1)))
(loop for target from 1 to max-target
do (loop for k from 1 to (min (1- target) 6)
do (incf (aref ctr target) (aref ctr (- target k)))))
ctr))
This function returns a vector containing the values of *counter* for
target from 0 to max-target. I get *counter* = 50679972597024 for target
= 47. Now even if each call to roll-nums took only a nanosecond (which
is doubtful), you'd still be waiting at least 50679972597024 / (1e9 *
3600) = 14 hours to get the answer.
If this seems complicated, just notice that *counter* is defined by a
certain recurrence relation, just like the Fibonacci numbers. Now here
are two algorithms for computing the Fibonacci numbers:
(defun naive-fib (n)
(if (< n 2)
1
(+ (naive-fib (- n 1))
(naive-fib (- n 2)))))
(defun faster-fib (n &optional (a 1) (b 1))
(cond ((= n 0) a)
((= n 1) b)
(t (faster-fib (- n 1) b (+ a b)))))
On Dec 12, 4:30 pm, Joseph Dale <·····@berkeley.edu> wrote:
> Jason wrote:
> > P.S. I'm *STILL* waiting for my original program to return. Going on 3
> > and 1/2 hours now.
>
> How long are you planning to wait? As I pointed out earlier, your
> algorithm takes exponential time. That is, the running time of
> (expected-throws n) is an exponential function of n, of the form k*c^n.
>
> I timed your program under SBCL, running (expected-throws n) for n = 0
> to 25. I then fit a regression line to the logarithm of the runtimes,
> which gave me c = 1.880429. This means that (expected-throws (1+ n))
> will take about 1.88 times longer than (expected-throws n). By my
> calculations, (expected-throws 47) would take nearly two years on my
> machine (a 2.2 GHz AMD64 running Linux).
>
> The point here is that when you recognize that you have an
> exponential-time algorithm, the only optimization that makes sense is to
> find a better algorithm.
>
> > I'm morbidly curious about what the value of
> > *counter* will be...
>
> Well, again, you're going to have to find a better way to compute
> *counter*. Actually, we can compute *counter* in linear time! *counter*
> is the number of times roll-nums gets called, right? So the basic
> principle is to notice that:
>
> - for target = 1, no recursive calls are made; *counter* = 1
>
> - for target = 2, one recursive call is made with target = 1, so
> *counter* = 1 + 1 = 2
>
> - for target = 3, two recursive calls are made, with target = 2 and
> target = 1, so *counter* = 1 + 2 + 1 = 4
>
> - for target = 4, three recursive calls are made, with target = 3,
> target = 2, and target = 1, so *counter* = 1 + 4 + 2 + 1 = 8
>
> ... and so on. When n gets large enough, the general case (assuming
> sides is fixed at six) is:
>
> - for target = n, six recursive calls are made, with target = n - 1,
> target = n - 2, ..., target = n - 6. If C(k) is the value of *counter*
> for target = k, then C(n) = 1 + C(n-1) + C(n-2) + ... + C(n-6).
>
> From these observations, we can build up the value of *counter* from
> small values of target to large:
>
> (defun counter (max-target)
> (let ((ctr (make-array (1+ max-target) :initial-element 1)))
> (loop for target from 1 to max-target
> do (loop for k from 1 to (min (1- target) 6)
> do (incf (aref ctr target) (aref ctr (- target k)))))
> ctr))
>
> This function returns a vector containing the values of *counter* for
> target from 0 to max-target. I get *counter* = 50679972597024 for target
> = 47. Now even if each call to roll-nums took only a nanosecond (which
> is doubtful), you'd still be waiting at least 50679972597024 / (1e9 *
> 3600) = 14 hours to get the answer.
>
> If this seems complicated, just notice that *counter* is defined by a
> certain recurrence relation, just like the Fibonacci numbers. Now here
> are two algorithms for computing the Fibonacci numbers:
>
> (defun naive-fib (n)
> (if (< n 2)
> 1
> (+ (naive-fib (- n 1))
> (naive-fib (- n 2)))))
>
> (defun faster-fib (n &optional (a 1) (b 1))
> (cond ((= n 0) a)
> ((= n 1) b)
> (t (faster-fib (- n 1) b (+ a b)))))
Wow. This is an excellent description of the mathematics behind this
problem. Thank you!
I'm out of town until Monday, and my program is happily running in my
absence. Let's see where we are in 108 hours. :P
-Jason