Hello!
I am trying to solve a problem at online programmnig contest
(https://www.spoj.pl/problems/PIGBANK/). My program is asymptotically
efficient but I am getting "Time limit exceeded". I suspect I should
optimize the program to not to stress GC and to let type inferencer
do its work.
Could you please suggest what else could be done?
I am using CLISP. The contest system supports also GCL, should I use
GCL?
Here is the source:
(defmacro coin-weight (c)
`(cdr ,c))
(defmacro coin-price (c)
`(car ,c))
(setq table (make-array 10001 :element-type 'fixnum))
(defun solve2 (target-weight coins)
(declare (type fixnum target-weight))
(declare (type (array 'fixnum 1) table))
(declare (optimize (speed 3)))
(loop for i from 0 to target-weight do (setf (aref table i) nil))
(setf (aref table 0) 0)
(loop for c in coins do
(loop for i from (coin-weight c) to target-weight do
(let ((a (aref table (- i (coin-weight c)))))
(when a
(setf (aref table i)
(cond
((aref table i) (min (aref table i) (+ a
(coin-price c))))
(t (+ a (coin-price c)))))))))
(aref table target-weight))
(dotimes (i (read))
(let ((w (read)) (c nil) (r nil))
(setq w (- (read) w))
(dotimes (j (read))
(push (cons (read) (read)) c))
(setq r (solve2 w c))
(cond
(r (format t "The minimum amount of money in the piggy-bank is
~a.~%" r))
(t (format t "This is impossible.~%")))))
Anton V. Belyaev wrote:
> Hello!
>
> I am trying to solve a problem at online programmnig contest
> (https://www.spoj.pl/problems/PIGBANK/). My program is asymptotically
> efficient but I am getting "Time limit exceeded". I suspect I should
> optimize the program to not to stress GC and to let type inferencer
> do its work.
> Could you please suggest what else could be done?
>
> I am using CLISP. The contest system supports also GCL, should I use
> GCL?
It's worth trying it on GCL. CLISP is fairly fast for an interpreter,
and GCL not the fastest compiler, but still for some codes it will be
faster.
I can't recommend any programming improvements right now because I
don't really understand your program.
Rob,
I tried GCL and recieved "Timelimit" also.
I rewrote the program in C++ and it was accepted. It took 0.6 sec to
complete the test.
The time limit is 5 sec, so my Lisp program is at least 10 times slower
than C++ one! :(
The C++ variant is accepted, this means that asymptotically my
algorithm is fast enougth.
The case is low level optimization of Lisp program. Are there any
resources on this?
Anton V. Belyaev wrote:
> Rob,
>
> I tried GCL and recieved "Timelimit" also.
> I rewrote the program in C++ and it was accepted. It took 0.6 sec to
> complete the test.
> The time limit is 5 sec, so my Lisp program is at least 10 times slower
> than C++ one! :(
>
> The C++ variant is accepted, this means that asymptotically my
> algorithm is fast enougth.
> The case is low level optimization of Lisp program. Are there any
> resources on this?
I can't make your program work. Some points:-
* If I type in the example given on the website into your program then
it fails after "30 50". There is a bug in the parsing part I think,
though I don't understand the program properly.
* You must use the compiler to get fast lisp programs from GCL
* If you enter this code into a lisp which is writing to standard
output then at the end of each top-level form it will return a value.
At the end of the form (setq table ...) it will output the table to
standard output, which is a lot of zeros. This behaviour isn't nice.
* Put your code in SBCL or CMUCL they will give you many warnings
telling you what you have to do to make the code more optimal. Almost
all of their good advice will apply to GCL too, and probably CLisp.
* Don't declare things on the top level with setq (like "table"), it is
bad style use defvar or defparameter
On Boomtime, The Aftermath 35, 3172 YOLD, Rob Thorpe wrote:
> * You must use the compiler to get fast lisp programs from GCL
This is the case with SPOJ. Input program is first compiled to FASL
(whatever is GCL's file extension for this), which is not rated. What
is being rated is executing code loaded from FASL. Same for clisp,
but advantage is lesser since its .fas files are actually bytecode.
--
__ Maciek Pasternacki <·······@japhy.fnord.org> [ http://japhy.fnord.org/ ]
`| _ |_\ / { Ninja live by code of honor.Magical girl live by code of love.
,|{-}|}| }\/ This lead to many disaster and much destruction of urban area.
\/ |____/ Honor much safer. } ( Junpei @ Megatokyo #674 ) -><-
"Anton V. Belyaev" <·············@gmail.com> writes:
> I tried GCL and recieved "Timelimit" also.
> I rewrote the program in C++ and it was accepted. It took 0.6 sec to
> complete the test.
> The time limit is 5 sec, so my Lisp program is at least 10 times slower
> than C++ one! :(
>
> The C++ variant is accepted, this means that asymptotically my
> algorithm is fast enougth.
No. It just means that for the test cases they present, the constants
in C++ compiled code are low enough.
> The case is low level optimization of Lisp program. Are there any
> resources on this?
There's no need for any low level optimization.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner
Lisp will never beat C on a simple problem, esp in terms of speed, so
it seems to me more sensible (and interesting) to try the more
challenging problems, like Crane Operator that has many submissions but
NO accepted solutions! (This particular problem looks like it's made
for Lisp, involving recurrence relations and symbolic search.)
········@gmail.com wrote:
> Lisp will never beat C on a simple problem, esp in terms of speed, so
> it seems to me more sensible (and interesting) to try the more
> challenging problems, like Crane Operator that has many submissions but
> NO accepted solutions! (This particular problem looks like it's made
> for Lisp, involving recurrence relations and symbolic search.)
I am pretty sure that it is possible to write Lisp program as fast as C
one.
Modern Lisp compilers eliminate dynamic typing overhead.
I saw somewhere an example:
Task was to write a program that does specific processing. Everyone was
allowed to submit solutions in C, Lisp and other languages. Best Lisp
program
was even a bit faster than best C one.
This Lisp program was written in non-Lisp style with knowledge of
certain Lisp
compiler features.
"Anton V. Belyaev" <·············@gmail.com> writes:
> Hello!
>
> I am trying to solve a problem at online programmnig contest
> (https://www.spoj.pl/problems/PIGBANK/). My program is asymptotically
> efficient but I am getting "Time limit exceeded". I suspect I should
> optimize the program to not to stress GC and to let type inferencer
> do its work.
> I am using CLISP. The contest system supports also GCL, should I use
> GCL?
GCL is faster, but I think it's an algorithm problem. You can probably
design an algorithm that can be run in time by clisp.
> Could you please suggest what else could be done?
Find the most worthless coin, and fill the piggy with it.
For example, with the Sample Input, adding a (princ ".") before the
LET of your inner LOOP in SOLVE2:
.......................................................................................................................................................The minimum amount of money in the piggy-bank is 60.
...........................................................................................................................................................................The minimum amount of money in the piggy-bank is 100.
.....This is impossible.
And mine:
(defun solve (target coins)
(if (zerop target)
0
(loop
:for i :from 0 :below (length coins)
:for n = (truncate target (third (aref coins i)))
:do (princ ".")
(when (plusp n)
(let ((rv (solve (- target (* n (third (aref coins i)))) coins)))
(when rv
(return-from solve (+ (* n (second (aref coins i))) rv)))))
:finally (return-from solve nil))))
(defun solve2 (target-weight coins)
(solve target-weight
(sort (map 'vector (lambda (c) (list (/ (float (coin-price c)) (coin-weight c))
(coin-price c)
(coin-weight c)))
coins)
(function <=) :key (function first))))
.The minimum amount of money in the piggy-bank is 60.
.The minimum amount of money in the piggy-bank is 100.
......This is impossible.
(Remove the (PRINC ".") before submitting!)
> Here is the source:
>
> (defmacro coin-weight (c)
> `(cdr ,c))
>
> (defmacro coin-price (c)
> `(car ,c))
>
> (setq table (make-array 10001 :element-type 'fixnum))
>
> (defun solve2 (target-weight coins)
> (declare (type fixnum target-weight))
> (declare (type (array 'fixnum 1) table))
> (declare (optimize (speed 3)))
> (loop for i from 0 to target-weight do (setf (aref table i) nil))
> (setf (aref table 0) 0)
> (loop for c in coins do
> (loop for i from (coin-weight c) to target-weight do
> (let ((a (aref table (- i (coin-weight c)))))
> (when a
> (setf (aref table i)
> (cond
> ((aref table i) (min (aref table i) (+ a
> (coin-price c))))
> (t (+ a (coin-price c)))))))))
> (aref table target-weight))
>
> (dotimes (i (read))
> (let ((w (read)) (c nil) (r nil))
> (setq w (- (read) w))
> (dotimes (j (read))
> (push (cons (read) (read)) c))
> (setq r (solve2 w c))
> (cond
> (r (format t "The minimum amount of money in the piggy-bank is
> ~a.~%" r))
> (t (format t "This is impossible.~%")))))
>
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You cannot really appreciate Dilbert unless you read it in the
original Klingon"
Pascal Bourguignon wrote:
> "Anton V. Belyaev" <·············@gmail.com> writes:
>
> > Hello!
> >
> > I am trying to solve a problem at online programmnig contest
> > (https://www.spoj.pl/problems/PIGBANK/). My program is asymptotically
> > efficient but I am getting "Time limit exceeded". I suspect I should
> > optimize the program to not to stress GC and to let type inferencer
> > do its work.
>
> > I am using CLISP. The contest system supports also GCL, should I use
> > GCL?
>
> GCL is faster, but I think it's an algorithm problem. You can probably
> design an algorithm that can be run in time by clisp.
>
>
> > Could you please suggest what else could be done?
>
>
> Find the most worthless coin, and fill the piggy with it.
>
>
> For example, with the Sample Input, adding a (princ ".") before the
> LET of your inner LOOP in SOLVE2:
>
> .......................................................................................................................................................The minimum amount of money in the piggy-bank is 60.
> ...........................................................................................................................................................................The minimum amount of money in the piggy-bank is 100.
> .....This is impossible.
>
> And mine:
>
> (defun solve (target coins)
> (if (zerop target)
> 0
> (loop
> :for i :from 0 :below (length coins)
> :for n = (truncate target (third (aref coins i)))
> :do (princ ".")
> (when (plusp n)
> (let ((rv (solve (- target (* n (third (aref coins i)))) coins)))
> (when rv
> (return-from solve (+ (* n (second (aref coins i))) rv)))))
> :finally (return-from solve nil))))
>
> (defun solve2 (target-weight coins)
> (solve target-weight
> (sort (map 'vector (lambda (c) (list (/ (float (coin-price c)) (coin-weight c))
> (coin-price c)
> (coin-weight c)))
> coins)
> (function <=) :key (function first))))
>
>
> .The minimum amount of money in the piggy-bank is 60.
> .The minimum amount of money in the piggy-bank is 100.
> ......This is impossible.
>
I'm pretty sure that will fail to solve the problem set.
Try (solve2 7 '((1 . 2)(1 . 3)))
To the OP: You could try reducing work in the inner loop, for example,
SETF gets
called even when it's not needed.
Maybe something like (untested!!):
(loop for c in coins do
(let ((weight (coin-weight c))
(price (coin-price c)))
(declare (type fixnum weight price))
(loop for i fixnum from weight to target-weight do
(let ((a (aref table (- i weight)))
(b (aref table i)))
;; Nasty bit: if a compiler thinks that A and B are of
;; type fixnum it may eliminate the tests
;; for nil as unnecessary. NIL is not a fixnum
(when a
(let ((new-price (+ a price)))
(when (or (null b)
(> b new-price))
(setf (aref table i) new-price))))))))
-----
Geoff
"Geoffrey Summerhayes" <·······@hotmail.com> writes:
> [...]
> I'm pretty sure that will fail to solve the problem set.
> Try (solve2 7 '((1 . 2)(1 . 3)))
Oops! I can make it work with an obvious correction, but I'm not sure
it finds the minimum amount in all cases. It'd need more
pre-processing I think.
> To the OP: You could try reducing work in the inner loop, for example,
> SETF gets
> called even when it's not needed.
>
> Maybe something like (untested!!):
>
> (loop for c in coins do
> (let ((weight (coin-weight c))
> (price (coin-price c)))
> (declare (type fixnum weight price))
> (loop for i fixnum from weight to target-weight do
> (let ((a (aref table (- i weight)))
> (b (aref table i)))
> ;; Nasty bit: if a compiler thinks that A and B are of
> ;; type fixnum it may eliminate the tests
> ;; for nil as unnecessary. NIL is not a fixnum
> (when a
> (let ((new-price (+ a price)))
> (when (or (null b)
> (> b new-price))
> (setf (aref table i) new-price))))))))
>
> -----
> Geoff
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
Pascal,
Thanks a lot for your attention.
But the solution you proposed gives incorrect answer for some test
cases:
(setq ccc '((2 . 3) (7 . 5)))
(setq www 31)
(solve-Pascal www ccc) => nil
(solve2 www ccc) => 28
There might be an error in your code, but I cant resolve it because I
cant understand it fully.
Maybe "n" should be counted down after an unsuccessfull try?
"Anton V. Belyaev" <·············@gmail.com> writes:
> Pascal,
>
> Thanks a lot for your attention.
> But the solution you proposed gives incorrect answer for some test
> cases:
>
> (setq ccc '((2 . 3) (7 . 5)))
> (setq www 31)
>
> (solve-Pascal www ccc) => nil
> (solve2 www ccc) => 28
>
> There might be an error in your code, but I cant resolve it because I
> cant understand it fully.
> Maybe "n" should be counted down after an unsuccessfull try?
Yes. But this is not enough, since it's conceivable that with some
combination of prices and weights, the first combination found is not
the minimum. I'd need more preprocessing, analyzing the coins to be
sure the first matching combination is the minimum.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
"Anton V. Belyaev" <·············@gmail.com> writes:
> Hello!
>
> I am trying to solve a problem at online programmnig contest
> (https://www.spoj.pl/problems/PIGBANK/). My program is asymptotically
> efficient but I am getting "Time limit exceeded". I suspect I should
> optimize the program to not to stress GC and to let type inferencer
> do its work.
> Could you please suggest what else could be done?
I would be inclined to look at this, if you could:
1. Give a working example, preferably with some input in the form of a list
(and not reading numbers from stdout).
2. Document a bit how your function is solving the problem.
Yours, Nicolas
> I would be inclined to look at this, if you could:
>
> 1. Give a working example, preferably with some input in the form of a list
> (and not reading numbers from stdout).
>
> 2. Document a bit how your function is solving the problem.
>
> Yours, Nicolas
Nicolas,
1)
(setq ccc '((2 . 3) (7 . 5)))
(setq www 31)
(solve2 www ccc) => 28 ;; 28 is the minimum amount of money
2)
"table" array - is array size of target weight + 1. It keeps the
current
minimum amount of money for each target weight 0..target weight.
We can write table[0] = 0, because with any set of coins it is true.
Then (external loop of solve2 function), for each coin we starting to
improve
our table. For each tartet weight of table (inner loop of solve2) we
trying to
improve the value if this weight can be reached from other weight by
current (external loop c varialbe) coin.
Thats all. At the end we look at table[target-weight]. It contains
minimum
amount of money for the weight or nil if it is unreachable with given
coin set.
OK, here you go. I doubt that you will have any speed problems with the
program below. What about a larger test?
Nicolas
(defstruct (coin (:type list))
price
weight)
(defun solve-piggy-bank (target-weight coins)
(let ((minimal-amount (make-array (1+ target-weight)
:initial-element nil)))
(setf (aref minimal-amount 0) 0)
(loop for weight from 0 upto target-weight
and amount across minimal-amount
when amount do
(loop for coin in coins
for new-weight = (+ weight (coin-weight coin))
and new-amount = (+ amount (coin-price coin))
when (<= new-weight target-weight) do
(let ((old-amount (aref minimal-amount new-weight)))
(when (or (null old-amount)
(> old-amount new-amount))
(setf (aref minimal-amount new-weight) new-amount)))))
(let ((amount (aref minimal-amount target-weight)))
(if amount
(format t "Minimal amount: ~A~%" amount)
(format t "Impossible!~%")))))
(solve-piggy-bank 31 '((2 3) (7 5)))
Nicolas Neuss <········@mathematik.uni-karlsruhe.de> writes:
> OK, here you go. I doubt that you will have any speed problems with the
> program below. What about a larger test?
To be clear: maybe you will still hit the limit for a large numbers of
coins. But I am quite sure that we can easily improve the performance if
you provide a suitable testcase.
Nicolas
Nicolas,
Thanks for your variant of the program.
I tried to sumbit it - "Time limit" as well (both CLISP and GCL).
It is easy to generate a large test by random. But I dont know
exact test cases of contest.
Nicolas Neuss wrote:
> OK, here you go. I doubt that you will have any speed problems with the
> program below. What about a larger test?
>
> Nicolas
>
> (defstruct (coin (:type list))
> price
> weight)
>
> (defun solve-piggy-bank (target-weight coins)
> (let ((minimal-amount (make-array (1+ target-weight)
> :initial-element nil)))
> (setf (aref minimal-amount 0) 0)
> (loop for weight from 0 upto target-weight
> and amount across minimal-amount
> when amount do
> (loop for coin in coins
> for new-weight = (+ weight (coin-weight coin))
> and new-amount = (+ amount (coin-price coin))
> when (<= new-weight target-weight) do
> (let ((old-amount (aref minimal-amount new-weight)))
> (when (or (null old-amount)
> (> old-amount new-amount))
> (setf (aref minimal-amount new-weight) new-amount)))))
> (let ((amount (aref minimal-amount target-weight)))
> (if amount
> (format t "Minimal amount: ~A~%" amount)
> (format t "Impossible!~%")))))
>
> (solve-piggy-bank 31 '((2 3) (7 5)))
"Anton V. Belyaev" <·············@gmail.com> writes:
> Nicolas,
>
> Thanks for your variant of the program.
> I tried to sumbit it - "Time limit" as well (both CLISP and GCL).
>
> It is easy to generate a large test by random. But I dont know
> exact test cases of contest.
OK, I see. One submits a program, and it is tested against unknown test
cases. At first sight, this looks fairer, but at second sight, I doubt it,
because
1. There may be people knowing the test cases and having an unfair
advantage.
2. It precludes any intelligent program development where Lisp shines.
There is simply no help against idiotic tests which aim only at solving
very many and small piggy-bank problems. In such a case, I/O might be
the decisive factor.
I fear that this makes the problem rather uninteresting for me, because I
refuse to optimize programs without knowing the direction.
Nicolas
Nicolas Neuss wrote:
> "Anton V. Belyaev" <·············@gmail.com> writes:
>
> > Nicolas,
> >
> > Thanks for your variant of the program.
> > I tried to sumbit it - "Time limit" as well (both CLISP and GCL).
> >
> > It is easy to generate a large test by random. But I dont know
> > exact test cases of contest.
>
> OK, I see. One submits a program, and it is tested against unknown test
> cases. At first sight, this looks fairer, but at second sight, I doubt it,
> because
>
> 1. There may be people knowing the test cases and having an unfair
> advantage.
>
> 2. It precludes any intelligent program development where Lisp shines.
> There is simply no help against idiotic tests which aim only at solving
> very many and small piggy-bank problems. In such a case, I/O might be
> the decisive factor.
>
> I fear that this makes the problem rather uninteresting for me, because I
> refuse to optimize programs without knowing the direction.
>
> Nicolas
Remember, I rewrote the program in C++ and it was accepted.
I thought it is possible to optimize Lisp program in low level (adding
type proclamations,
using arrays instead of lists, etc) to achieve C++ speed.
But if IO speed is critical we really cant improve the program.
"Anton V. Belyaev" <·············@gmail.com> writes:
> Remember, I rewrote the program in C++ and it was accepted. I thought it
> is possible to optimize Lisp program in low level (adding type
> proclamations, using arrays instead of lists, etc) to achieve C++ speed.
> But if IO speed is critical we really cant improve the program.
You can, but it is some work. What you ask for is the rather boring task
of making a Lisp program run as fast as a C/C++ equivalent. This will
usually not be possible with CLISP. Period. The only other implementation
which we have available is GCL. In my experience, optimizing Lisp code for
GCL is a hard task, and not really worthwile. Using SBCL, CMUCL, Allegro,
Lispworks optimization is much easier.
Sorry, this does not wet my appetite. At first, I thought that at least
the piggy-bank problem might be interesting. But it looks as if the whole
stuff is simply another "Programming Language Shootout", probably even
worse. For this kind of optimization the sig below fits very well.
Nicolas
[1] Note that this does in no way discredit CLISP. There are problems
which are much more interesting than "piggy-bank" and which can be solved
with CLISP better than with any other general purpose language, e.g.:
compute sqrt(2) up to 10000 digits. In CLISP, this is simply "(sqrt 2L0)".
--
Performance is the last refuge of the miserable programmer. (Erik Naggum)
Nicolas Neuss wrote:
> "Anton V. Belyaev" <·············@gmail.com> writes:
>
> > Remember, I rewrote the program in C++ and it was accepted. I thought it
> > is possible to optimize Lisp program in low level (adding type
> > proclamations, using arrays instead of lists, etc) to achieve C++ speed.
> > But if IO speed is critical we really cant improve the program.
>
> You can, but it is some work. What you ask for is the rather boring task
> of making a Lisp program run as fast as a C/C++ equivalent. This will
> usually not be possible with CLISP. Period. The only other implementation
> which we have available is GCL. In my experience, optimizing Lisp code for
> GCL is a hard task, and not really worthwile. Using SBCL, CMUCL, Allegro,
> Lispworks optimization is much easier.
>
> Sorry, this does not wet my appetite. At first, I thought that at least
> the piggy-bank problem might be interesting. But it looks as if the whole
> stuff is simply another "Programming Language Shootout", probably even
> worse. For this kind of optimization the sig below fits very well.
>
The one thing I cannot find on the site is information on how
the timing is done, let alone what is being timed. It could be
that for C++ the compiled executable is timed and for the Lisp
code includes CLISP's and GCL's load/startup times.
----
Geoff
Nicolas Neuss wrote:
-snip-
> Sorry, this does not wet my appetite. At first, I thought that at least
> the piggy-bank problem might be interesting. But it looks as if the whole
> stuff is simply another "Programming Language Shootout", probably even
> worse. For this kind of optimization the sig below fits very well.
-snip-
> Performance is the last refuge of the miserable programmer. (Erik Naggum)
That sig is so lacking in context that an ordinary reading would take
"Performance" to mean the performance of the programmer.