Как (zerop # * 000) в общем лиспе? - PullRequest
Новая
       17

Как (zerop # * 000) в общем лиспе?

6 голосов
/ 22 апреля 2020

Есть ли эффективный способ проверить, все ли битовые векторы равны нулю? (Я использую SBCL на Linux.) Я просмотрел документацию, но не смог найти подходящую функцию. Лучшее, что я придумал, это: 

(defun bit-zerop (array)
  (equal array (make-array (length array) :element-type 'bit)))

(bit-zerop #*000)

Я также пробовал 

(defun bit-zerop (array)
  (dotimes (i (length array))
    (if (eql (sbit array i) 1)
        (return-from bit-zerop nil)))
  t)

, но на больших битовых векторах он примерно в 100 раз медленнее, чем в первой версии , (Что ожидается, поскольку каждое 64-битное слово читается 64 раза, я думаю, а не только один раз). Конечно, первая версия является неоптимальной и должна выделять новый массив.

РЕДАКТИРОВАТЬ: время для упомянутых решений.

РЕДАКТИРОВАТЬ 2 : время с объявлениями типа. 

(defun bit-zerop-1 (array)
  ;; (declare (simple-bit-vector array))
  (equal array (make-array (length array) :element-type 'bit)))

(defun bit-zerop-2 (array)
  ;; (declare (simple-bit-vector array))
  (every #'zerop array))

(defun bit-zerop-3 (array)
  ;; (declare (simple-bit-vector array))
  (loop
     for bit across array
     never (= bit 1)))

(defun bit-zerop-4 (array)
  ;; (declare (simple-bit-vector array))
  (not (find 1 array)))

(dolist (func '(bit-zerop-1 bit-zerop-2 bit-zerop-3 bit-zerop-4))
  (dolist (size '(10 100 1000))
    (let ((x (make-array size :element-type 'bit)))
      (format t "Testing ~a on ~a elements~%" func size)
      (time
       (dotimes (i 1000000)
         (funcall func x))))))

дает 

===============================================
method         size 10    size 100    size 1000
------------------- untyped -------------------
bit-zerop-1    0.030 s     0.030 s      0.058 s
bit-zerop-2    0.112 s     1.000 s      9.324 s
bit-zerop-3    0.111 s     0.935 s      8.742 s
bit-zerop-4    0.047 s     0.047 s      0.063 s
-------------------- typed --------------------
bit-zerop-1    0.025 s     0.023 s      0.040 s
bit-zerop-2    0.036 s     0.315 s      3.005 s
bit-zerop-3    0.041 s     0.348 s      3.346 s
bit-zerop-4    0.010 s     0.012 s      0.026 s
===============================================

Ответы [ 2 ]

4 голосов
/ 22 апреля 2020

Вот вариант: 

(defun bit-vector-zerop (bit-vector)
  (not (find 1 bit-vector)))

Это не имеет недостатков и очень эффективно для SBCL. Это быстрее, если вы можете объявить аргумент битовым вектором.

2 голосов
/ 22 апреля 2020

Я не уверен, есть ли какая-либо специальная функция logi c, см., Например, здесь .

Но как насчет этого? 

(loop
  for bit across #*0000
  never (= bit 1))
...