common-lisp - LISP 中两个位向量之间的距离

Question

我在使用普通 lisp 计算两个位向量之间的距离时遇到问题。

我对 lisp 很陌生，这是我人工智能作业的最后一道作业题，我相信我遇到的问题是语法问题。

问题是:

Write a recursive function DISTANCE between two bit vectors of the same length represented by lists of ones and zeros. For example,

(distance '(1 0 1 1) '(0 1 0 1))

Answer: 3

Discuss what would have to be done, if the vectors were of a different length.

根据我的理解，两个位向量之间的距离只是对两者进行异或运算，然后将 1 加起来。

使用示例，我们将得到 1011 ^ 0101 = 1110，这将等于 3。

假设这是计算距离的正确方法，那么我的问题是在 lisp 中找到一种除了递归之外的异或方法。

我如何获取两个列表并将它们放入我可以使用类似logxor (shown here) 的格式？然后计算结果列表中的 1？

在尝试执行 (logxor '(1 0 1 1) '(0 1 0 1))时，它告诉我 '(1 0 1 1) 不是整数，所以看起来logxor 不适用于列表，这让我不知所措。

如果您能提供任何帮助，我们将不胜感激

谢谢!

Answer 1

您的问题提到了“位向量”，但您实际上是在处理位列表。 Common Lisp 实际上提供了一个bit-vector类型，虽然。它是一种特殊类型的数组。不过，它仍然是一个向量，因此您可以使用适用于任意序列(向量或列表)的序列函数，因此您可以为此编写一个适用于位向量以及元素为位的任何其他序列的解决方案，方法是使用map :

(defun distance (bits1 bits2)
  (reduce '+ (map 'bit-vector 'logxor bits1 bits2)))

它按预期工作，但请注意，您可以使用位向量(您可以使用 #*… 符号轻松编写)以及列表。 mapcar 没有这种灵 active ，它只适用于列表。另请注意使用 (reduce '+ …) 而不是 (apply '+ …)。这有两个原因

1. reduce 适用于任意序列，因此您可以将其用于向量和列表。
2. apply 受制于 call-arguments-limit这是可以传递给函数的参数的最大数量。虽然此处的小案例不会与此冲突，但如果您有更大的位向量，则可能会遇到该问题。

CL-USER> (distance #*1011 #*0101)
3
CL-USER> (distance '(1 0 1 1) '(0 1 0 1))
3
CL-USER> (distance #*1011 '(0 1 0 1))
3

Rainer Joswig's answer指出您还可以对整数进行位运算。由于这是一件非常合理的事情(特别是因为您随后可以使用二进制整数表示法)，因此值得制作一个适用于它的版本。这是一个将其所有参数转换为整数(无论它们已经是整数还是位序列)并使用 (logcount (logxor … …)) 的实现:

(defun distance (bits1 bits2)
  (flet ((to-int (bits)
           (if (integerp bits) bits
               (reduce (lambda (int bit)
                         (logior (ash int 1) bit))
                       bits))))
    (logcount (logxor (to-int bits1) (to-int bits2)))))

CL-USER> (distance #b1011 '(0 1 0 1))
3
CL-USER> (distance #*1011 '(0 1 0 1))
3
CL-USER> (distance #*1011 5)
3
CL-USER> (distance 11 5)
3