algorithm - 使用哈希查找 float 数组的模式

Question

我最近读到，涉及散列的方法可能是查找 float 数组模式的好方法。我对散列及其应用了解不多，文中没有进一步解释。

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

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

我建议不要使用散列，因为它假设进行精确比较——这对 float 来说从来都不是一个好的假设。你总是想做一个 epsilon comparison某种。如果您的数组包含一些元素 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]