使用哈希集的 Racket 中的平方欧氏距离

Question

我正在尝试编写一个计算 squared Euclidean distance 的函数。我最初将数据存储在以下形式的列表中：

'(1 8 0 0 0 1 0 5 0 1)
'(1 0 2 0 0 0 0 5 0 0)

基本上我试图获得的是以下总和：

'(0 64 4 0 0 1 0 0 0 1)

使用列表这并不难实现，就像下面的代码一样：

(define (f a b)
  (apply + (map (λ(x y) (sqr (- x y))) a b)))

但是我正在处理的数据中有很多零，所以我尝试用散列集替换列表，如下所示：

'#hash((0 . 1) (1 . 8) (5 . 1) (7 . 5) (9 . 1))
'#hash((0 . 1) (2 . 1) (7 . 5))

在这里，当我尝试重写 f 函数时，我遇到了哈希集问题，因为我不知道如何直接遍历它们。到目前为止，我写的内容没有计算第二个哈希集中的元素，但不计算第一个哈希集中的元素。

(define (f a b)
  (for/fold ([sum 0])
            ([(k v) (in-hash a)])
    (+ sum (sqr (- (hash-ref b k 0) v)))))

有没有办法快速实现（最好使用单个for）？或者也许有更好的方法来处理稀疏列表（包含许多零）？

Answer 1

问题是，我们需要处理两个哈希中的缺失值。只迭代具有实际值的索引，我们可以这样做：

(define (squared-euclidean-distance a b)
  (for/fold ([sum 0])
            ([idx (set-union (hash-keys a) (hash-keys b))])
    (+ sum (sqr (- (hash-ref a idx 0)
                   (hash-ref b idx 0))))))

如果缺少索引，我们只需 return 0。它按预期工作：

(squared-euclidean-distance
 '#hash((0 . 1) (1 . 8) (5 . 1) (7 . 5) (9 . 1))
 '#hash((0 . 1) (2 . 2) (7 . 5)))
=> 70

Answer 2

一个解决方案是获取出现在稀疏向量中的所有索引的列表，然后映射到该索引列表以计算平方距离：

(define (sparse-sum-of-squares u v)
  (let ((indices (remove-duplicates (append (hash-keys u) (hash-keys v)))))
    (apply + (map (lambda (i) (let ((x (hash-ref u i 0))
                                    (y (hash-ref v i 0)))
                                (sqr (- x y))))
                  indices))))

在开始使数据表示复杂化之前，您可能应该对数据进行一些实际测试，看看性能是否是一个问题。在修复发布示例中的稀疏向量使其匹配后，结果如下：

sparse-vector.rkt> (f '(1 8 0 0 0 1 0 5 0 1)
                      '(1 0 2 0 0 0 0 5 0 0))
70
sparse-vector.rkt> (sparse-sum-of-squares '#hash((0 . 1) (1 . 8) (5 . 1) (7 . 5) (9 . 1))
                                          '#hash((0 . 1) (2 . 2) (7 . 5)))
70

使用哈希集的 Racket 中的平方欧氏距离

Squared euclidean distance in Racket using a hash-set

racket