“我很好奇如何使用类似 Lisp 的语言来实现这一点。 ”这实际上取决于您使用的是哪种 Lisp。在 Scheme 中,您可能会执行类似于已发布的 Hy 解决方案的操作:
(define (cos-sim-1 u v)
(/ (dot-prod u v)
(* (norm u) (norm v))))
(define (dot-prod u v)
(fold-left + 0 (map * u v)))
(define (norm u)
(sqrt (fold-left (lambda (acc x) (+ acc (* x x)))
0
u)))
这在时间复杂度上是线性的,但可以通过只传递一次输入来通过一个常数因子来改进。Scheme 提供了一个命名let
构造,可用于将名称绑定到过程;这在这里很方便,因为它提供了一个简单的机制来构建点积和规范:
(define (cos-sim-2 u v)
(let iter ((u u)
(v v)
(dot-product 0)
(U^2 0)
(V^2 0))
(if (null? u)
(/ dot-product (sqrt (* U^2 V^2)))
(let ((x (car u))
(y (car v)))
(iter (cdr u)
(cdr v)
(+ dot-product (* x y))
(+ U^2 (* x x))
(+ V^2 (* y y)))))))
这两个过程都假设输入列表具有相同的长度;添加一些验证代码来检查这一点可能很有用。请注意,这fold-left
是 R6RS 方案中的标准,但其他标准为此依赖 SRFI,并且某些实现可能使用不同的名称,但该fold-left
功能通常是可用的(可能是foldl
或reduce
)。
可以使用上面显示的任何一种基本方法来解决 Common Lisp 中的问题,尽管在 Common Lisp 中您将使用labels
而不是 named let
。但是通常会看到使用loop
宏的 Common Lisp 解决方案。Common Lisp 标准不保证尾调用消除(尽管一些实现确实支持),因此显式循环比在 Scheme 中更常见。该loop
宏非常强大,您可以在只传递一次输入列表时解决此问题的一种方法是:
(defun cos-sim (u v)
(loop :for x :in u
:for y :in v
:sum (* x y) :into dot-product
:sum (* x x) :into u2
:sum (* y y) :into y2
:finally (return (/ dot-product (sqrt (* u2 y2))))))
以下是一些示例交互:
方案(Chez 方案):
> (cos-sim-1 '(1 0 0) '(1 0 0))
1
> (cos-sim-1 '(1 0 0) '(-1 0 0))
-1
> (cos-sim-1 '(1 0 0) '(0 1 0))
0
> (cos-sim-1 '(1 1 0) '(0 1 0))
0.7071067811865475
> (cos-sim-2 '(1 0 0) '(1 0 0))
1
> (cos-sim-2 '(1 0 0) '(-1 0 0))
-1
> (cos-sim-2 '(1 0 0) '(0 1 0))
0
> (cos-sim-2 '(1 1 0) '(0 1 0))
0.7071067811865475
普通 Lisp:
CL-USER> (cos-sim '(1 0 0) '(1 0 0))
1.0
CL-USER> (cos-sim '(1 0 0) '(-1 0 0))
-1.0
CL-USER> (cos-sim '(1 0 0) '(0 1 0))
0.0
CL-USER> (cos-sim '(1 1 0) '(0 1 0))
0.70710677