CODEWITHSUNDEEP
lispcommon-lispadjustable-array
FrankS101
FrankS101

Reputation: 2135

insert element in adjustable array in Lisp

First of all, I work with LispWorks. I have an adjustable array where I want to insert an element in position i < fill-pointer, so I will need to move all the elements from i to its position + 1. My problem is I don't know how to do that and have as result an adjustable array but WITHOUT COPYING all the elements to another array. Performance is really important. With this array #(0 1 2 3 4 6 7) my way to insert number 5 in position i=5:

(let ((arr (make-array 7 :initial-contents (list 0 1 2 3 4 6 7) 
                     :adjustable T :fill-pointer 7))
      (i 5)) 
    (concatenate 'vector (subseq arr 0 i)
                         (make-array 1 :initial-contents '(5))
                         (subseq arr i (fill-pointer arr))))

which I don't know if LispWorks is internally copying all elements to the result array, but gives me the desired array, although it is no adjustable and does not have fill-pointer. Some idea?

Upvotes: 2

Views: 3018

Answers (2)

sds
sds

Reputation: 60074

First of all, your code conses far too much.

Here is a version which conses as little as possible:

(defun insert-into-array (vector value position)
  (vector-push-extend value vector) ; ensure that the array is large enough
  ;; shift the end of the array right
  (loop for i from (1- (length vector)) downto (1+ position) do
      (setf (aref vector i) (aref vector (1- i))))
  (setf (aref vector position) value) ; insert value into the right place
  vector)
(insert-into-array (make-array 9 :initial-contents '(0 1 2 3 4 6 7 8 9) 
                                 :adjustable T :fill-pointer 9) 5 5)
==> #(0 1 2 3 4 5 6 7 8 9)

Note that this will do N assignments in the worse case, so, if insertion is a common operation in your setup and you do not need random access, you might want to consider linked lists instead of arrays.

EDIT: I forgot about replace, which makes the loop unnecessary:

(defun insert-into-array (vector value position)
  (replace vector vector :start2 position :start1 (1+ position) 
           :end2 (vector-push-extend value vector))
  (setf (aref vector position) value) 
  vector)

Upvotes: 3

huaiyuan
huaiyuan

Reputation: 26549

To increase optimization opportunities for your compiler, use specialized simple-array if possible; i.e., avoid fill-pointer and adjustable array. Also, higher level operation such as replace should allow memory to be moved in blocks (instead of one word at a time).

(defun insert-at (vec i val)
  (check-type vec (simple-array fixnum 1))
  (let ((new (make-array (1+ (length vec)) :element-type 'fixnum)))
    (declare (optimize speed))
    (setf (aref new i) val)
    (replace new vec :end1 i)
    (replace new vec :start1 (1+ i) :start2 i)))

Repeat 100 times to get more meaningful benchmark result(using sbcl):

(let ((arr (make-array 1000000 :element-type 'fixnum)))
  (time (loop repeat 100 for i from 500000 do
          (insert-at arr i i))))

Evaluation took:
  0.988 seconds of real time
  0.992062 seconds of total run time (0.804051 user, 0.188011 system)
  [ Run times consist of 0.148 seconds GC time, and 0.845 seconds non-GC time. ]
  100.40% CPU
  2,962,811,250 processor cycles
  800,003,200 bytes consed

Probably you should look at heap, which allows O(log n) insertion while maintaining (some sort of) order. Several implementations are available via quicklisp.

Upvotes: 4

Related Questions