[Gcl-devel] Re: Optimize lisp program

[Camm Maguire]

The following message is a courtesy copy of an article
that has been posted to comp.lang.lisp as well.

The following appears fully optimizable using gcl 2.7.0 (cvs head).
Similar can be had in 2.6 with more declarations.

Take care,
=============================================================================
(deftype foo nil `(integer -1 10000))

(defstruct coin
  (weight 1 :type foo)
  (price 1  :type foo))


(defun solve2 (target-weight coins table)
  (declare (foo target-weight))
  (declare ((vector foo) table))
  (declare (optimize (speed 3)))
  (loop for i from 0 to target-weight do (setf (aref table i) -1))
  (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 0)
                (setf (aref table i)
                  (cond
                    ((>= (aref table i) 0) (min (aref table i) (+ a (coin-price 
c))))
                    (t (+ a (coin-price c)))))))))
  (aref table target-weight))

(let ((table (make-array 10001 :element-type 'fixnum)))
  (dotimes (i (read))
    (let ((w (read)) (c nil) (r nil))
      (setq w (- (read) w))
      (dotimes (j (read))
        (push (make-coin :weight (read) :price (read)) c))
      (setq r (solve2 w c table))
      (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" <address@hidden> writes:

> 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?
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah