确定位阵列是否在位阵列的集合中

Question

给定二维NxN位数组，我正在尝试评估确定一个位数组是否已经在以前看到的大量位数组中的最佳方法。

一种简单的方法是将位数组放入哈希表中。但是比较数组需要一个#'equip:test函数，这可能不是很有效。(但SBCL可能会自动针对不同的密钥类型进行优化？(

另一个方案是将所有位数组转换为整数，并将整数放入哈希表中。然后测试可以是#'ql:

(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处理事情更有效，因为它仍然单独处理每个元素。也许定制的哈希表会提供效率优势？

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

欣赏一些经验丰富的见解。

Answer 1

我认为知道这一点的唯一方法是尝试，看看什么是最快的。

您可以尝试的一个可怕的技巧是将位向量表示为(row-length . integer-of-bits)的cons。您需要行长度，这样您就可以以位的整数计算偏移量。然后你可以做这样的事情(这些可能是错误的，因为我总是被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哈希表(，但值得注意的问题是，它不在乎对象有多少行：它们本质上都有无限数量的行。

如果"数组"非常大，并且你经常更改其中的位，那就太可怕了，因为每次更改一位都会产生一个新的bignum。

但我认为知道的唯一方法是测量。