2

首先，我使用 LispWorks。我有一个可调整的数组，我想在位置 i < 填充指针中插入一个元素，所以我需要将所有元素从 i 移动到它的位置 + 1。我的问题是我不知道该怎么做结果是一个可调整的数组，但没有将所有元素复制到另一个数组。性能真的很重要。使用这个数组 #(0 1 2 3 4 6 7) 我在位置 i=5 中插入数字 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))))

我不知道 LispWorks 是否在内部将所有元素复制到结果数组，但给了我所需的数组，尽管它不可​​调整且没有填充指针。有什么想法？

4

2 回答 2

3

首先，你的代码太多了。

这是一个尽可能少的版本：

(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)

请注意，这将N在最坏的情况下进行分配，因此，如果插入是您设置中的常见操作并且您不需要随机访问，您可能需要考虑链表而不是数组。

编辑：我忘记了replace，这使得循环变得不必要：

(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)
于 2013-06-09T13:23:41.587 回答
3

为了增加编译器的优化机会，尽可能使用专门的简单数组；即，避免填充指针和可调整数组。此外，更高级别的操作，例如replace应该允许以块的形式移动内存（而不是一次一个字）。

(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)))

重复 100 次以获得更有意义的基准测试结果（使用 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

可能您应该查看heap，它允许在保持（某种）顺序的同时进行 O(log n) 插入。通过quicklisp可以获得几个实现。

于 2013-06-09T19:34:06.420 回答