algorithm - 计算 2 个整数列表的增量

Question

我有 2 张 map :map1 和 map2。其中字符串是一个键，值是该键出现的次数。

我想比较 map 之间的“增量”，即我想知道一张表与另一张表的距离，但我不确定计算该差异的正确函数是什么。

例如:

map 1:阿巴 100美国 10

map 2:阿巴 300美国 210

ABBA 在 map 1 和 2 中的出现次数相差 200，USA 在 map 1 和 2 中的出现次数也相差 10/210 << 100/300，但显然不是相同的差异。所以它不会帮助我对绝对差异进行平均。

另一方面，使用除法也是不对的，因为 0/100 == 0/1000。我知道我需要以某种方式结合这两种方法，但我不确定该怎么做。

Answer 1

如果您将 map 视为矢量，在数学意义上，那么您可以通过减去匹配元素来计算所有通常的距离(度量)。

假设您想要 Manhattan (L1) distance .这是两个向量中匹配元素的绝对差之和:

d = 0
for key in map1:
    if key in map2:
        d += abs(map1[key] - map2[key])
    else:
        d += abs(map1[key])  # implicit zero in the other map

for key in map2:
    if key not in map1:
        d += abs(map2[key])

类似地，您可以计算 Euclidean distance ，这是差平方和的平方根:

d = 0
for key in map1:
    for key in map2:
        d += (map1[key] - map2[key]) ^ 2
    else:
        d += map2[key] ^ 2

for key in map2:
    if key not in map1:
        d += abs(map2[key])

d = sqrt(d)

如果 map 查找的时间复杂度为 O(1)，那么这两者都可以在线性时间内计算出来，许多其他距离也是如此。