Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Arrays vs. lists in Lisp: Why are lists so much faster in the code below?

I got an unexpected result while solving Problem 75 in Project Euler. My code does find the correct solution, but it behaves strangely.

My solution consists of traversing a Pythagorean tree (Barning's matrices) until the perimeter limit is reached, counting the numbers of times the perimeter assumed each value, and, lastly, counting the perimeter lengths that occurred only once. My admittedly untidy but functioning code is:

(defparameter *barning-matrixes*
   '(#(1 -2  2) #(2 -1  2) #(2 -2  3)
     #(1  2  2) #(2  1  2) #(2  2  3)
     #(-1 2  2) #(-2 1  2) #(-2 2  3)))

(defparameter *lengths* (make-array 1500001 :initial-element 0))

(defun expand-node (n)
"Takes a primitive Pythagorean triple in a vector and traverses subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
   (let ((perimeter (reduce #'+ n)))
   (unless (> perimeter 1500000)
     (let ((next-nodes (mapcar #'(lambda (x)
                                   (reduce #'+ (map 'vector #'* n x))) *barning-matrixes*)))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

(expand-node #(3 4 5))  ; Takes too darn long :-(
(count 1 *lengths*)

I expected the tree expansion to run in a few milliseconds, but the expand-node function took 8.65 seconds--a lot more than expected--to traverse a not very large tree.

However, I was surprised when I tweaked the code to remove the vectors...

(defparameter *barning-matrixes*
   '((1 -2  2) (2 -1  2) (2 -2  3)
     (1  2  2) (2  1  2) (2  2  3)
     (-1 2  2) (-2 1  2) (-2 2  3)))


(defparameter *lengths* (make-array 1500001 :initial-element 0))

(defun expand-node (n)
"Takes a primitive Pythagorean triple in a list and traverses subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
   (let ((perimeter (reduce #'+ n)))
   (unless (> perimeter 1500000)
     (let ((next-nodes (mapcar #'(lambda (x) (reduce #'+ (mapcar #'* n x))) *barning-matrixes*)))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

(expand-node '(3 4 5))  ; Much faster, but why?!
(count 1 *lengths*)

...and the traversing went hugely faster, taking only 35 ms. I'm intrigued by this massive difference and am hoping someone out there can explain why it happened.

Thanks, Paulo

PS: I'm using CCL for all this.

like image 490
Paulo Mendes Avatar asked Jul 20 '16 23:07

Paulo Mendes


People also ask

Why arrays are faster than lists?

Whereas ArrayList can increase and decrease size dynamically. An Array is a collection of similar items. Whereas ArrayList can hold item of different types. An array is faster and that is because ArrayList uses a fixed amount of array.

Why are lists slower than arrays?

Slower Search Time: Linked list have slower search times than arrays as random access is not allowed. Unlike arrays where the elements can be search by index, linked list require iteration.

Which is more efficient array or List?

The array is faster in case of access to an element while List is faster in case of adding/deleting an element from the collection.

Which is faster accessing an element from a vector or from a List?

std::vector is insanely faster than std::list to find an element. std::vector performs always faster than std::list with very small data. std::vector is always faster to push elements at the back than std::list. std::list handles very well large elements, especially for sorting or inserting in the front.


2 Answers

You didn't say which implementation you were using.

You would need to find out, where the time is spend.

But for me it looks like the implementation of MAP of a list and a vector of equal length to a new vector in your Common Lisp might be very inefficient. Even when consing a new vector, which has some overhead, the implementation can be much faster.

Try to implement the vector operation as a LOOP and compare:

(loop with v = (make-array (length n))
      for n1 across n
      for x1 across x
      for i from 0
      do (setf (aref v i) (* n1 x1))
      finally (return v))

This faster version conses too, but has replaced the list operations with vector operations:

(defparameter *barning-matrixes*
  #(#(1 -2  2) #(2 -1  2) #(2 -2  3) #(1  2  2) #(2  1  2) #(2  2  3) #(-1 2  2) #(-2 1  2) #(-2 2  3)))

(defparameter *lengths* (make-array 1500001 :initial-element 0))

(defun expand-node (n)
  "Takes a primitive Pythagorean triple in a vector and traverses subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
  (let ((perimeter (reduce #'+ n)))
    (unless (> perimeter 1500000)
      (let ((next-nodes
             (loop with v = (make-array (length *barning-matrixes*))
                   for e across *barning-matrixes*
                   for i from 0
                   do (setf (aref v i)
                            (reduce #'+
                                    (loop with v = (make-array (length n))
                                          for n1 across n
                                          for x1 across e
                                          for i from 0
                                          do (setf (aref v i) (* n1 x1))
                                          finally (return v))))
                   finally (return v))))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

(time (expand-node #(3 4 5)))

Let's look at your code:

(defun expand-node (n)

; here we don't know of which type N is. You call it from the toplevel
; with a vector, but recursive calls call it with a list

  "Takes a primitive Pythagorean triple in a vector and traverses
 subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
  (let ((perimeter (reduce #'+ n)))
    (unless (> perimeter 1500000)
      (let ((next-nodes (mapcar #'(lambda (x)    ; this mapcar creates a list
                                    (reduce #'+
                                            (map 'vector
                                                 #'*
                                                 n  ; <- list or vector
                                                 x))) ; <- vector
                                *barning-matrixes*)))
        (loop for i from perimeter to 1500000 by perimeter
              do (incf (aref *lengths* i)))
        (expand-node (subseq next-nodes 0 3))   ; this subseq returns a list most of the times...
        (expand-node (subseq next-nodes 3 6))
        (expand-node (subseq next-nodes 6 9))))))

So you call MAP with a list and a vector most of the times. What is the size of the result vector? MAP has to find out by traversing the list or by some other way. The result vector length is the shortest of the argument sequence lengths. Then it has to iterate over the list and the vector. If MAP now uses generic sequence operations, the element access into the list is always traversing the list. Obviously one can write an optimized version, which does all that faster, but a Common Lisp implementation might choose to provide only a generic implementation of MAP...

like image 135
Rainer Joswig Avatar answered Sep 28 '22 01:09

Rainer Joswig


Welcome to the intricacies of Common Lisp optimization! The first thing to note is about the different program optimization strategies performed by the different implementations: I tried your examples in SBCL, and both of them performed very efficiently with almost the same time, while in CCL the vector version was executed much much slower than the list version. I do not know which implementation you have tried, but you can try to use different implementations to see very different execution times.

From a few tests in CCL it seems to me that the main problem arises from this form:

(map 'vector #'* n x)

which is executed much much slowly than the corresponding list version:

(mapcar #'* n x)

Using time I have seen that the vector version conses a lot.

This first impression has been confirmed by simply changing map with map-into, using an auxiliary vector. Actually the following version is slightly faster in CCL than the list version:

(defun expand-node (n)
"Takes a primitive Pythagorean triple in a vector and traverses subsequent nodes in the the tree of primitives until perimeter > 1,500,000"
   (let ((perimeter (reduce #'+ n))
         (temp-vector (make-array 3 :initial-element 0)))
     (unless (> perimeter 1500000)
       (let ((next-nodes (mapcar #'(lambda (x)
                                   (reduce #'+ (map-into temp-vector #'* n x))) *barning-matrixes*)))
         (loop for i from perimeter to 1500000 by perimeter
               do (incf (aref *lengths* i)))
         (expand-node (subseq next-nodes 0 3))
         (expand-node (subseq next-nodes 3 6))
         (expand-node (subseq next-nodes 6 9))))))
like image 29
Renzo Avatar answered Sep 28 '22 02:09

Renzo