lisp - 在 Lisp 的可调数组中插入元素

Question

首先，我使用 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 是否在内部将所有元素复制到结果数组，但给了我所需的数组，尽管它不可​​调整且没有填充指针。有什么想法吗？

Answer 1

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

(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 可以使用多种实现方式.