使用散列查找浮点数数组的众数

Question

我最近读到，涉及散列的方法可能是查找浮点数数组众数的好方法。我对哈希或其应用了解不多，文本也没有进一步解释。

有谁知道这个方法会涉及什么？

Answer 1

J

   NB. random array of floating-point numbers
   ] y =: 10 (?@$%]) 5
0 0.6 0.2 0.4 0.4 0.8 0.6 0.6 0.8 0
   NB. count occurrences
   ({:,#)/.~ y
  0 2
0.6 3
0.2 1
0.4 2
0.8 2
   NB. order by occurrences
   (\:{:"1)({:,#)/.~ y
0.6 3
  0 2
0.4 2
0.8 2
0.2 1
   NB. pick the most frequent
   {.{.(\:{:"1)({:,#)/.~ y
0.6

我建议不要使用哈希，因为它假设精确比较——这对浮点数来说并不是一个好的假设。您总是想要进行某种epsilon 比较。如果您的数组包含一些元素0.2(00000000)和0.2(00000001)，它们实际上应该被认为是相等的，但不是因为它们来自不同的计算，该怎么办？

方便的是，J总是默认进行 epsilon 比较。太方便了，因为它隐藏在 中，/.~我必须编写更多代码才能演示如何在其他语言（如 Python）中执行此操作...

epsilon = 0.0001
def almost_equal(a, b):
    return -epsilon <= a-b <= epsilon

array = [0.0, 0.6, 0.2, 0.4, 0.4, 0.8, 0.6, 0.6, 0.8, 0.0]

# more efficient would be to keep this in sorted order,
# and use binary search to determine where to insert,
# but this is just a simple demo
counts = []
for a in array:
    for i, (b, c) in enumerate(counts):
        if almost_equal(a, b):
            counts[i] = (b, c + 1)
            break
    else:
        counts.append((a, 1))

# sort by frequency, extract key of most frequent
print "Mode is %f" % sorted(counts, key = lambda(a, b): b)[-1][0]