Lisp newbie trying to optimize recursive algorithm, help?

[Konfusius]

I tested your heavily optimized array version count-inversions-6 on my PC and it still takes more than twice the time than the OPs version without a funcalled predicate (0.562 seconds vs 0.205 seconds). Maybe its just my hardware (Intel Pentium Dual-Core E5300 @ 2.60GHz) but all the arrays and declarations don't seem to help very much.

[tensorproduct]

I tested your heavily optimized array version count-inversions-6 on my PC and it still takes more than twice the time than the OPs version without a funcalled predicate (0.562 seconds vs 0.205 seconds). Maybe its just my hardware (Intel Pentium Dual-Core E5300 @ 2.60GHz) but all the arrays and declarations don't seem to help very much.

I've tested my original code (without the funcall) against wvxvw's and I found the opposite to what you have: 0.169 seconds vs 0.275 (on a 10000 element array or list).

[wvxvw]

^ I think Konfusius compared the optimized array version which uses funcall against your version which he modified to not use funcall. In which case it sounds likely to be true, as the impression I've got from my tests was that the funcall ate most of the resources.
One more thing to test is, as Ramarren suggested: instead of using a funcall to a generic function, do something like:

Code: Select all

(defun comparator (a b)
  (declare (type (fixnum a b))
    (ftype (function (fixnum fixnum) boolean) comparator))
  (< a b))

(defun count-inversions (source &optional (predicate #'comarator))
  (declare (inline comparator)) ...)

But this would be identical (I believe...) to just using the concrete #'< function inside count-inversions, but this sounds more like gambling. Sorry for the untested code above, it's intended for illustration.

Oh, wait, I see it's count-inversions-6, in which case that sounds rather unlikely to be true, or, possibly the Lisp implementation did something wrong compiling that function... wait, there's ideone site, could be good for testing. I'll try it there.

EDIT: http://ideone.com/ufhJ6
(Note that I've reduced it by one order of magnitude so that it would fit into 5 seconds time limit.)
The Lisp used at ideone.com is CLISP, and, well, in this particular case we are seeing the work of the compiler in effect. Probably SBCL knows how to optimize array-based code, while CLISP might be at all using lists to represent arrays, or that would be my guess.

[Konfusius]

I tested count-conversions-6 again but this time with both SBCL and Clozure. In Clozure it took 0.594s and in SBCL it took only 0.1875s. So it was the Lisp implementation.

The OPs version took about 0.21s in both implementations. But this is still only a difference of about 11% compared to the heavily optimized array version.

EDIT
I slightly optimized the OPs code to use fixnums and now its slightly faster than the array version again in SBCL and still more than twice as fast in Clozure CL.

Code: Select all

(defun count-inversions (lst &optional (predicate #'<))
  (if (or (null lst) (null (cdr lst)))
   0
   (let* ((half      (ceiling (/ (length lst) 2)))
         (left-list  (subseq lst 0 half))
         (right-list (subseq lst half)))
     (+ (loop for a fixnum in left-list
            summing (loop for b fixnum in right-list
                      counting (not (< a b)))) ;(funcall predicate a b))))
       (count-inversions left-list predicate)
       (count-inversions right-list predicate)))))

[wvxvw]

Well, that shouldn't happen, because it doesn't make sense, or there must be very bad array implementation in both Clozure and CLISP. I mean, you can't beat O(1) with O(n), unless you do something very silly. In fact, I suspect that as some other dynamic languages (for example JavaScript or Lua) arrays may be implemented as hash tables with integer keys, in which case splitting such an array would be even worse then splitting a list (it would be some kind of O(n log n) I suppose). Though, ultimately, that should not happen with "normal" arrays.

And, by the way, inspired by my guess, I tried this, and the result is quite surprising! Could you please try with CLISP to see if you get the result similar to array?

Code: Select all

(defun make-big-hash-table (x)
  (do* ((y (make-hash-table :size x))
   (i 0 (1+ i)))
       (nil)
    (when (= x i) (return y))
    (setf (gethash i y) (random 1000))))

(defun count-inversions-7 (table &optional (predicate #'<))
  (let ((ht-size (hash-table-count table)))
    (if (< ht-size 2)
   0
   (let* ((half (floor (/ ht-size 2)))
          (right-table (split-hash-table table half)))
     (+ (loop for a fixnum being the hash-values of table
      summing
        (loop for b fixnum being the hash-values of right-table
           counting (not (< a b)))) ;(funcall predicate a b))))
        (count-inversions-7 table predicate)
        (count-inversions-7 right-table predicate))))))

(defun split-hash-table (table half)
  (let ((result (make-hash-table)))
    (maphash
     #'(lambda (key value)
    (when (>= key half)
      (setf (gethash (- key half) result) value)
      (remhash key table))) table) result))

(time (count-inversions-7 (make-big-hash-table 10000)))

;; Evaluation took:
;;   0.499 seconds of real time
;;   0.492031 seconds of total run time (0.492031 user, 0.000000 system)
;;   98.60% CPU
;;   1,397,445,267 processor cycles
;;   16,766,080 bytes consed


[Konfusius]

I didn't use CLISP but SBCL. But I tried your version 7 with CLISP too and it took 4.266s after manually compiling (CLISP doesn't compile automatically). As expected CLISP is very slow because it compiles to interpreted bytecode instead of machine code.

With SBCL your version 7 took 0.672s and 3.031s with Clozure. Thats still much slower than my optimized OPs version.

Well, that shouldn't happen, because it doesn't make sense, or there must be very bad array implementation in both Clozure and CLISP. I mean, you can't beat O(1) with O(n), unless you do something very silly.

The list version isn't O(n). Its mostly O(1) because the lists are traversed sequentially. And the subseq-ing of the lists doesn't fall into account for big n's because its effectively copying the original list only log(n) times.

OTOH, array access in Common Lisp is slow by design because it has to check for index boundaries, simple/non-simpe arrays, and for the various specialized array types.

[wvxvw]

array access in Common Lisp is slow by design [...]

Well, that's something I thought I would avoid by setting the optimization setting as they were - I still don't know Lisp assembler at the level I can understand what is going on in the code it generates, but I hoped to get something similar to C plain arrays of integers (i.e. by setting safety to 0 I would ensure that it would rely on me I will not read/write out of bounds). I thought it was possible because if I did read past the array bounds I would get a memory fault, something I assumed to be similar in nature to the one I'd get in C.

I didn't mean version 7 to be more optimized, I was suggesting it might work the same as the one with the array - because I thought that the implementation that performed bad with arrays might be using a hash-table behind the stage to represent an array.

Re' O(n) - besides doing subseq the algorithm measures the length, and it does it every time, which is really redundant - you need this only once. And the speed of doing subseq is linear, no log(n), sorry It contributes to the complexity of the entire algorithm in a non-linear way (just as you say) - I agree, but if you compare (subseq list) vs (subseq array) it is O(n) vs O(1) proper.

I still don't understand why the result is as you describe, but I'm not knowledgeable enough to research it more. I hope, one day I'll know