Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

I'm new to Lisp and I'm yet to wrap my head around the Lisp way of writing programs. Any comments regarding approach, style, missed opportunities appreciated:

In particular, please advice if I build results list correctly ((setf merged-list (append merged-list (list a)))).

;;;; Count inversions
(defun small-list (list)
  (or (null list) (null (rest list))))

(defun split-in-half (list)
  (let ((mid (ceiling (length list) 2)))
    (values (subseq list 0 mid)
            (subseq list mid))))

(defun count-inversions (list)
  (if (small-list list) (list list 0)
    (multiple-value-bind (lower upper) (split-in-half list)
      (merge-inversions
        (count-inversions lower)
        (count-inversions upper)))))

(defun merge-inversions (lower-pair upper-pair)
  (let ((lower (first lower-pair))
        (upper (first upper-pair))
        (merged-list '())
        (num-inversions 0))
    (loop while (not (and (null lower) (null upper)))
          do (cond
               ((null lower) (let ((a (first upper)))
                               (setf merged-list (append merged-list (list a)))
                               (setf upper (rest upper))))
               ((null upper) (let ((a (first lower)))
                               (setf merged-list (append merged-list (list a)))
                               (setf lower (rest lower))))
               ((< (first lower) (first upper)) (let ((a (first lower)))
                                                (setf merged-list (append merged-list (list a)))
                                                (setf lower (rest lower))) )

               (t (let ((a (first upper)))
                    (setf merged-list (append merged-list (list a)))
                    (setf upper (rest upper))
                    (incf num-inversions (length lower))))))
    (list merged-list (+ (second lower-pair) (second upper-pair) num-inversions)))

UPD: revised version using @sds's suggestions:

(defun small-list-p (list)
  (or (null list) (null (rest list))))

(defun split-in-half (list)
  (let ((mid (ceiling (length list) 2)))
    (values (subseq list 0 mid)
            (subseq list mid))))

(defun count-inversions (list)
  (if (small-list-p list) (list list 0)
    (multiple-value-bind (lower upper) (split-in-half list)
      (merge-inversions
        (count-inversions lower)
        (count-inversions upper)))))

(defmacro move-last (source target)
  `(setf ,target (nconc ,target (list (pop ,source)))))

Function MERGE-INVERSIONS:

(defun merge-inversions (lower-pair upper-pair )
  (loop 
    with lower = (first lower-pair)
    with upper = (first upper-pair)
    with merged-list = '()
    with num-inversions = 0
    while (not (and (null lower) (null upper)))
    do (cond
         ((null lower) (move-last upper merged-list))
         ((null upper) (move-last lower merged-list))
         ((< (first lower) (first upper)) (move-last lower merged-list))
         (t
          (move-last upper merged-list)
          (incf num-inversions (length lower)) ))
    finally (return (list merged-list
                          (+ (second lower-pair)
                             (second upper-pair)
                             num-inversions)))))

Performance went from this

139.740 seconds of real time
80,080,445,136 bytes consed

to this:

26.411 seconds of real time
87,009,536 bytes consed
share|improve this question
@RTOSkit, As I said, I need advice on how to make my lisp better. The program does what it needs to do, however there is certainly ways to make it more concise, efficient, elegant. I would like to learn them. – zzandy Feb 7 at 16:26
No docstrings!! – Gareth Rees Feb 8 at 21:06
An explanation of what this code is doing would be appreciated. Also, I see you don't declare any types. – Faheem Mitha Mar 3 at 18:22
@FaheemMitha, the code is aimed at counting inversions on a list, that is each situation when an element lower in the list is greater than an element higher in the list. Regarding types, could you please elaborate, as I mentioned I'm new to Lisp, and might easily be missing something obvious. – zzandy Mar 3 at 21:14
@zzandy: I think adding type declarations is used when you want to improve performance and/or when you want to add some typing to improve error checking of your code. (Specifically, for many operations, simple vectors are faster than linked lists.) However, performance considerations may not apply in your case. Most lisp books have sections on this topic. It is in the Common Lisp standard. Could you add a usage example for your code that the reader could run? – Faheem Mitha Mar 4 at 10:08
show 3 more comments

1 Answer

up vote 4 down vote accepted

  1. Use nconc instead of append for speed in

    (setf merged-list (append merged-list (list a)))

    Note that you need setf with nconc only if merged-list is nil.

  2. Use pop: instead of

    (let ((a (first lower))) (setf merged-list (append merged-list (list a))) (setf lower (rest lower))))

    you can write

    (setf merged-list (nconc merged-list (list (pop lower))))

  3. The combination of let and loop creates extra indentation for no good reason. You can use with clause in loop to create bindings instead, or use the do macro.

  4. Usually predicates are named with a -p suffix, so I suggest that you rename your small-list to small-list-p.

  5. Please fix line breaks and indentation in the third cond clause.

share|improve this answer
Thanks, that's a reply I was hoping for. I've changed indentation in third clause, I that what you meant? – zzandy Feb 8 at 9:09
@zzandy: looks good now (I added another small thing, see #3) – sds Feb 8 at 13:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.