确定位数组是否在位数组集合中

Question

给定 2 维 NxN 位数组，我正在尝试评估确定位数组是否已经在以前见过的位数组的大型集合中的最佳方法。

一种直接的方法是将位数组放在散列中 table。但是比较数组需要一个#'equalp :test 函数，这可能不是很有效。（但也许 SBCL 会自动针对不同的密钥类型进行优化？）

另一个计划是将所有位数组转换为整数，并将整数放入散列中table。然后测试可以是#'eql:

(defun bit-arr-to-int (bit-array)
  (reduce (lambda (bit1 bit2)
            (+ (* bit1 2) bit2))
          (make-array (array-total-size bit-array)
                      :displaced-to bit-array)))

但不确定这是否最终会比让 SBCL 处理事情更有效，因为它仍然单独处理每个元素。也许自定义哈希 table 会提供效率优势？

第三个选项可能涉及将基本表示从位数组更改为简单的位向量（也称为整数），因为原始位数组的维度是已知的。要允许数组等效元素引用，这需要一个函数将隐式数组行、列坐标转换为显式简单位向量索引。根据需要计算索引可能比为每个散列 table 查找将整个位数组转换为整数更有效，如上所述。

感谢一些有经验的见解。

Answer 1

我认为了解这一点的唯一方法是尝试并查看最快的方法。

您可以尝试的一个可怕技巧是将 bit-vectors 表示为 (row-length . integer-of-bits) 的缺点。您需要行长度，以便可以计算整数位的偏移量。然后你可以这样做（这些可能是错误的，因为我总是被 dpb 和 ldb 搞糊涂）：

(deftype index ()
  `(integer 0 ,most-positive-fixnum))

(defun make-bv (columns)
  (declare (type index columns))
  (cons columns 0))

(defun bv-ref (bv row column)
  (declare (type (cons index integer) bv)
           (type index row column))
  (let ((columns (car bv)))
    (assert (< column columns) (column) "column out of range")
    (ldb (byte 1 (+ (* row columns) column)) (cdr bv))))

(defun (setf bv-ref) (bit bv row column)
  (declare (type bit bit)
           (type (cons index integer) bv)
           (type index row column))
  (let ((columns (car bv)))
    (assert (< column columns) (column) "column out of range")
    (setf (cdr bv) (dpb bit (byte 1 (+ (* row columns) column)) (cdr bv)))
    bit))

在现实生活中你当然想要内联这些东西。

像这样的表示可能适合散列（您可以只对 equal 进行散列，或者甚至为 cons 中的两个元素嵌套 eql 散列表），但它的显着问题是不关心对象有多少行：它们基本上都有无限行数。

如果 'arrays' 非常大并且您经常更改其中的位，那就太糟糕了，因为每次更改位都会产生一个新的 bignum。

但我认为了解的唯一方法是测量。

确定位数组是否在位数组集合中

Determining if a bit array is in a collection of bit arrays

arrays

common-lisp

bitarray

bitvector